AVL-tree. Не подскажете, что неверно в add?
Добавил некоторые функции и изменил add обычного дерева, чтобы было AVL. Но у меня почему-то какие-то ошибки при развороте. В примере в main ошибка, Под конец, когда добавляем 444, там должен быть LL разворот, но он что-то не то возвращает И ПРАДед 444 должен смотреть на отца 444, но он почему-то не меняет указатель и ПРАДЕД 444 все так же смотрит на ДЕДА 444. Функции, которые я добавил : REBALANCE, CHECKbalance и Повороты.
#include <iostream>
using namespace std;
#include<iostream>
using namespace std;
struct Node {
int val;
Node* left, * right;
int bal;
Node* parent;
Node(int val) {
this->val = val;
parent = left = right = NULL;
bal = 0;
}
};
class Tree {
private:
Node* main_root;
void Destroy(Node* root) {
if (root == NULL)return;
Destroy(root->left);
Destroy(root->right);
delete root;
}
int Size(Node* root) {
if (root == NULL)return 0;
int s1 = Size(root->left);
int s2 = Size(root->right);
return 1 + s1 + s2;
}
int Height(Node* root) {
if (root == NULL)return 0;
int h1 = Height(root->left);
int h2 = Height(root->right);
return 1+ (h1 > h2 ? h1 : h2);
}
void PPrint(Node* root, int hh) {
if (root == NULL) {
for (int i = 0; i < hh; i++) cout << " ";
cout << "@" << endl;
return;
}
PPrint(root->right, hh + 2);
for (int i = 0; i < hh; i++) cout << " ";
cout << root->val << endl;
PPrint(root->left, hh + 2);
}
void Print_in(Node* root) {
if (root == NULL)return;
Print_in(root->left);
cout << (root->val) << " ";
Print_in(root->right);
}
void Print_pre(Node* root) {
if (root == NULL)return;
cout << (root->val) << " ";
Print_pre(root->left);
Print_pre(root->right);
}
void Print_post(Node* root) {
if (root == NULL)return;
Print_post(root->left);
Print_post(root->right);
cout << (root->val) << " ";
}
//**********************************************
void Rebalance(Node*node) {
if (node->bal < -1) {
if (Height(node->left->left) > Height(node->left->right))
node = RIGHT(node);
else
node = L_R(node);
}
else
if (node->bal > 1) {
if(Height(node->right->right) > Height(node->right->left))
node = LEFT(node);
else
node = R_L(node);
}
}
void CHECKbalance(Node*node){
Node* cur = node;
while (cur!= NULL) {
cur->bal = Height(cur->right) - Height(cur->left);
if (cur->bal > 1 || cur->bal < -1) Rebalance(cur);
cur = cur->parent;
}
}
////************************************
Node* LEFT(Node* node) {
Node* temp = node->right;
Node* node_par = node->parent;
// if (node_par != NULL)node_par->right = temp;
node->right = temp->left;
if (temp->left != NULL)temp->left->parent = node;
temp->left = node;
node->parent = temp;
temp->parent = node_par;
if (node == main_root){
main_root = temp;
return main_root;
}
return temp;
}
Node* RIGHT(Node* node) {
Node* temp = node->left;
Node* node_par = node->parent;
node->left = temp->right;
if(temp->right !=NULL)temp->right->parent = node;
temp->right = node;
node->parent = temp;
temp->parent = node_par;
if (node == main_root) {
main_root = temp;
return main_root;
}
return temp;
}
Node* L_R(Node* node) {
node->left = LEFT(node->left);
return RIGHT(node);
}
Node* R_L(Node* node) {
node->right = RIGHT(node->right);
return LEFT(node);
}
public:
Tree() {
main_root = NULL;
}
Tree(int x) {
main_root = new Node(x);
}
~Tree() {
Destroy(main_root);
}
//@@@@------------
void Remove(int x) {
if (main_root == NULL)return;
Node* cur = main_root;
Node* par = main_root;
while (cur != NULL && cur->val != x) {
par = cur;
if (cur->val > x)cur = cur->left;
else cur = cur->right;
}
if (cur == NULL)return;
// if (cur == main_root)return;
// 1 случай, это лист
if (cur->right == NULL && cur->left == NULL) {
if (par->right == cur) {
par->right = NULL;
delete cur;
}
else if (par->left == cur) {
par->left = NULL;
delete cur;
}
else if (par == cur) {
return;
}
return;
}
// 2 случай, есть только правый
if (cur->left == NULL && cur->right != NULL) {
if (par->right == cur) {
par->right = cur->right;
delete cur;
}
else if (par->left == cur) {
par->left = cur->right;
delete cur;
}
else if (cur == par) {
main_root = cur->right;
delete cur;
}
return;
}
// 3 случай, есть только левый
if (cur->right == NULL && cur->left != NULL) {
if (par->right == cur) {
par->right = cur->left;
delete cur;
}
else if (par->left == cur) {
par->left = cur->left;
delete cur;
}
else if (cur == par) {
main_root = cur->left;
delete cur;
}
return;
}
// 4 случай, есть оба
if (cur->right != NULL && cur->left != NULL) {
Node* small = cur->right;
Node* small_par = cur;
while (small->left != NULL) {
small_par = small;
small = small->left;
}
cur->val = small->val;
if (small_par->right == small) {
small_par->right = small->right;
}
else small_par->left = small->right;
delete small;
}
}
//@@@@-------------
bool add(int x) {
if (main_root == NULL) {
main_root = new Node(x);
main_root->bal = 0;
return 1;
}
Node* cur = main_root;
while (true) {
if (cur->val > x) {
if (cur->left == NULL) {
cur->left = new Node(x);
cur->left->parent = cur;
CHECKbalance(cur->left);
return 1;
}
else cur = cur->left;
}
else if (cur->val == x) { return false; }
else {
if (cur->right == NULL) {
cur->right = new Node(x);
cur->right->parent = cur;
CHECKbalance(cur->right);
return 1;
}
else cur = cur->right;
}
}
}
//------------
int height() {
return Height(main_root);
}
//-------------
void print_preorder() {
Print_pre(main_root);
cout << endl;
}
void print_inorder() {
Print_in(main_root);
cout << endl;
}
void print_postorder() {
Print_post(main_root);
cout << endl;
}
//-------------
void print() {
PPrint(main_root, 0);
}
int size() {
return Size(main_root);
}
};
int main()
{
Tree TT;
TT.add(5);
TT.add(2);
TT.add(7);
TT.add(1);
TT.add(4);
TT.add(3);
TT.add(444);
//TT.add(11);
TT.print();
}