## DEV Community is a community of 674,199 amazing developers

We're a place where coders share, stay up-to-date and grow their careers.

# AVL Tree C++

I wanted to be a cool kid, so I did front-end, now I'm boring. Good day!

AVL Tree is a balanced binary search tree in which any two subtree height only differ by at most 1 i.e height of |Left child - Right child| <= 1. Along with key and value at each node we also store the computed Height property.

We do Rebalancing if the difference is more than 1.
AVL supports following operations:-

• Find in O(logN)
• Insert in O(logN)
• Delete in O(logN)

### Analysis of operations

`````` AVLInsert(k, R)
Insert(k, R)
N <- Find(k, R)
Rebalance(N)

Rebalancing
if |N.Left.Height - N.Right.Height| <= 1

Rebalance(N)
p <- N.Parent
if N.Left.Height > N.Right.Height + 1:
RebalanceRight(N)
if N.Right.Height > N.Left.Height + 1:
RebalanceLeft(N)
if P != null:
Rebalance(N)

N.Height <- 1 + max(N.Left.Height + N.Right.Height)
``````

### Code

The code is pretty straightforward, we will just implement the operations. It is self explanatory and pretty verbose

``````
//
//  AVLTree.h
//  Data structures
//
//  Created by Lalit Yadav on 06/09/20.
//

#ifndef AVLTree_h
#define AVLTree_h

#include <iostream>

using namespace std;

struct Node {
int data;
int height;
Node * parent;
Node * left;
Node * right;
};

typedef Node * Nodeptr;

class AVLTree {
Nodeptr root;
Nodeptr Maximum(Nodeptr node);
int GetHeight(Nodeptr node);
void ReplaceChild(Nodeptr parent, Nodeptr child, Nodeptr new_child);

void RotateLeft(Nodeptr node);
void RotateRight(Nodeptr node);

void Rebalance(Nodeptr node);
void RebalanceLeft(Nodeptr node);
void RebalanceRight(Nodeptr node);
public:
AVLTree(): root(nullptr) {}
AVLTree(int key);
bool IsEmpty();
Nodeptr Root();
Nodeptr Find(int key);
void Insert(int key);
void Delete(int key);
void PrintInOrder(Nodeptr node);
void PrintPreOrder(Nodeptr node);
};

bool AVLTree::IsEmpty() {
return root == nullptr;
}

Nodeptr AVLTree::Root() {
return root;
}

Nodeptr AVLTree::Maximum(Nodeptr node) {
if (node -> right != NULL) {
return Maximum(node -> right);
} else {
return node;
}
}

int AVLTree::GetHeight(Nodeptr node) {
if (node == nullptr)
return 0;

return node -> height;
}

Nodeptr AVLTree::Find(int key) {
if (IsEmpty()) {
return nullptr;
}

auto parent = root;

while (parent != nullptr) {
if (key > parent -> data && parent -> right != nullptr)
parent = parent -> right;
else if (key < parent -> data && parent -> left != nullptr)
parent = parent -> left;
else
return parent;
}

return parent;
}

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

void AVLTree::RotateLeft(Nodeptr node) {
auto pivot = node -> right;

// Update the parent of the node
pivot -> parent = node -> parent;
node -> parent = pivot;

// Update the child of of the updated parent
if (pivot -> parent == nullptr)
root = pivot;
else if (pivot -> parent -> left == node)
pivot -> parent -> left = pivot; // Update the child link of the parent
else
pivot -> parent -> right = pivot;

node -> right = pivot -> left;

if (pivot -> left != nullptr)
pivot -> left -> parent = node;

pivot -> left = node;

}

void AVLTree::RotateRight(Nodeptr node) {
auto pivot = node -> left;

pivot -> parent = node -> parent;
node -> parent = pivot;

if (pivot -> parent == nullptr)
root = pivot;
else if (pivot -> parent -> left == node)
pivot -> parent -> left = pivot;
else
pivot -> parent -> right = pivot;

node -> left = pivot -> right;

if (pivot -> right != nullptr)
pivot -> right -> parent = node;

pivot -> right = node;

}

void AVLTree::RebalanceLeft(Nodeptr node) {
auto right_child = node -> right;

if (right_child != nullptr) {
if (GetHeight(right_child -> left) > GetHeight(right_child -> right))
RotateRight(right_child);
}

RotateLeft(node);
}

void AVLTree::RebalanceRight(Nodeptr node) {
auto left_child = node -> left;

if (left_child != nullptr) {
if (GetHeight(left_child -> right) > GetHeight(left_child -> left))
RotateLeft(left_child);
}

RotateRight(node);
}

void AVLTree::Rebalance(Nodeptr node) {
auto parent = node -> parent;

if (GetHeight(node -> left) > GetHeight(node -> right) + 1)
RebalanceRight(node);

if (GetHeight(node -> right) > GetHeight(node -> left) + 1)
RebalanceLeft(node);

if (parent != nullptr) {
Rebalance(parent);
}
}

void AVLTree::Insert(int key) {
auto p = new Node;

p -> data = key;
p -> height = 0;
p -> parent = nullptr;
p -> left = nullptr;
p -> right = nullptr;

if (IsEmpty()) {
root = p;
} else {
auto parent = Find(key);
p -> height = 1;

if (key < parent -> data)
parent -> left = p;
else
parent -> right = p;

p -> parent = parent;
Rebalance(parent);
}
}

void AVLTree::Delete(int key) {
auto node = Find(key);

if (node == nullptr)
return;

if (node -> right == nullptr && node -> left == nullptr) {
if (node -> parent == nullptr) {
root = nullptr;
} else {
ReplaceChild(node -> parent, node, nullptr);
Rebalance(node -> parent);
}
} else if (node -> left == nullptr) {
// Replace the node with it's right child
if (node -> parent == nullptr) {
root = node -> right;
node -> right -> parent = nullptr;
Rebalance(node -> right);
} else {
ReplaceChild(node -> parent, node, node -> right);
node -> right -> parent = node -> parent;
Rebalance(node -> parent);
}
} else {
// Replace the node with the maximum key from it's left child
auto new_node = Maximum(node -> left);

if (node -> parent == nullptr) {
root = new_node;

new_node -> right = node -> right;
new_node -> left = node -> left;

Rebalance(new_node);
} else {
auto parent_new_node = new_node -> parent;
ReplaceChild(node -> parent, node, new_node);
ReplaceChild(new_node -> parent, new_node, nullptr);

new_node -> parent = node -> parent;
new_node -> left = node -> left;

if (node -> right != nullptr) {
new_node -> right = node -> right;
new_node -> right -> parent = new_node;
}

if (parent_new_node -> parent == node) {
parent_new_node -> parent = new_node;
}

Rebalance(parent_new_node);
}
}

delete node;
}

void AVLTree::ReplaceChild(Nodeptr parent, Nodeptr child, Nodeptr new_child) {
if (parent -> left == child) {
parent -> left = new_child;
} else {
parent -> right = new_child;
}
}

void AVLTree::PrintInOrder(Nodeptr node) {
if (node == nullptr)
return;

PrintInOrder(node -> left);
cout << node -> data << ' ';
PrintInOrder(node -> right);
}

void AVLTree::PrintPreOrder(Nodeptr node) {
if (node == nullptr)
return;

cout << node -> data << ' ';
PrintPreOrder(node -> left);
PrintPreOrder(node -> right);
}

#endif /* AVLTree_h */
``````