Algorithm
An AVL tree (Adelson-Velsky and Landis tree) is a self-balancing binary search tree. In a binary search tree, each node has at most two children, and for each node, all elements in its left subtree are less than the node, and all elements in its right subtree are greater than the node.
The balance property of an AVL tree is that the height difference between the left and right subtrees of any node (called the balance factor) is either -1, 0, or 1. If, at any time during an insertion or deletion operation, this balance property is violated, the tree is rebalanced to restore it.
Here are some key points about AVL trees:
-
Balancing Factor: The balance factor of a node is calculated as the difference between the height of the left subtree and the height of the right subtree.
-
Rotations: There are four possible rotations to maintain the balance of the AVL tree:
- Left-Left Rotation (LL)
- Right-Right Rotation (RR)
- Left-Right Rotation (LR)
- Right-Left Rotation (RL)
-
Insertion: When a new element is inserted into an AVL tree, the tree may become unbalanced. To restore balance, rotations are performed as needed.
-
Deletion: When an element is deleted from an AVL tree, the tree may also become unbalanced. Similar to insertion, rotations are performed to maintain the balance.
-
Complexity: The AVL tree ensures that the height of the tree is logarithmic in the number of nodes, which guarantees efficient search, insertion, and deletion operations. The time complexity for these operations is O(log n), where n is the number of nodes in the tree.
AVL trees are widely used in situations where efficient searching, insertion, and deletion operations are required and where the data set is dynamic, meaning that elements are frequently added or removed. They are an example of a self-balancing binary search tree, and there are other variations with similar goals, such as red-black trees.
Code Examples
#1 AVL Tree implement in Python
Code -
Python Programming
class Node:
def __init__(self, key):
self.key = key
self.left = None
self.right = None
self.height = 1
class AVLTree:
def getHeight(self, node):
if not node:
return 0
return node.height
def getBalance(self, node):
if not node:
return 0
return self.getHeight(node.left) - self.getHeight(node.right)
def rotateRight(self, y):
x = y.left
T2 = x.right
x.right = y
y.left = T2
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
return x
def rotateLeft(self, x):
y = x.right
T2 = y.left
y.left = x
x.right = T2
x.height = 1 + max(self.getHeight(x.left), self.getHeight(x.right))
y.height = 1 + max(self.getHeight(y.left), self.getHeight(y.right))
return y
def insert(self, root, key):
if not root:
return Node(key)
if key < root.key:
root.left = self.insert(root.left, key)
elif key > root.key:
root.right = self.insert(root.right, key)
else:
return root # Duplicate keys are not allowed
root.height = 1 + max(self.getHeight(root.left), self.getHeight(root.right))
balance = self.getBalance(root)
# Left Heavy
if balance > 1:
if key < root.left.key:
return self.rotateRight(root)
else:
root.left = self.rotateLeft(root.left)
return self.rotateRight(root)
# Right Heavy
if balance < -1:
if key > root.right.key:
return self.rotateLeft(root)
else:
root.right = self.rotateRight(root.right)
return self.rotateLeft(root)
return root
def insertKey(self, key):
self.root = self.insert(self.root, key)
def preOrder(self, root):
if not root:
return
print("{0} ".format(root.key), end="")
self.preOrder(root.left)
self.preOrder(root.right)
if __name__ == "__main__":
avl_tree = AVLTree()
keys = [10, 20, 30, 40, 50, 25]
for key in keys:
avl_tree.insertKey(key)
print("Preorder traversal of AVL tree:")
avl_tree.preOrder(avl_tree.root)
#2 AVL Tree implement in Java
Code -
Java Programming
class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
class AVLTree {
Node root;
// Get height of a node
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
// Get the balance factor of a node
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.left) - height(N.right);
}
// Right rotate subtree rooted with y
Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
// Perform rotation
x.right = y;
y.left = T2;
// Update heights
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
// Return new root
return x;
}
// Left rotate subtree rooted with x
Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
// Perform rotation
y.left = x;
x.right = T2;
// Update heights
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
// Return new root
return y;
}
// Insert a key into the tree
Node insert(Node node, int key) {
// Perform normal BST insertion
if (node == null)
return (new Node(key));
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else // Duplicate keys are not allowed
return node;
// Update height of current node
node.height = 1 + Math.max(height(node.left), height(node.right));
// Get the balance factor of this ancestor node to check whether this node became unbalanced
int balance = getBalance(node);
// 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;
}
// Preorder traversal of the tree
void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
/* Constructing tree given in the above figure */
tree.root = tree.insert(tree.root, 10);
tree.root = tree.insert(tree.root, 20);
tree.root = tree.insert(tree.root, 30);
tree.root = tree.insert(tree.root, 40);
tree.root = tree.insert(tree.root, 50);
tree.root = tree.insert(tree.root, 25);
/* The constructed AVL Tree would be
30
/ \
20 40
/ \ \
10 25 50
*/
System.out.println("Preorder traversal" + " of the constructed tree is:");
tree.preOrder(tree.root);
}
}
#3 AVL Tree implement in C
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
// Node structure for AVL tree
struct Node {
int key;
struct Node *left;
struct Node *right;
int height;
};
// Function to get the height of a node
int height(struct Node *node) {
if (node == NULL)
return 0;
return node->height;
}
// Function to get the maximum of two integers
int max(int a, int b) {
return (a > b) ? a : b;
}
// Function to create a new node with a given key
struct Node* newNode(int key) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // New node is initially at height 1
return node;
}
// Function to right rotate a subtree rooted with y
struct Node* rightRotate(struct Node *y) {
struct Node *x = y->left;
struct 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;
}
// Function to left rotate a subtree rooted with x
struct Node* leftRotate(struct Node *x) {
struct Node *y = x->right;
struct 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 a node
int getBalance(struct Node *node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// Function to insert a key into the AVL tree
struct Node* insert(struct Node *node, int key) {
// Perform standard BST insert
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 // Duplicate keys not allowed
return node;
// Update height of current node
node->height = 1 + max(height(node->left), height(node->right));
// Get the balance factor to check if the node became unbalanced
int balance = getBalance(node);
// 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);
}
// If the node is balanced, return the unchanged node
return node;
}
// Function to print the inorder traversal of the tree
void inOrder(struct Node *root) {
if (root != NULL) {
inOrder(root->left);
printf("%d ", root->key);
inOrder(root->right);
}
}
// Driver program to test the AVL tree functions
int main() {
struct 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);
printf("Inorder traversal of the constructed AVL tree: \n");
inOrder(root);
return 0;
}
#4 AVL Tree implement in C++
Code -
C++ Programming
#include <iostream>
#include <algorithm>
class AVLTree {
private:
struct Node {
int key;
int height;
Node* left;
Node* right;
Node(int k) : key(k), height(1), left(nullptr), right(nullptr) {}
};
Node* root;
int height(Node* node) {
if (node == nullptr) {
return 0;
}
return node->height;
}
int balanceFactor(Node* node) {
if (node == nullptr) {
return 0;
}
return height(node->left) - height(node->right);
}
void updateHeight(Node* node) {
if (node != nullptr) {
node->height = 1 + std::max(height(node->left), height(node->right));
}
}
Node* rotateRight(Node* y) {
Node* x = y->left;
Node* T2 = x->right;
x->right = y;
y->left = T2;
updateHeight(y);
updateHeight(x);
return x;
}
Node* rotateLeft(Node* x) {
Node* y = x->right;
Node* T2 = y->left;
y->left = x;
x->right = T2;
updateHeight(x);
updateHeight(y);
return y;
}
Node* insert(Node* node, int key) {
if (node == nullptr) {
return new Node(key);
}
if (key < node->key) {
node->left = insert(node->left, key);
} else if (key > node->key) {
node->right = insert(node->right, key);
} else {
// Duplicate keys are not allowed in this example
return node;
}
updateHeight(node);
int bf = balanceFactor(node);
// Left Heavy
if (bf > 1) {
if (key < node->left->key) {
// Left-Left case
return rotateRight(node);
} else {
// Left-Right case
node->left = rotateLeft(node->left);
return rotateRight(node);
}
}
// Right Heavy
if (bf < -1) {
if (key > node->right->key) {
// Right-Right case
return rotateLeft(node);
} else {
// Right-Left case
node->right = rotateRight(node->right);
return rotateLeft(node);
}
}
return node;
}
void inorderTraversal(Node* node) {
if (node != nullptr) {
inorderTraversal(node->left);
std::cout << node->key << " ";
inorderTraversal(node->right);
}
}
public:
AVLTree() : root(nullptr) {}
void insert(int key) {
root = insert(root, key);
}
void inorderTraversal() {
inorderTraversal(root);
std::cout << std::endl;
}
};
int main() {
AVLTree avlTree;
avlTree.insert(10);
avlTree.insert(20);
avlTree.insert(30);
std::cout << "Inorder Traversal of AVL Tree: ";
avlTree.inorderTraversal();
return 0;
}
Demonstration
AVL Tree-DevsEnv