AVL Tree in Data Structures with Examples
21 Sep 2023
Advanced
327 Views
AVL Tree in Data Structures: An Overview
Are you interested in learning more about data structures? If so, then you're in luck! Today we'll be discussing a powerful yet complex type of data structure known as an AVL Tree. AVL Tree Structures are used to store and organize data, allowing for efficient retrieval and insertion operations. By understanding how this structure works, you can use it to create solutions to problems that involve sorting and retrieving large amounts of varying types of data quickly. You'll understand the basics of trees as well as AVL Tree in Data Structures with examples today, along with the main algorithms for applying them to your chosen programming language.
What is AVL tree in data structures?
AVL tree in data structures is a popular self-balancing binary search tree in data structures. It was introduced by Georgy Adelson-Velsky and Evgenii Landis in 1962, hence the name AVL. With a maximum depth of log2n, AVL trees automatically balance themselves to ensure effective search operations. They are essential for programmers and computer science students learning complex data structures and algorithms since they have several applications, including database indexing, language translation, and file systems.
AVL Tree Rotation
AVL tree rotation is a fundamental operation used in self-balancing binary search trees, specifically in AVL trees. AVL trees are binary search trees that maintain balance by ensuring that the heights of the left and right subtrees of any node differ by at most one. When a node is inserted or deleted from an AVL tree and this balance condition is violated, rotations are performed to restore balance.
There are four types of AVL rotations:
AVL tree Left Rotation (LL Rotation):
In a left rotation, a node's right child becomes the new root, while the original node becomes the left child of the new root. The left child of the new root becomes the right child of the original node.
Example:
AVL tree Right Rotation (RR Rotation):
In a right rotation, a node's left child becomes the new root, while the original node becomes the right child of the new root. The right child of the new root becomes the left child of the original node.
Example:
Left right rotation in AVL tree (LR Rotation):
An LR rotation is a combination of a left rotation followed by a right rotation. It is performed when the left subtree of a node is unbalanced to the right, and the right subtree of the left child of that node is unbalanced to the left.
Example:
Right left rotation AVL tree (RL Rotation):
An RL rotation is a combination of a right rotation followed by a left rotation. It is performed when the right subtree of a node is unbalanced to the left, and the left subtree of the right child of that node is unbalanced to the right.
Example:
Basic operations of AVL tree
- Insertion: When inserting a new node into an AVL tree, it follows the same process as a binary search tree. After inserting the node, the tree may become unbalanced, violating the AVL property. You need to perform one or more rotations on the affected nodes to restore balance.
- Deletion: Deletion in an AVL tree also follows the same process as a binary search tree. After deleting a node, the tree may become unbalanced. Similar to insertion, you need to perform rotations to maintain the AVL property.
- Rotations: Rotations are the fundamental operations in AVL trees for maintaining balance. There are four types of rotations: left rotation, right rotation, left-right rotation (also known as LR rotation), and right-left rotation (also known as RL rotation). Rotations are performed on specific nodes to adjust the balance factor and restore the AVL property. Rotations preserve the binary search tree ordering while adjusting the heights of the nodes.
- Balancing Factor: Each node in an AVL tree has a balance factor associated with it. The balance factor is the difference between the heights of the left and right subtrees of a node. It can be -1, 0, or 1, indicating whether the tree is balanced or which side is heavier. When a node's balance factor exceeds these values, it means the tree is unbalanced and requires rotations to restore balance.
- Height Update: During insertion or deletion, the height of the affected nodes must be recalculated to update the tree's structure. The height of a node is the length of the longest path from that node to a leaf. After performing rotations, the measurements of the affected nodes are adjusted accordingly.
- Searching: AVL trees support efficient searching operations. You can search for a specific key in an AVL tree by comparing the key with the values in the nodes and traversing the tree accordingly, similar to a binary search tree.
AVL tree insertion algorithm
- Start by performing a standard binary search tree insertion. Compare the value of the new node to be inserted with the value of the current node. If the value is less than the current node, move to the left subtree; if it is more significant, move to the right subtree.
- Recursively insert the new node into the appropriate subtree. If the subtree is empty, simply insert the new node at that position.
- After inserting the new node, update the balance factor of each node on the insertion path from the root to the newly inserted node. Calculate the balance factor by subtracting the height of the right subtree from the height of the left subtree.
- If the balance factor of any node becomes greater than 1 or less than -1, it indicates that the tree is unbalanced at that node.
- To restore balance, perform the appropriate rotations. There are four possible cases to consider, depending on the balance factor of the node and its children:
- Left-Left (LL) Case: If the balance factor of the node is greater than 1 and the balance factor of its left child is also greater than or equal to 0, perform a right rotation on the unbalanced node.
- Left-Right (LR) Case: If the balance factor of the node is greater than 1 and the balance factor of its left child is less than 0, perform a left rotation on the left child followed by a right rotation on the unbalanced node.
- Right-Right (RR) Case: If the balance factor of the node is less than -1 and the balance factor of its right child is less than or equal to 0, perform a left rotation on the unbalanced node.
- Right-Left (RL) Case: If the balance factor of the node is less than -1 and the balance factor of its right child is greater than 0, perform a right rotation on the right child followed by a left rotation on the unbalanced node.
- After performing the rotations, update the balance factors of the affected nodes.
- Repeat steps 4 to 6 until the balance is restored for all the nodes on the insertion path.
- Finally, return the root of the updated AVL tree
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
self.height = 1
def max(a, b):
return a if (a > b) else b
def height(N):
if N is None:
return 0
return N.height
def newNode(data):
node = Node(data)
node.leftChild = None
node.rightChild = None
node.height = 1
return node
def rightRotate(y):
x = y.leftChild
T2 = x.rightChild
x.rightChild = y
y.leftChild = T2
y.height = max(height(y.leftChild), height(y.rightChild)) + 1
x.height = max(height(x.leftChild), height(x.rightChild)) + 1
return x
def leftRotate(x):
y = x.rightChild
T2 = y.leftChild
y.leftChild = x
x.rightChild = T2
x.height = max(height(x.leftChild), height(x.rightChild)) + 1
y.height = max(height(y.leftChild), height(y.rightChild)) + 1
return y
def getBalance(N):
if N is None:
return 0
return height(N.leftChild) - height(N.rightChild)
def insertNode(node, data):
if node is None:
return newNode(data)
if data < node.data:
node.leftChild = insertNode(node.leftChild, data)
elif data > node.data:
node.rightChild = insertNode(node.rightChild, data)
else:
return node
node.height = 1 + max(height(node.leftChild), height(node.rightChild))
balance = getBalance(node)
if balance > 1 and data < node.leftChild.data:
return rightRotate(node)
if balance < -1 and data > node.rightChild.data:
return leftRotate(node)
if balance > 1 and data > node.leftChild.data:
node.leftChild = leftRotate(node.leftChild)
return rightRotate(node)
if balance < -1 and data < node.rightChild.data:
node.rightChild = rightRotate(node.rightChild)
return leftRotate(node)
return node
def minValueNode(node):
current = node
while current.leftChild is not None:
current = current.leftChild
return current
def printTree(root):
if root is None:
return
printTree(root.leftChild)
print(root.data, end=" ")
printTree(root.rightChild)
root = None
root = insertNode(root, 22)
root = insertNode(root, 14)
root = insertNode(root, 72)
root = insertNode(root, 44)
root = insertNode(root, 25)
root = insertNode(root, 63)
root = insertNode(root, 98)
print("AVL Tree: ", end="")
printTree(root)
class Node {
int data;
Node leftChild;
Node rightChild;
int height;
Node(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.height = 1;
}
}
class AVLTree {
Node root;
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
Node rightRotate(Node y) {
Node x = y.leftChild;
Node T2 = x.rightChild;
x.rightChild = y;
y.leftChild = T2;
y.height = max(height(y.leftChild), height(y.rightChild)) + 1;
x.height = max(height(x.leftChild), height(x.rightChild)) + 1;
return x;
}
Node leftRotate(Node x) {
Node y = x.rightChild;
Node T2 = y.leftChild;
y.leftChild = x;
x.rightChild = T2;
x.height = max(height(x.leftChild), height(x.rightChild)) + 1;
y.height = max(height(y.leftChild), height(y.rightChild)) + 1;
return y;
}
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.leftChild) - height(N.rightChild);
}
Node insertNode(Node node, int data) {
if (node == null)
return new Node(data);
if (data < node.data)
node.leftChild = insertNode(node.leftChild, data);
else if (data > node.data)
node.rightChild = insertNode(node.rightChild, data);
else
return node;
node.height = 1 + max(height(node.leftChild), height(node.rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node.leftChild.data)
return rightRotate(node);
if (balance < -1 && data > node.rightChild.data)
return leftRotate(node);
if (balance > 1 && data > node.leftChild.data) {
node.leftChild = leftRotate(node.leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node.rightChild.data) {
node.rightChild = rightRotate(node.rightChild);
return leftRotate(node);
}
return node;
}
Node minValueNode(Node node) {
Node current = node;
while (current.leftChild != null)
current = current.leftChild;
return current;
}
void printTree(Node root) {
if (root == null)
return;
printTree(root.leftChild);
System.out.print(root.data + " ");
printTree(root.rightChild);
}
}
public class Main {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insertNode(tree.root, 22);
tree.root = tree.insertNode(tree.root, 14);
tree.root = tree.insertNode(tree.root, 72);
tree.root = tree.insertNode(tree.root, 44);
tree.root = tree.insertNode(tree.root, 25);
tree.root = tree.insertNode(tree.root, 63);
tree.root = tree.insertNode(tree.root, 98);
System.out.print("AVL Tree: ");
tree.printTree(tree.root);
}
}
#include <iostream>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
void printTree(struct Node *root){
if (root == NULL)
return;
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->leftChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
return 0;
}This code defines an AVL tree, applies various operations to it, such as rotation and insertion, and then prints the finished AVL tree.
Output
>AVL Tree: 14 22 14 44 14 22 14
AVL tree deletion algorithm
- Start by performing a standard binary search to find the node that needs to be deleted from the AVL tree. If the node is not found, the deletion operation terminates. Once the node is found, there are three cases to consider:
- Case 1: The node has no children (it is a leaf node). In this case, simply remove the node from the tree. The tree remains balanced since removing a leaf node does not affect the heights of other nodes.
- Case 2: The node has one child. In this case, replace the node with its child. The tree remains balanced since the height of the subtree rooted at the deleted node is the same as the height of its child.
- Case 3: The node has two children.
- This case is more complex and requires additional steps to maintain the AVL tree balance. Here's how to handle it:
- Find the node's in-order predecessor or successor (either the largest node in its left subtree or the smallest node in its right subtree).
- Copy the value of the in-order predecessor or successor to the node that needs to be deleted.
- Delete the in-order predecessor or successor node using either Case 1 or Case 2 (since it has at most one child).
- After performing the deletion, we need to update the heights of the ancestors of the deleted node and check for balance violations.
- Starting from the parent of the deleted node, traverse up the tree towards the root, updating the heights of the nodes along the path.
- At each node, check if the height difference between its left and right subtrees is greater than 1 (indicating an imbalance). If an imbalance is detected, proceed to the next step.
- Perform one of the following rotations to restore the balance:
- Left-Left Case: Perform a right rotation at the imbalanced node.
- Right-Right Case: Perform a left rotation at the imbalanced node.
- Left-Right Case: Perform a left rotation at the node's left child, followed by a right rotation at the imbalanced node.
- Right-Left Case: Perform a right rotation at the node's right child, followed by a left rotation at the imbalanced node.
- Continue updating the heights and performing rotations up the tree until the root is reached or the balance is restored.
- After the deletion and necessary rotations, the AVL tree remains balanced, and the deletion operation is complete
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
self.height = 1
def max(a, b):
return a if (a > b) else b
def height(N):
if N is None:
return 0
return N.height
def newNode(data):
node = Node(data)
return node
def rightRotate(y):
x = y.leftChild
T2 = x.rightChild
x.rightChild = y
y.leftChild = T2
y.height = max(height(y.leftChild), height(y.rightChild)) + 1
x.height = max(height(x.leftChild), height(x.rightChild)) + 1
return x
def leftRotate(x):
y = x.rightChild
T2 = y.leftChild
y.leftChild = x
x.rightChild = T2
x.height = max(height(x.leftChild), height(x.rightChild)) + 1
y.height = max(height(y.leftChild), height(y.rightChild)) + 1
return y
def getBalance(N):
if N is None:
return 0
return height(N.leftChild) - height(N.rightChild)
def insertNode(root, data):
if root is None:
return newNode(data)
if data < root.data:
root.leftChild = insertNode(root.leftChild, data)
elif data > root.data:
root.rightChild = insertNode(root.rightChild, data)
else:
return root
root.height = 1 + max(height(root.leftChild), height(root.rightChild))
balance = getBalance(root)
if balance > 1 and data < root.leftChild.data:
return rightRotate(root)
if balance < -1 and data > root.rightChild.data:
return leftRotate(root)
if balance > 1 and data > root.leftChild.data:
root.leftChild = leftRotate(root.leftChild)
return rightRotate(root)
if balance < -1 and data < root.rightChild.data:
root.rightChild = rightRotate(root.rightChild)
return leftRotate(root)
return root
def minValueNode(node):
current = node
while current.leftChild is not None:
current = current.leftChild
return current
def deleteNode(root, data):
if root is None:
return root
if data < root.data:
root.leftChild = deleteNode(root.leftChild, data)
elif data > root.data:
root.rightChild = deleteNode(root.rightChild, data)
else:
if root.leftChild is None:
temp = root.rightChild
root = None
return temp
elif root.rightChild is None:
temp = root.leftChild
root = None
return temp
temp = minValueNode(root.rightChild)
root.data = temp.data
root.rightChild = deleteNode(root.rightChild, temp.data)
if root is None:
return root
root.height = 1 + max(height(root.leftChild), height(root.rightChild))
balance = getBalance(root)
if balance > 1 and getBalance(root.leftChild) >= 0:
return rightRotate(root)
if balance > 1 and getBalance(root.leftChild) < 0:
root.leftChild = leftRotate(root.leftChild)
return rightRotate(root)
if balance < -1 and getBalance(root.rightChild) <= 0:
return leftRotate(root)
if balance < -1 and getBalance(root.rightChild) > 0:
root.rightChild = rightRotate(root.rightChild)
return leftRotate(root)
return root
def printTree(root):
if root is not None:
printTree(root.leftChild)
print(root.data, end=" ")
printTree(root.rightChild)
# Main program
root = None
root = insertNode(root, 22)
root = insertNode(root, 14)
root = insertNode(root, 72)
root = insertNode(root, 44)
root = insertNode(root, 25)
root = insertNode(root, 63)
root = insertNode(root, 98)
print("AVL Tree: ", end="")
printTree(root)
root = deleteNode(root, 25)
print("\nAfter deletion: ", end="")
printTree(root)
class Node {
int data;
Node leftChild;
Node rightChild;
int height;
Node(int data) {
this.data = data;
this.leftChild = null;
this.rightChild = null;
this.height = 1;
}
}
class AVLTree {
Node root;
int max(int a, int b) {
return (a > b) ? a : b;
}
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
Node rightRotate(Node y) {
Node x = y.leftChild;
Node T2 = x.rightChild;
x.rightChild = y;
y.leftChild = T2;
y.height = max(height(y.leftChild), height(y.rightChild)) + 1;
x.height = max(height(x.leftChild), height(x.rightChild)) + 1;
return x;
}
Node leftRotate(Node x) {
Node y = x.rightChild;
Node T2 = y.leftChild;
y.leftChild = x;
x.rightChild = T2;
x.height = max(height(x.leftChild), height(x.rightChild)) + 1;
y.height = max(height(y.leftChild), height(y.rightChild)) + 1;
return y;
}
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.leftChild) - height(N.rightChild);
}
Node insertNode(Node node, int data) {
if (node == null)
return (new Node(data));
if (data < node.data)
node.leftChild = insertNode(node.leftChild, data);
else if (data > node.data)
node.rightChild = insertNode(node.rightChild, data);
else
return node;
node.height = 1 + max(height(node.leftChild), height(node.rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node.leftChild.data)
return rightRotate(node);
if (balance < -1 && data > node.rightChild.data)
return leftRotate(node);
if (balance > 1 && data > node.leftChild.data) {
node.leftChild = leftRotate(node.leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node.rightChild.data) {
node.rightChild = rightRotate(node.rightChild);
return leftRotate(node);
}
return node;
}
Node minValueNode(Node node) {
Node current = node;
while (current.leftChild != null)
current = current.leftChild;
return current;
}
Node deleteNode(Node root, int data) {
if (root == null)
return root;
if (data < root.data)
root.leftChild = deleteNode(root.leftChild, data);
else if (data > root.data)
root.rightChild = deleteNode(root.rightChild, data);
else {
if ((root.leftChild == null) || (root.rightChild == null)) {
Node temp = (root.leftChild != null) ? root.leftChild : root.rightChild;
if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
Node temp = minValueNode(root.rightChild);
root.data = temp.data;
root.rightChild = deleteNode(root.rightChild, temp.data);
}
}
if (root == null)
return root;
root.height = 1 + max(height(root.leftChild), height(root.rightChild));
int balance = getBalance(root);
if (balance > 1 && getBalance(root.leftChild) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root.leftChild) < 0) {
root.leftChild = leftRotate(root.leftChild);
return rightRotate(root);
}
if (balance < -1 && getBalance(root.rightChild) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root.rightChild) > 0) {
root.rightChild = rightRotate(root.rightChild);
return leftRotate(root);
}
return root;
}
void printTree(Node root) {
if (root != null) {
printTree(root.leftChild);
System.out.print(root.data + " ");
printTree(root.rightChild);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insertNode(tree.root, 22);
tree.root = tree.insertNode(tree.root, 14);
tree.root = tree.insertNode(tree.root, 72);
tree.root = tree.insertNode(tree.root, 44);
tree.root = tree.insertNode(tree.root, 25);
tree.root = tree.insertNode(tree.root, 63);
tree.root = tree.insertNode(tree.root, 98);
System.out.print("AVL Tree: ");
tree.printTree(tree.root);
tree.root = tree.deleteNode(tree.root, 25);
System.out.print("\nAfter deletion: ");
tree.printTree(tree.root);
}
}
#include <iostream>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
struct Node *deleteNode(struct Node *root, int data){
if (root == NULL)
return root;
if (data < root->data)
root->leftChild = deleteNode(root->leftChild, data);
else if (data > root->data)
root->rightChild = deleteNode(root->rightChild, data);
else {
if ((root->leftChild == NULL) || (root->rightChild == NULL)) {
struct Node *temp = root->leftChild ? root->leftChild : root->rightChild;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
struct Node *temp = minValueNode(root->rightChild);
root->data = temp->data;
root->rightChild = deleteNode(root->rightChild, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->leftChild),
height(root->rightChild));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->leftChild) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->leftChild) < 0) {
root->leftChild = leftRotate(root->leftChild);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->rightChild) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->rightChild) > 0) {
root->rightChild = rightRotate(root->rightChild);
return leftRotate(root);
}
return root;
}
// Print the tree
void printTree(struct Node *root){
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
root = deleteNode(root, 25);
printf("\nAfter deletion: ");
printTree(root);
return 0;
}This code describes how to implement an AVL tree, including node-adding and -removing operations as well as rotations to keep the AVL tree balanced. Then it shows how to add nodes to the tree and remove one, after which it prints the AVL tree both before and after the deletion operation.
Output
AVL Tree: 14 22 25 44 63 72 98
After deletion: 14 22 44 63 72 98
AVL Tree Implementation
class Node:
def __init__(self, data):
self.data = data
self.leftChild = None
self.rightChild = None
self.height = 1
def max(a, b):
return a if (a > b) else b
def height(N):
if N is None:
return 0
return N.height
def newNode(data):
node = Node(data)
return node
def rightRotate(y):
x = y.leftChild
T2 = x.rightChild
x.rightChild = y
y.leftChild = T2
y.height = max(height(y.leftChild), height(y.rightChild)) + 1
x.height = max(height(x.leftChild), height(x.rightChild)) + 1
return x
def leftRotate(x):
y = x.rightChild
T2 = y.leftChild
y.leftChild = x
x.rightChild = T2
x.height = max(height(x.leftChild), height(x.rightChild)) + 1
y.height = max(height(y.leftChild), height(y.rightChild)) + 1
return y
def getBalance(N):
if N is None:
return 0
return height(N.leftChild) - height(N.rightChild)
def insertNode(node, data):
if node is None:
return newNode(data)
if data < node.data:
node.leftChild = insertNode(node.leftChild, data)
elif data > node.data:
node.rightChild = insertNode(node.rightChild, data)
else:
return node
node.height = 1 + max(height(node.leftChild), height(node.rightChild))
balance = getBalance(node)
if balance > 1 and data < node.leftChild.data:
return rightRotate(node)
if balance < -1 and data > node.rightChild.data:
return leftRotate(node)
if balance > 1 and data > node.leftChild.data:
node.leftChild = leftRotate(node.leftChild)
return rightRotate(node)
if balance < -1 and data < node.rightChild.data:
node.rightChild = rightRotate(node.rightChild)
return leftRotate(node)
return node
def minValueNode(node):
current = node
while current.leftChild is not None:
current = current.leftChild
return current
def deleteNode(root, data):
if root is None:
return root
if data < root.data:
root.leftChild = deleteNode(root.leftChild, data)
elif data > root.data:
root.rightChild = deleteNode(root.rightChild, data)
else:
if root.leftChild is None or root.rightChild is None:
temp = root.leftChild if root.leftChild else root.rightChild
if temp is None:
temp = root
root = None
else:
root = temp
else:
temp = minValueNode(root.rightChild)
root.data = temp.data
root.rightChild = deleteNode(root.rightChild, temp.data)
if root is None:
return root
root.height = 1 + max(height(root.leftChild), height(root.rightChild))
balance = getBalance(root)
if balance > 1 and getBalance(root.leftChild) >= 0:
return rightRotate(root)
if balance > 1 and getBalance(root.leftChild) < 0:
root.leftChild = leftRotate(root.leftChild)
return rightRotate(root)
if balance < -1 and getBalance(root.rightChild) <= 0:
return leftRotate(root)
if balance < -1 and getBalance(root.rightChild) > 0:
root.rightChild = rightRotate(root.rightChild)
return leftRotate(root)
return root
def printTree(root):
if root is not None:
printTree(root.leftChild)
print(root.data, end=" ")
printTree(root.rightChild)
root = None
root = insertNode(root, 22)
root = insertNode(root, 14)
root = insertNode(root, 72)
root = insertNode(root, 44)
root = insertNode(root, 25)
root = insertNode(root, 63)
root = insertNode(root, 98)
print("AVL Tree:", end=" ")
printTree(root)
root = deleteNode(root, 25)
print("\nAfter deletion:", end=" ")
printTree(root)
class Node {
int data;
Node leftChild;
Node rightChild;
int height;
Node(int data) {
this.data = data;
leftChild = null;
rightChild = null;
height = 1;
}
}
class AVLTree {
Node root;
int height(Node N) {
if (N == null)
return 0;
return N.height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
Node rightRotate(Node y) {
Node x = y.leftChild;
Node T2 = x.rightChild;
x.rightChild = y;
y.leftChild = T2;
y.height = max(height(y.leftChild), height(y.rightChild)) + 1;
x.height = max(height(x.leftChild), height(x.rightChild)) + 1;
return x;
}
Node leftRotate(Node x) {
Node y = x.rightChild;
Node T2 = y.leftChild;
y.leftChild = x;
x.rightChild = T2;
x.height = max(height(x.leftChild), height(x.rightChild)) + 1;
y.height = max(height(y.leftChild), height(y.rightChild)) + 1;
return y;
}
int getBalance(Node N) {
if (N == null)
return 0;
return height(N.leftChild) - height(N.rightChild);
}
Node insertNode(Node node, int data) {
if (node == null)
return (new Node(data));
if (data < node.data)
node.leftChild = insertNode(node.leftChild, data);
else if (data > node.data)
node.rightChild = insertNode(node.rightChild, data);
else
return node;
node.height = 1 + max(height(node.leftChild), height(node.rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node.leftChild.data)
return rightRotate(node);
if (balance < -1 && data > node.rightChild.data)
return leftRotate(node);
if (balance > 1 && data > node.leftChild.data) {
node.leftChild = leftRotate(node.leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node.rightChild.data) {
node.rightChild = rightRotate(node.rightChild);
return leftRotate(node);
}
return node;
}
Node minValueNode(Node node) {
Node current = node;
while (current.leftChild != null)
current = current.leftChild;
return current;
}
Node deleteNode(Node root, int data) {
if (root == null)
return root;
if (data < root.data)
root.leftChild = deleteNode(root.leftChild, data);
else if (data > root.data)
root.rightChild = deleteNode(root.rightChild, data);
else {
if (root.leftChild == null || root.rightChild == null) {
Node temp = (root.leftChild != null) ? root.leftChild : root.rightChild;
if (temp == null) {
temp = root;
root = null;
} else
root = temp;
} else {
Node temp = minValueNode(root.rightChild);
root.data = temp.data;
root.rightChild = deleteNode(root.rightChild, temp.data);
}
}
if (root == null)
return root;
root.height = 1 + max(height(root.leftChild), height(root.rightChild));
int balance = getBalance(root);
if (balance > 1 && getBalance(root.leftChild) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root.leftChild) < 0) {
root.leftChild = leftRotate(root.leftChild);
return rightRotate(root);
}
if (balance < -1 && getBalance(root.rightChild) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root.rightChild) > 0) {
root.rightChild = rightRotate(root.rightChild);
return leftRotate(root);
}
return root;
}
void printTree(Node root) {
if (root != null) {
printTree(root.leftChild);
System.out.print(root.data + " ");
printTree(root.rightChild);
}
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.root = tree.insertNode(tree.root, 22);
tree.root = tree.insertNode(tree.root, 14);
tree.root = tree.insertNode(tree.root, 72);
tree.root = tree.insertNode(tree.root, 44);
tree.root = tree.insertNode(tree.root, 25);
tree.root = tree.insertNode(tree.root, 63);
tree.root = tree.insertNode(tree.root, 98);
System.out.print("AVL Tree: ");
tree.printTree(tree.root);
tree.root = tree.deleteNode(tree.root, 25);
System.out.print("\nAfter deletion: ");
tree.printTree(tree.root);
}
}
#include <iostream>
struct Node {
int data;
struct Node *leftChild;
struct Node *rightChild;
int height;
};
int max(int a, int b);
int height(struct Node *N){
if (N == NULL)
return 0;
return N->height;
}
int max(int a, int b){
return (a > b) ? a : b;
}
struct Node *newNode(int data){
struct Node *node = (struct Node *) malloc(sizeof(struct Node));
node->data = data;
node->leftChild = NULL;
node->rightChild = NULL;
node->height = 1;
return (node);
}
struct Node *rightRotate(struct Node *y){
struct Node *x = y->leftChild;
struct Node *T2 = x->rightChild;
x->rightChild = y;
y->leftChild = T2;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
return x;
}
struct Node *leftRotate(struct Node *x){
struct Node *y = x->rightChild;
struct Node *T2 = y->leftChild;
y->leftChild = x;
x->rightChild = T2;
x->height = max(height(x->leftChild), height(x->rightChild)) + 1;
y->height = max(height(y->leftChild), height(y->rightChild)) + 1;
return y;
}
int getBalance(struct Node *N){
if (N == NULL)
return 0;
return height(N->leftChild) - height(N->rightChild);
}
struct Node *insertNode(struct Node *node, int data){
if (node == NULL)
return (newNode(data));
if (data < node->data)
node->leftChild = insertNode(node->leftChild, data);
else if (data > node->data)
node->rightChild = insertNode(node->rightChild, data);
else
return node;
node->height = 1 + max(height(node->leftChild),
height(node->rightChild));
int balance = getBalance(node);
if (balance > 1 && data < node->leftChild->data)
return rightRotate(node);
if (balance < -1 && data > node->rightChild->data)
return leftRotate(node);
if (balance > 1 && data > node->leftChild->data) {
node->leftChild = leftRotate(node->leftChild);
return rightRotate(node);
}
if (balance < -1 && data < node->rightChild->data) {
node->rightChild = rightRotate(node->rightChild);
return leftRotate(node);
}
return node;
}
struct Node *minValueNode(struct Node *node){
struct Node *current = node;
while (current->leftChild != NULL)
current = current->leftChild;
return current;
}
struct Node *deleteNode(struct Node *root, int data){
if (root == NULL)
return root;
if (data < root->data)
root->leftChild = deleteNode(root->leftChild, data);
else if (data > root->data)
root->rightChild = deleteNode(root->rightChild, data);
else {
if ((root->leftChild == NULL) || (root->rightChild == NULL)) {
struct Node *temp = root->leftChild ? root->leftChild : root->rightChild;
if (temp == NULL) {
temp = root;
root = NULL;
} else
*root = *temp;
free(temp);
} else {
struct Node *temp = minValueNode(root->rightChild);
root->data = temp->data;
root->rightChild = deleteNode(root->rightChild, temp->data);
}
}
if (root == NULL)
return root;
root->height = 1 + max(height(root->leftChild),
height(root->rightChild));
int balance = getBalance(root);
if (balance > 1 && getBalance(root->leftChild) >= 0)
return rightRotate(root);
if (balance > 1 && getBalance(root->leftChild) < 0) {
root->leftChild = leftRotate(root->leftChild);
return rightRotate(root);
}
if (balance < -1 && getBalance(root->rightChild) <= 0)
return leftRotate(root);
if (balance < -1 && getBalance(root->rightChild) > 0) {
root->rightChild = rightRotate(root->rightChild);
return leftRotate(root);
}
return root;
}
// Print the tree
void printTree(struct Node *root){
if (root != NULL) {
printTree(root->leftChild);
printf("%d ", root->data);
printTree(root->rightChild);
}
}
int main(){
struct Node *root = NULL;
root = insertNode(root, 22);
root = insertNode(root, 14);
root = insertNode(root, 72);
root = insertNode(root, 44);
root = insertNode(root, 25);
root = insertNode(root, 63);
root = insertNode(root, 98);
printf("AVL Tree: ");
printTree(root);
root = deleteNode(root, 25);
printf("\nAfter deletion: ");
printTree(root);
return 0;
}An AVL tree data structure is defined and implemented in this code. The tree can be rotated, printed, and subjected to insertion and deletion operations. In the code, nodes are added to the AVL tree, a node is deleted, and then the tree is printed both before and after the deletion operation.
Output
AVL Tree: 14 22 25 44 63 72 98
After deletion: 14 22 44 63 72 98Balance Factor in AVL Tree in Data Structures
The balance factor in AVL Tree in Data Structures is a numerical value that represents the difference in height between the left and right subtrees of a node. It is used to determine if the tree is balanced or needs rebalancing. In an AVL tree, each node is assigned a balance factor of either -1, 0, or 1. The balance factor is calculated as follows:
- Balance Factor = height(left subtree) - height(right subtree)
- Here, the height of a subtree is the maximum number of edges from the root node to a leaf node in that subtree. By convention, an empty subtree has a height of -1.
- The balance factor helps maintain the balance property of an AVL tree, which states that for every node in the tree, the heights of its left and right subtrees differ by at most 1.
- When inserting or deleting nodes in an AVL tree, the balance factor of affected nodes is checked. If a node's balance factor becomes -2 or 2 (indicating an imbalance), rotations are performed to restore the balance. The specific type of rotation depends on the relationship between the node and its children.
- For example, if a node has a balance factor of -2, it means its left subtree is two levels higher than its right subtree, indicating a "left-heavy" imbalance. In this case, a right rotation is performed to restore balance.
- Similarly, if a node has a balance factor of 2, it means its right subtree is two levels higher than its left subtree, indicating a "right-heavy" imbalance. In this case, a left rotation is performed.
- After rotations, the balance factors of the affected nodes are updated, and the process continues until the entire tree is balanced again.
- By maintaining the balance property through the balance factor, AVL trees ensure efficient insertion, deletion, and search operations with a worst-case time complexity of O(log n), where n is the number of nodes in the tree
Advantages of AVL Tree in Data Structures:
- AVL trees are capable of self-balancing.
- It can't possibly be skewed.
- Compared to Red-Black Trees, it offers faster lookups.
- Superior searching efficiency compared to other trees, such as the binary tree.
- Height is limited to log(N), where N is the number of nodes in the tree as a whole.
Disadvantages of AVL Tree in Data Structures:
- Implementing it is challenging.
- Certain procedures have high constant factors.
- Compared to Red-Black trees, less common.
- As additional rotations are conducted, AVL trees offer complex insertion and removal procedures because of their rather rigid balance.
- Take longer to process in order to balance.
FAQs
1. What is the difference between binary and AVL?
The balancing of binary trees and AVL trees is where they differ most from one another. In contrast to self-balancing binary search trees (AVL trees), which may automatically maintain balance, binary trees can fall out of balance, which can result in ineffective operations.
2. What is an AVL tree example?
A self-balancing binary search tree is an example of an AVL tree, and it has a maximum height difference (balance factor) of 1 between its left and right subtrees. For instance, an AVL tree will be balanced if the elements are added in the following order: 10, 20, 30, 40, 50, 25, etc.
3. What is the AVL tree?
A self-balancing binary search tree known as an AVL tree, or Adelson-Velsky and Landis tree, has a balance factor of every node (the height difference between its left and right subtrees) that is no greater than 1.
4. What is the main use of the AVL Tree in Data Structures?
An AVL tree is useful for database indexing and other data storage applications because it ensures that insertion, deletion, and searching operations are efficient and maintain their logarithmic time complexity.
5. How many types of AVL trees are there?
Although there is normally only one type of AVL tree, several implementations may use modifications and optimizations. The major objective is to keep the tree balanced, and while different implementations may slightly differ in how this balance is accomplished, they all follow the same basic idea of self-balancing binary search trees.
Summary
AVL Tree in Data Structures is a great tool to help structure and organize data. By keeping track of the difference in heights between two nodes, AVL data structures can save you from having to calculate these values manually. Furthermore, as it is self-balancing, you don’t have to worry about the tree becoming unbalanced as it grows. While traversing may take longer due to all the re-balancing happening, this method gives you greater control over your data sets than many regular BSTs would and it is a more efficient use of memory. So go out there and make wise use of this powerful data structure technology - happy coding!
Take our free skill tests to evaluate your skill!
In less than 5 minutes, with our skill test, you can identify your knowledge gaps and strengths.
Previous Tutorial
