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)
AdjustHeight(N)
if P != null:
Rebalance(N)
AdjustHeight(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.
// Copyright © 2020 Lalit Yadav. All rights reserved.
//
#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 AdjustHeight(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;
}
void AVLTree::AdjustHeight(Nodeptr node) {
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;
AdjustHeight(node);
AdjustHeight(pivot);
}
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;
AdjustHeight(node);
AdjustHeight(pivot);
}
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);
AdjustHeight(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 */
Top comments (0)