87 lines
1.8 KiB
C++
87 lines
1.8 KiB
C++
#include "avl.h"
|
|
#include "algorithm"
|
|
|
|
int getHeight(AVL_tree *root) {
|
|
if (!root)
|
|
return 0;
|
|
return root->height;
|
|
}
|
|
|
|
AVL_tree *rightRotate(AVL_tree *y) {
|
|
AVL_tree *x = y->left;
|
|
AVL_tree *T2 = x->right;
|
|
|
|
x->right = y;
|
|
y->left = T2;
|
|
|
|
y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
|
|
x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
|
|
|
|
return x;
|
|
}
|
|
|
|
AVL_tree *leftRotate(AVL_tree *x) {
|
|
AVL_tree *y = x->right;
|
|
AVL_tree *T2 = y->left;
|
|
|
|
y->left = x;
|
|
x->right = T2;
|
|
|
|
x->height = 1 + std::max(getHeight(x->left), getHeight(x->right));
|
|
y->height = 1 + std::max(getHeight(y->left), getHeight(y->right));
|
|
|
|
return y;
|
|
}
|
|
|
|
int getBalance(AVL_tree *root) {
|
|
if (!root)
|
|
return 0;
|
|
return getHeight(root->left) - getHeight(root->right);
|
|
}
|
|
|
|
AVL_tree *insertAVL(AVL_tree *root, int value) {
|
|
if (root == nullptr) {
|
|
return new AVL_tree{value, nullptr, nullptr, 1};
|
|
}
|
|
|
|
if (value < root->info) {
|
|
root->left = insertAVL(root->left, value);
|
|
} else if (value > root->info) {
|
|
root->right = insertAVL(root->right, value);
|
|
} else {
|
|
return root;
|
|
}
|
|
|
|
root->height = 1 + std::max(getHeight(root->left), getHeight(root->right));
|
|
|
|
int balance = getBalance(root);
|
|
|
|
if (balance > 1 && value < root->left->info) {
|
|
return rightRotate(root);
|
|
}
|
|
|
|
if (balance < -1 && value > root->right->info) {
|
|
return leftRotate(root);
|
|
}
|
|
|
|
if (balance > 1 && value > root->left->info) {
|
|
root->left = leftRotate(root->left);
|
|
return rightRotate(root);
|
|
}
|
|
|
|
if (balance < -1 && value < root->right->info) {
|
|
root->right = rightRotate(root->right);
|
|
return leftRotate(root);
|
|
}
|
|
|
|
return root;
|
|
}
|
|
|
|
void deleteAVL(AVL_tree *root){
|
|
if (root != nullptr) {
|
|
deleteAVL(root->left);
|
|
deleteAVL(root->right);
|
|
delete root;
|
|
}
|
|
}
|