Created
October 18, 2014 11:11
-
-
Save harish-r/097688ac7f48bcbadfa5 to your computer and use it in GitHub Desktop.
AVL Tree Implementation in C++. Self Balancing Tree
This file contains hidden or 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
| /* AVL Tree Implementation in C++ */ | |
| /* Harish R */ | |
| #include<iostream> | |
| using namespace std; | |
| class BST | |
| { | |
| struct node | |
| { | |
| int data; | |
| node* left; | |
| node* right; | |
| int height; | |
| }; | |
| node* root; | |
| void makeEmpty(node* t) | |
| { | |
| if(t == NULL) | |
| return; | |
| makeEmpty(t->left); | |
| makeEmpty(t->right); | |
| delete t; | |
| } | |
| node* insert(int x, node* t) | |
| { | |
| if(t == NULL) | |
| { | |
| t = new node; | |
| t->data = x; | |
| t->height = 0; | |
| t->left = t->right = NULL; | |
| } | |
| else if(x < t->data) | |
| { | |
| t->left = insert(x, t->left); | |
| if(height(t->left) - height(t->right) == 2) | |
| { | |
| if(x < t->left->data) | |
| t = singleRightRotate(t); | |
| else | |
| t = doubleRightRotate(t); | |
| } | |
| } | |
| else if(x > t->data) | |
| { | |
| t->right = insert(x, t->right); | |
| if(height(t->right) - height(t->left) == 2) | |
| { | |
| if(x > t->right->data) | |
| t = singleLeftRotate(t); | |
| else | |
| t = doubleLeftRotate(t); | |
| } | |
| } | |
| t->height = max(height(t->left), height(t->right))+1; | |
| return t; | |
| } | |
| node* singleRightRotate(node* &t) | |
| { | |
| node* u = t->left; | |
| t->left = u->right; | |
| u->right = t; | |
| t->height = max(height(t->left), height(t->right))+1; | |
| u->height = max(height(u->left), t->height)+1; | |
| return u; | |
| } | |
| node* singleLeftRotate(node* &t) | |
| { | |
| node* u = t->right; | |
| t->right = u->left; | |
| u->left = t; | |
| t->height = max(height(t->left), height(t->right))+1; | |
| u->height = max(height(t->right), t->height)+1 ; | |
| return u; | |
| } | |
| node* doubleLeftRotate(node* &t) | |
| { | |
| t->right = singleRightRotate(t->right); | |
| return singleLeftRotate(t); | |
| } | |
| node* doubleRightRotate(node* &t) | |
| { | |
| t->left = singleLeftRotate(t->left); | |
| return singleRightRotate(t); | |
| } | |
| node* findMin(node* t) | |
| { | |
| if(t == NULL) | |
| return NULL; | |
| else if(t->left == NULL) | |
| return t; | |
| else | |
| return findMin(t->left); | |
| } | |
| node* findMax(node* t) | |
| { | |
| if(t == NULL) | |
| return NULL; | |
| else if(t->right == NULL) | |
| return t; | |
| else | |
| return findMax(t->right); | |
| } | |
| node* remove(int x, node* t) | |
| { | |
| node* temp; | |
| // Element not found | |
| if(t == NULL) | |
| return NULL; | |
| // Searching for element | |
| else if(x < t->data) | |
| t->left = remove(x, t->left); | |
| else if(x > t->data) | |
| t->right = remove(x, t->right); | |
| // Element found | |
| // With 2 children | |
| else if(t->left && t->right) | |
| { | |
| temp = findMin(t->right); | |
| t->data = temp->data; | |
| t->right = remove(t->data, t->right); | |
| } | |
| // With one or zero child | |
| else | |
| { | |
| temp = t; | |
| if(t->left == NULL) | |
| t = t->right; | |
| else if(t->right == NULL) | |
| t = t->left; | |
| delete temp; | |
| } | |
| if(t == NULL) | |
| return t; | |
| t->height = max(height(t->left), height(t->right))+1; | |
| // If node is unbalanced | |
| // If left node is deleted, right case | |
| if(height(t->left) - height(t->right) == 2) | |
| { | |
| // right right case | |
| if(height(t->left->left) - height(t->left->right) == 1) | |
| return singleLeftRotate(t); | |
| // right left case | |
| else | |
| return doubleLeftRotate(t); | |
| } | |
| // If right node is deleted, left case | |
| else if(height(t->right) - height(t->left) == 2) | |
| { | |
| // left left case | |
| if(height(t->right->right) - height(t->right->left) == 1) | |
| return singleRightRotate(t); | |
| // left right case | |
| else | |
| return doubleRightRotate(t); | |
| } | |
| return t; | |
| } | |
| int height(node* t) | |
| { | |
| return (t == NULL ? -1 : t->height); | |
| } | |
| int getBalance(node* t) | |
| { | |
| if(t == NULL) | |
| return 0; | |
| else | |
| return height(t->left) - height(t->right); | |
| } | |
| void inorder(node* t) | |
| { | |
| if(t == NULL) | |
| return; | |
| inorder(t->left); | |
| cout << t->data << " "; | |
| inorder(t->right); | |
| } | |
| public: | |
| BST() | |
| { | |
| root = NULL; | |
| } | |
| void insert(int x) | |
| { | |
| root = insert(x, root); | |
| } | |
| void remove(int x) | |
| { | |
| root = remove(x, root); | |
| } | |
| void display() | |
| { | |
| inorder(root); | |
| cout << endl; | |
| } | |
| }; | |
| int main() | |
| { | |
| BST t; | |
| t.insert(20); | |
| t.insert(25); | |
| t.insert(15); | |
| t.insert(10); | |
| t.insert(30); | |
| t.insert(5); | |
| t.insert(35); | |
| t.insert(67); | |
| t.insert(43); | |
| t.insert(21); | |
| t.insert(10); | |
| t.insert(89); | |
| t.insert(38); | |
| t.insert(69); | |
| t.display(); | |
| t.remove(5); | |
| t.remove(35); | |
| t.remove(65); | |
| t.remove(89); | |
| t.remove(43); | |
| t.remove(88); | |
| t.remove(20); | |
| t.remove(38); | |
| t.display(); | |
| } |
add the criterion for that.
...
else if( x == t->data) return t;
...
I referred to this project and re-implemented AVLTree. Thanks @harish-r!
AVLTree-CPP
Inorder display isn't working, we can print each node by storing it, why is that?
something like this is missing , is it ?
1.) Add
int max(int left,int right)
{
return (left >= right) ? left : right;
}
and :
2.) change
class BST
{
public:
and : cout << t->data << " ";
inorder(t->right);
}
- change
//public:
BST()
{
root = NULL;
}
Does anyone knows how to update the AVL tree using Linked List?
AVL Tree Implementation in C++ from : https://atechdaily.com/posts/AVL-Tree-Implementation-in-Cplusplus
man this doesnt work i get SIGSEG when trying this:
BST t;
t.insert(5);
t.insert(3);
t.insert(7);
t.insert(10);
t.insert(12);
t.remove(3);
t.insert(11);
t.insert(13);
t.display();
rotations in remove function for bf == -2 and bf == 2 should be opposite
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
Insert function there is not a criterion such as insert node key already exist what to do?