A Holistic Look At Using AVL Trees In Data Structures

// A C++ program to perform insertion in AVL tree

#include<bits/stdc++.h>

using namespace std;

// A class to create node

class Node

{

public:

int data;

Node *left;

Node *right;

int height;

};

// A function to find the maximum of two integers

int max(int x, int y);

// A function to find the height of the tree

int height(Node *n)

{

if (n == NULL)

return 0;

return n->height;

}

// Definition of max function

int max(int x, int y)

{

return (x > y)? x : y;

}

// A function that allocates a new node with the given data

Node* newnode(int data)

{

Node* newnode = new Node();

newnode->data = data;

newnode->left = NULL;

newnode->right = NULL;

newnode->height = 1; 

// A new node is initially added at leaf

return(newnode);

}

// A function to right rotate subtree rooted with b

Node *rightRotate(Node *b)

{

Node *a = b->left;

Node *t2 = a->right;

// Perform rotation

a->right = b;

b->left = t2;

// Update heights

b->height = max(height(b->left),

height(b->right)) + 1;

a->height = max(height(a->left),

height(a->right)) + 1;

// Return new root

return a;

}

// A function to left rotate subtree rooted with a

Node *leftRotate(Node *a)

{

Node *b = a->right;

Node *t2 = b->left;

// Perform rotation

b->left = a;

a->right = t2;

// Update heights

a->height = max(height(a->left),

height(a->right)) + 1;

b->height = max(height(b->left),

height(b->right)) + 1;

// Return new root

return b;

}

// A function to get Balance factor of node n

int getBalance(Node *n)

{

if (n == NULL)

return 0;

return height(n->left) - height(n->right);

}

// A function to insert the node in the AVL tree

Node* insert(Node* newnode, int data)

{

// Perform the normal BST insertion 

if (newnode == NULL)

return(newNode(data));

if (data < newnode->data)

newnode->left = insert(newnode->left, data);

else if (data > newnode->data)

newnode->right = insert(newnode->right, data);

else 

return newnode;

//Update height of this ancestor node

newnode->height = 1 + max(height(newnode->left),

height(newnode->right));

//call getbalance() to find the balance factor

int balance = getBalance(newnode);

// If this node becomes unbalanced, then

// there are 4 cases

// Left Left Case

if (balance > 1 && data < newnode->left->data)

return rightRotate(newnode);

// Right Right Case

if (balance < -1 && data > newnode->right->data)

return leftRotate(newnode);

// Left Right Case

if (balance > 1 && data > newnode->left->data)

{

newnode->left = leftRotate(newnode->left);

return rightRotate(newnode);

}

// Right Left Case

if (balance < -1 && data < newnode->right->data)

{

newnode->right = rightRotate(newnode->right);

return leftRotate(newnode);

}

/* return the (unchanged) newnode pointer */

return newnode;

}

// A function to print the AVL tree

void preOrder(Node *root)

{

if(root != NULL)

{

cout << root->data << " ";

preOrder(root->left);

preOrder(root->right);

}

}

// Driver Code

int main()

{

Node *root = NULL;

/* Constructing tree given in

the above figure */

root = insert(root, 10);

root = insert(root, 20);

root = insert(root, 30);

root = insert(root, 40);

root = insert(root, 50);

root = insert(root, 25);

/* The constructed AVL Tree would be

30

/ \

20 40

/ \ \

10 25 50

*/

cout << "Preorder traversal of the "

"constructed AVL tree is \n";

preOrder(root);

return 0;

}

// C++ program to delete a node from AVL Tree

#include<bits/stdc++.h>

using namespace std;

// An AVL tree node

class Node

{

public:

int key;

Node *left;

Node *right;

int height;

};

// A utility function to get maximum

// of two integers

int max(int a, int b);

// A utility function to get height

// of the tree

int height(Node *N)

{

if (N == NULL)

return 0;

return N->height;

}

// A utility function to get maximum

// of two integers

int max(int a, int b)

{

return (a > b)? a : b;

}

/* Helper function that allocates a

new node with the given key and

NULL left and right pointers. */

Node* newNode(int key)

{

Node* node = new Node();

node->key = key;

node->left = NULL;

node->right = NULL;

node->height = 1; // new node is initially

// added at leaf

return(node);

}

// A utility function to right

// rotate subtree rooted with y

// See the diagram given above.

Node *rightRotate(Node *y)

{

Node *x = y->left;

Node *T2 = x->right;

// Perform rotation

x->right = y;

y->left = T2;

// Update heights

y->height = max(height(y->left),

height(y->right)) + 1;

x->height = max(height(x->left),

height(x->right)) + 1;

// Return new root

return x;

}

// A utility function to left

// rotate subtree rooted with x

// See the diagram given above.

