Skip to content

Instantly share code, notes, and snippets.

@harish-r
Created October 18, 2014 11:11
Show Gist options
  • Save harish-r/097688ac7f48bcbadfa5 to your computer and use it in GitHub Desktop.
Save harish-r/097688ac7f48bcbadfa5 to your computer and use it in GitHub Desktop.
AVL Tree Implementation in C++. Self Balancing Tree
/* 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();
}
@vvtatarskii
Copy link

Insert numbers from 1 to 9 (first 1, then 2, and so on). Remove 4. Thank me later.

got the same error (not 1 to 9 - real case, but inserted nine numbers and removed fourth).

Do you have the solution?

@nvnrdhn
Copy link

nvnrdhn commented Feb 4, 2019

Insert numbers from 1 to 9 (first 1, then 2, and so on). Remove 4. Thank me later.

got the same error (not 1 to 9 - real case, but inserted nine numbers and removed fourth).

Do you have the solution?

In the node* remove function, this:

        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);
        }

should be:

        if(height(t->left) - height(t->right) == -2)
        {
            // right right case
            if(height(t->right->right) - height(t->right->left) == 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->left->left) - height(t->left->right) == 1){
                return singleRightRotate(t);
            }
            // left right case
            else
                return doubleRightRotate(t);
        }

CMIIW.

@buzz-95
Copy link

buzz-95 commented Apr 25, 2019

The code has a error, Try insert : 10, 20, 5, 8, 3 and then remove 10, it gives a segmentation fault, Please recttify it!

@alielzei
Copy link

nice

@knasiotis
Copy link

knasiotis commented Jun 19, 2019

Even with @nvnrdhn 's correction it doesn't work. (I mean there is an extra problem)
Try this:

    BST t;
    int array[]={100,55,50,45,47,70,80,78,77,79,82,81,83,150,140,
    135,142,143,180,170,165,160,175,173,200,190,195,500,1000,1500,2000,3000,4000,5000,6000,7000,8000,9000};

    for(int i=0;i<38;i++){
          t.insert(array[i]);
    }
    cout << "insertion done" << endl;

    t.remove(45);
    t.remove(47);
    t.remove(50);
    t.remove(55);
    t.remove(70);
    t.remove(77);
    t.remove(78);
    t.remove(79);
    t.remove(80);
    t.remove(81);
    t.remove(82);
    t.remove(83);
    t.remove(100);
    t.remove(135);
    cout << "Now I remove 140" << endl;
    t.remove(140);

Enjoy segfault.

With a gdb backtrace the problem is shown to be in

Program received signal SIGSEGV, Segmentation fault.
0x0000555555555546 in BST::singleRightRotate(BST::node*&) ()
(gdb) backtrace
#0  0x0000555555555546 in BST::singleRightRotate(BST::node*&) ()
#1  0x000055555555575a in BST::doubleLeftRotate(BST::node*&) ()
#2  0x0000555555555b81 in BST::remove(int, BST::node*) ()
#3  0x0000555555555948 in BST::remove(int, BST::node*) ()
#4  0x0000555555555948 in BST::remove(int, BST::node*) ()
#5  0x000055555555648f in BST::remove(int) ()
#6  0x0000555555557026 in main ()

UPDATE: If you change the singleRightRotate(node* &t) and singleLeftRotate(node* &t) to each respectively, it seems to be working fine. I will make another update if I encounter an error.

       node* singleRightRotate(node* &t)
	{
		if (t->left != NULL) {
			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;
		}
		return t;
	}
	node* singleLeftRotate(node* &t)
	{
            if (t->right != NULL) {
		    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;
            }
            return t;
	}

@zengqingfa
Copy link

Insert function there is not a criterion such as insert node key already exist what to do?

@developer0hye
Copy link

developer0hye commented Nov 16, 2019

@zengqingfa

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

Copy link

ghost commented Nov 28, 2019

Inorder display isn't working, we can print each node by storing it, why is that?

@Henner365
Copy link

Henner365 commented May 12, 2020

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);

}
  1. change

//public:

BST()

{

    root = NULL;

}

@Junaid-byte
Copy link

Does anyone knows how to update the AVL tree using Linked List?

@Hrishikesh2900
Copy link

@hkovacevic2
Copy link

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();

@Ekagra
Copy link

Ekagra commented May 25, 2022

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