алгоритм — C ++ AVL Проблемы балансировки дерева

Я построил дерево AVL из старого двоичного дерева в C ++ для практики, и оно работает неправильно. Я думаю, что это может не обновлять высоту узлов правильно, но я не могу выяснить корень проблемы (я на 90% уверен, что это связано с вспомогательными функциями getHeight, setHeight, getBalance).

Некоторые примеры тестовых прогонов ..:

добавление 6,3,4 вызывает вращение вправо, оно должно вызывать вращение RL

аналогично добавление 20,30,25 вызывает вращение LL, когда оно должно вызывать вращение LR

добавление 20,30,10,5,6 вызывает два отдельных вращения вправо, когда это должно вызвать вращение RL

#include <string>
#include <sstream>
#include <iostream>
#include <fstream>
#include <iomanip>
#include <cstdlib>

using namespace std;

struct intNode {
int data;
intNode * Left;
intNode * Right;
int height;

intNode(int input, intNode * iLeft= NULL, intNode * iRight = NULL) {
data = input;
Left = iLeft;
Right = iRight;
height = 0;
}

};

int getHeight(intNode* temp) {
if (temp == NULL)
return 0;
return temp->height;
}

void setHeight(intNode * temp)
{
int hLeft = getHeight(temp->Left);
int hRight = getHeight(temp->Right);
temp->height = 1 + max(hLeft, hRight);
}

int getBalance(intNode * temp) {

if (temp == NULL) {
return 0;
} else {
return getHeight(temp->Left) - getHeight(temp->Right);
}
}struct intTree {
intNode * root;

intTree();
void addNode(int input);
void addNode(int input, intNode *& root);
void print();
void print(intNode *input);

intNode * balanceTree(intNode *& sub);
intNode * rotateRight(intNode *& sub);
intNode * rotateLeft(intNode *& sub);

};

void intTree::print(intNode *input) {

if (input != NULL) {
print(input->Left);
cout << input->data << endl;
print(input->Right);
}

}

void intTree::print() {
print(root);
}

intNode * intTree::rotateRight(intNode *& subTree) {
intNode * newRoot = subTree->Left;
subTree->Left = newRoot->Right;
newRoot->Right = subTree;
setHeight(subTree);
setHeight(newRoot);

return newRoot;
}

intNode * intTree::rotateLeft(intNode *& subTree) {
intNode * newRoot = subTree->Right;
subTree->Right = newRoot->Left;
newRoot->Left = subTree;
setHeight(subTree);
setHeight(newRoot);

return newRoot;
}

intNode* intTree::balanceTree(intNode *& subTree) {
setHeight(subTree);

if (getBalance(subTree) == 2 && getBalance(subTree->Right) < 0) {
cout << "RL" << endl;
subTree->Left = rotateLeft(subTree->Left);
return rotateRight(subTree);

} else if (getBalance(subTree) == 2) {                    // RR
cout << "RR" << endl;
return rotateRight(subTree);

} else if (getBalance(subTree) == -2 && getBalance(subTree->Left) > 0) {  // LR
cout << "LR" << endl;
subTree->Right = rotateRight(subTree->Right);
return rotateLeft(subTree);

} else if (getBalance(subTree) == -2) {                   // LL
cout << "LL" << endl;
return rotateLeft(subTree);

} else {
return subTree;                                 // balanced
}

}

intTree::intTree() {
root = NULL;
}

void intTree::addNode(int input, intNode *& temp) {
if (temp == NULL) {
temp = new intNode(input);
} else if (input < temp->data) {
cout <<" added to the left" << endl;
addNode(input,temp->Left);
} else if (input > temp->data) {
cout <<" added to the right" << endl;
addNode(input, temp->Right);
}

temp = balanceTree(temp);

}

void intTree::addNode(int input) {
addNode(input, root);
}

void read() {
string num;
int balance, input;
int i = 0;

intTree * intBST = new intTree();

while (i != 10) {
cout << "number?" << endl;
cin >> input;intNode *tempInt= new intNode(input);
intBST->addNode(input);

i++;
}

cout << "Finished reading in files" << endl;

while (true) {
string userInput;
cin >> userInput;

if (userInput == "Exit") {
cout << "Goodbye!" << endl;
return;
}

if (userInput == "Print") {
intBST->print();
return;
}

}
}void main() {
read();

return 0;
}

Буду признателен за любые советы / помощь по дальнейшему выяснению этого. Дайте мне знать, если я могу предоставить дополнительную информацию, чтобы помочь.

Спасибо.

2

Решение

Задача ещё не решена.

Другие решения

Других решений пока нет …

По вопросам рекламы [email protected]