ASSIGNMENT NO #3

TOPIC: AVL TREES

Submitted By
Areeba Noor 22-Arid-4353
Ayesha Fayaz 22-Arid-4354
Khansa Rehman 22-Arid-4368
Mahnoor Nadeem 22-Arid-4369

Submitted To

Sir Ashar

Submission Date: 15-January-2024

Gujrat Institute of Management Sciences

PMAS-Arid Agriculture University, Rawalpindi

1
AVL Tree Data Structure
An AVL tree defined as a self-balancing Binary Search Tree (BST) where the
difference between heights of left and right subtrees for any node cannot be
more than one.
The difference between the heights of the left subtree and the right subtree for any
node is known as the balance factor of the node.
The AVL tree is named after its inventors, Georgy Adelson-Velsky and Evgenii
Landis, who published it in their 1962 paper “An algorithm for the organization of
information”.

Examples Of AVL Trees

The above tree is AVL because the differences between the heights of left and right
subtrees for every node are less than or equal to 1.

2
Operations On AVL Trees
 Insertion
 Deletion
 Selection[ It is similar to performing a search in BST]

Insertion in AVL Tree:

#include<iostream>
using namespace std;
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b)
{
return (a > b)? a : b;
}
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
return(node);
}
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
x->right = y;
y->left = T2;

y->height = max(height(y->left),
height(y->right)) + 1;

3
 x->height = max(height(x->left),
height(x->right)) + 1;
return x;
}

Node *leftRotate(Node *x)

{
Node *y = x->right;
Node *T2 = y->left;

y->left = x;
x->right = T2;

x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;

return y;
}

int getBalance(Node *N)

{
if (N == NULL)
return 0;
return height(N->left) - height(N->right);
}

Node* insert(Node* node, int key)

{
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
return node;
node->height = 1 + max(height(node->left), height(node->right));

int balance = getBalance(node);

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

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

return leftRotate(node);
if (balance > 1 && key > node->left->key)
{

4
 node->left = leftRotate(node->left);
return rightRotate(node);
}

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

{
node->right = rightRotate(node->right);
return leftRotate(node);
}

return node;
}

void preOrder(Node *root)

{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}

int main()
{
Node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);

cout << "Preorder traversal of the " "constructed AVL tree is \n";
preOrder(root);
return 0;
}

Output
Preorder traversal of the constructed AVL tree is
30 20 10 25 40 50

Time Complexity: O(log(n)), For Insertion

Auxiliary Space: O(1)

Deletion in an AVL Tree

5
#include<iostream>
using namespace std;
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};

int max(int a, int b);

int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}

int max(int a, int b)

{
return (a > b)? a : b;
}

Node* newNode(int key)

{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1;
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

6
// 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;

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

int balance = getBalance(node);

// Left Left Case

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

// Right Right Case

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

Node * minValueNode(Node* node)

{
Node* current = node;

/* loop down to find the leftmost leaf */

while (current->left != NULL)
current = current->left;
return current;
}

Node* deleteNode(Node* root, int key)

{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;

if ( key < root->key )

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

else if( key > root->key )

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

else
{
// node with only one child or no child
if( (root->left == NULL) | |(root->right == NULL) )

8
 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* temp = minValueNode(root->right);

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

}
}

if (root == NULL)
return root;
root->height = 1 + max(height(root->left), height(root->right));

int balance = getBalance(root);

// 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

9
 if (balance < -1 &&
getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}

return root;
}

void preOrder(Node *root)

{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}

int main()
{
Node *root = NULL;

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

cout << "Preorder traversal of the" "constructed AVL tree is \n";

preOrder(root);
root = deleteNode(root, 10);
cout << "\nPreorder traversal after"<< " deletion of 10 \n";
preOrder(root);
return 0;
}

Output
Preorder traversal of the constructed AVL tree is
9 1 0 -1 5 2 6 10 11
Preorder traversal after deletion of 10
1 0 -1 9 5 2 6 11

10
Time Complexity:
The rotation operations (left and right rotate) take constant time as only few pointers
are being changed there. Updating the height and getting the balance factor also take
constant time. So the time complexity of AVL delete remains same as BST delete
which is O(h) where h is height of the tree. Since AVL tree is balanced, the height is
O(Logn). So time complexity of AVL delete is O(Log n).
Auxiliary Space: O(1), since no extra space is used.

Searching in Avl Trees

#include <iostream>
using namespace std;

class BST {
private:
struct node {
int key;
struct node* left, *right;
};
struct node* root;
struct node* newNode(int item) {
struct node* temp = new struct node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}

struct node* insert(struct node* node, int key) {

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

struct node* search(struct node* root, int key) {

if (root == NULL || root->key == key)
return root;

if (root->key < key)

return search(root->right, key);
return search(root->left, key);
}

11
public:
BST() : root(NULL) {}

void insert(int key) {

root = insert(root, key);
}

bool search(int key) {

return search(root, key) != NULL;
}
};

int main() {
BST bst;

// Taking input for keys to be inserted

int numKeys;
cout << "Enter the number of keys to be inserted: ";
cin >> numKeys;

cout << "Enter the keys to be inserted:\n";

for (int i = 0; i < numKeys; ++i) {
int key;
cin >> key;
bst.insert(key);
}

// Taking input for keys to be searched

int numSearchKeys;
cout << "Enter the number of keys to be searched: ";
cin >> numSearchKeys;

cout << "Enter the keys to be searched:\n";

for (int i = 0; i < numSearchKeys; ++i) {
int key;
cin >> key;

// Searching in a BST
if (!bst.search(key))
cout << key << " not found" << endl;
else
cout << key << " found" << endl;
}

return 0;
}

12
Output
Enter the number of keys to be inserted:
5
Enter the keys to be inserted:
24
25
26
27
28
Enter the number of keys to be searched: 3
Enter the keys to be searched:
28
28 found
25
25 found
27
27 found

Time Complexity: O(log N), where N is the number of nodes of the tree
Auxiliary Space: O(1)

13