Node *leftRotate(Node *x)

{

Node *y = x->right;

Node *T2 = y->left;

// Perform rotation

y->left = x;

x->right = T2;

// Update heights

x->height = max(height(x->left),

height(x->right)) + 1;

y->height = max(height(y->left),

height(y->right)) + 1;

// Return new root

return y;

}

// Get Balance factor of node N

int getBalance(Node *N)

{

if (N == NULL)

return 0;

return height(N->left) - height(N->right);

}

Node* insert(Node* node, int key)

{

/* 1. Perform the normal BST rotation */

if (node == NULL)

return(newNode(key));

if (key < node->key)

node->left = insert(node->left, key);

else if (key > node->key)

node->right = insert(node->right, key);

else // Equal keys not allowed

return node;

/* 2. Update height of this ancestor node */

node->height = 1 + max(height(node->left),

height(node->right));

/* 3. Get the balance factor of this

ancestor node to check whether

this node became unbalanced */

int balance = getBalance(node);

// If this node becomes unbalanced,

// then there are 4 cases

// Left Left Case

if (balance > 1 && key < node->left->key)

return rightRotate(node);

// Right Right Case

if (balance < -1 && key > node->right->key)

return leftRotate(node);

// Left Right Case

if (balance > 1 && key > node->left->key)

{

node->left = leftRotate(node->left);

return rightRotate(node);

}

// Right Left Case

if (balance < -1 && key < node->right->key)

{

node->right = rightRotate(node->right);

return leftRotate(node);

}

/* return the (unchanged) node pointer */

return node;

}

/* Given a non-empty binary search tree,

return the node with the minimum key value

found in that tree. Note that the entire

tree does not need to be searched. */

Node * minValueNode(Node* node)

{

Node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)

current = current->left;

return current;

}

// Recursive function to delete a node

// with given key from subtree with

// given root. It returns root of the

// modified subtree.

Node* deleteNode(Node* root, int data)

{

// STEP 1: PERFORM STANDARD BST DELETE

if (root == NULL)

return root;

// If the data to be deleted is smaller

// than the root's data, then it lies

// in left subtree

if ( data < root->data )

root->left = deleteNode(root->left, data);

// If the data to be deleted is greater

// than the root's data, then it lies

// in right subtree

else if( data > root->data )

root->right = deleteNode(root->right, data);

else

{

if( (root->left == NULL) || (root->right == NULL) )

{

Node *temp = root->left ?

root->left :

root->right;

// No child case

if (temp == NULL)

{

temp = root;

root = NULL;

}

else // One child case

*root = *temp; // Copy the contents of

// the non-empty child

free(temp);

}

else

{

// node with two children: Get the inorder

// successor (smallest in the right subtree)

Node* temp = minValueNode(root->right);

// Copy the inorder successor's

// data to this node

root->key = temp->key;

// Delete the inorder successor

root->right = deleteNode(root->right, temp->key);

}

}

// If the tree had only one node

// then return root

if (root == NULL)

return root;

//update height of the current root

root->height = 1 + max(height(root->left),

height(root->right));

//get the balance factor of this node

int balance = getBalance(root);

// If this node becomes unbalanced,

// then there are 4 cases

// Left Left Case

if (balance > 1 &&

getBalance(root->left) >= 0)

return rightRotate(root);

// Left Right Case

if (balance > 1 &&

getBalance(root->left) < 0)

{

root->left = leftRotate(root->left);

return rightRotate(root);

}

// Right Right Case

if (balance < -1 &&

getBalance(root->right) <= 0)

return leftRotate(root);

// Right Left Case

if (balance < -1 &&

getBalance(root->right) > 0)

{

root->right = rightRotate(root->right);

return leftRotate(root);

}

return root;

}

// A utility function to print preorder

// traversal of the tree.

// The function also prints height

// of every node

void preOrder(Node *root)

{

if(root != NULL)

{

cout << root->key << " ";

preOrder(root->left);

preOrder(root->right);

}

}

// Driver Code

int main()

{

Node *root = NULL;

/* Constructing tree given in

the above figure */

root = insert(root, 9);

root = insert(root, 5);

root = insert(root, 10);

root = insert(root, 0);

root = insert(root, 6);

root = insert(root, 11);

root = insert(root, -1);

root = insert(root, 1);

root = insert(root, 2);

/* The constructed AVL Tree would be

9

/ \

1 10

/ \ \

0 5 11

/ / \

-1 2 6

*/

cout << "constructed AVL tree is \n";

preOrder(root);

root = deleteNode(root, 10);

/* The AVL Tree after deletion of 10

1

/ \

0 9

/ / \

-1 5 11

/ \

2 6

*/

cout << "\nModified AVL Tree after deletion of 10 \n";

preOrder(root);

return 0;

}