Created
March 17, 2021 01:56
-
-
Save Marcellofabrizio/18546cd2610ef6467bf2ddbcf71ec64f to your computer and use it in GitHub Desktop.
AVL Tree in C++. Did this in a rush for an assigment, so if this is usefull to you, please help improving it so it could be helpful to others too!
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include <iostream> | |
| using namespace std; | |
| class Node { | |
| public: | |
| int value; | |
| int height; | |
| Node* left; | |
| Node* right; | |
| private: | |
| void insertNode(int key, Node* node); | |
| }; | |
| Node* getLowestNode(Node *node); | |
| int max(int a, int b) { | |
| return (a > b) ? a : b; | |
| } | |
| int height(Node* Node) { | |
| if(Node == NULL) { | |
| return 0; | |
| } | |
| else { | |
| int LHeight = height(Node->left); | |
| int RHeight = height(Node->right); | |
| if(LHeight > RHeight) { | |
| return LHeight + 1; | |
| } else return RHeight + 1; | |
| } | |
| } | |
| int balance_factor(Node* node) { | |
| if(node == NULL) { | |
| return 0; | |
| } | |
| return height(node->left) - height(node->right); | |
| } | |
| Node* new_node(int value) { | |
| Node* new_node = new Node; | |
| new_node->value = value; | |
| new_node->right = NULL; | |
| new_node->left = NULL; | |
| new_node->height = 1; | |
| return new_node; | |
| } | |
| /* | |
| To balance an AVL Tree | |
| --> inserts the value V into the tree | |
| --> starting from V, searches the firts unbalanced node | |
| --> do the folowing rotations | |
| */ | |
| Node *rotate_left(Node *x) { | |
| Node *y = x->right; | |
| Node *aux = y->left; | |
| y->left = x; | |
| x->right = aux; | |
| x->height = max(height(x->left), height(x->right)) + 1; | |
| y->height = max(height(y->left), height(y->right)) + 1; | |
| return y; | |
| } | |
| Node *rotate_right(Node *x) { | |
| Node *y = x->left; | |
| Node *aux = y->right; | |
| y->right = x; | |
| x->left = aux; | |
| x->height = max(height(x->left), height(x->right)) + 1; | |
| y->height = max(height(y->left), height(y->right)) + 1; | |
| return y; | |
| } | |
| Node *rotate_right_left(Node *z) { | |
| /* | |
| Being Z father of X and X father of Y, | |
| Z | |
| / \ | |
| X B | |
| / \ | |
| A Y | |
| Rotate right X-Y | |
| Rotate left Y-Z | |
| */ | |
| z->right = rotate_right(z->right); | |
| return rotate_left(z); | |
| } | |
| Node *rotate_left_right(Node *z) { | |
| /* | |
| Being Z father of X and X father of Y, | |
| Z | |
| / \ | |
| B X | |
| / \ | |
| A Y | |
| Rotate left X-Y | |
| Rotate right Y-Z | |
| */ | |
| z->left = rotate_left(z->left); | |
| return rotate_right(z); | |
| } | |
| Node *insertNode(int key, Node* node) { | |
| if(node == NULL) { | |
| return(new_node(key)); | |
| } | |
| if(node->value > key) { | |
| node->left = insertNode(key, node->left); | |
| } | |
| else if(node->value < key) { | |
| node->right = insertNode(key, node->right); | |
| } | |
| else { | |
| return node; | |
| } | |
| node->height = max(height(node->left), height(node->right)) + 1; | |
| int balance = balance_factor(node); | |
| //if the node's height is bigger than one, it means | |
| //that the tree is unbalanced to the left, so we do | |
| //right rotation or LR rotation | |
| if(balance > 1) { | |
| //if the new key is smaller than the left child's key | |
| //do a right rotation | |
| if(key < node->left->value) { | |
| return rotate_right(node); | |
| } | |
| //if not, do LR rotation | |
| else if(key > node->left->value){ | |
| return rotate_left_right(node); | |
| } | |
| } | |
| if(balance < -1) { | |
| if(key > node->right->value) { | |
| return rotate_left(node); | |
| } | |
| else if(key < node->right->value){ | |
| return rotate_right_left(node); | |
| } | |
| } | |
| return node; | |
| } | |
| Node *deleteNode(Node *node, int key) { | |
| if(node == NULL) { | |
| return node; | |
| } | |
| if(node->value > key) { | |
| node->left = deleteNode(node->left, key); | |
| } | |
| if(node->value < key) { | |
| node->right = deleteNode(node->right, key); | |
| } | |
| else { | |
| //if node is only a leaf, just remove the node | |
| //if it only has one child, change the content | |
| //of the father for the son's and delete it | |
| if(node->left == NULL || node->right == NULL) { | |
| Node *aux = node->left ? node->left : node->right; | |
| if(aux == NULL) { | |
| aux = node; | |
| node = NULL; | |
| } | |
| else | |
| *node = *aux; | |
| free(aux); | |
| } | |
| //if node has two childs | |
| //---acha o filho com menor valor da árvore a direita | |
| //---find the rightmost element of the tree | |
| //---swap its content | |
| //---removes the child | |
| else { | |
| Node *nodeWithLowestValue = getLowestNode(node->right); | |
| node->value = nodeWithLowestValue->value; | |
| node->right = deleteNode(node->right, nodeWithLowestValue->value) ; | |
| } | |
| } | |
| //recalculates the balance factor | |
| node->height = max(height(node->left), height(node->right)) + 1; | |
| int balance = balance_factor(node); | |
| if(balance > 1) { | |
| if(key < node->left->value) { | |
| return rotate_right(node); | |
| } | |
| else if(key > node->left->value){ | |
| return rotate_left_right(node); | |
| } | |
| } | |
| if(balance < -1) { | |
| if(key > node->right->value) { | |
| return rotate_left(node); | |
| } | |
| else if(key < node->right->value){ | |
| return rotate_right_left(node); | |
| } | |
| } | |
| return node; | |
| } | |
| Node* getLowestNode(Node *node) { | |
| Node *current = node; | |
| while(current->left != NULL) | |
| current = current->left; | |
| return current; | |
| } | |
| void preorder_print(Node* node){ | |
| if(node != NULL){ | |
| cout << node->value << "\n"; | |
| preorder_print(node->left); | |
| preorder_print(node->right); | |
| } | |
| } | |
| void printTree(Node *root, string indent, bool last) { | |
| if (root != nullptr) { | |
| cout << indent; | |
| if (last) { | |
| cout << "R----"; | |
| indent += " "; | |
| } else { | |
| cout << "L----"; | |
| indent += "| "; | |
| } | |
| cout << root->value << endl; | |
| printTree(root->left, indent, false); | |
| printTree(root->right, indent, true); | |
| } | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment