$40
DS Lab 7 AVL Tree Solved
Lab 7
AVL Tree
In the previous lab, we learned how to build up a BST. And in this tutorial, we continue to extend Binary Search Tree to the Balanced Binary Search Tree, one of them called AVL Tree.
1. What is AVL Tree?
AVL is the abbreviation of the Russian authors Adelson-Velskii and Landis (1962) who defined the balanced tree.
An AVL tree is the same as a binary search tree, except that for every node, the height of the left and right subtrees can differ only by 1 (and an empty tree has a height of -1)1. This difference is called Balance Factor. When the Balance Factor 1, the tree will be rebalanced.
Figure 1: AVL tree
2. Node of a AVL tree
In this lab, we add one more attribute which is called height to the Node class (same with BST). This attribute will help us access the height of the node faster.
1https://web.stanford.edu/class/archive/cs/cs106b/cs106b.1176/lectures/20-BinarySearchTrees/20BinarySearchTrees.pptx
1
public class Node{ Integer key; Node left,right; int height;
public Node(Integer key){ this.key = key; this.height = 0;
this.left = this.right = null;
}
}
1
2
3
4
5
6
7
8
9
10
11
In AVL class:
public int height(Node node){ if (node == null) return -1;
return node.height; }
1
2
3
4
5
3. Check balance factor
A Balance Factor of a AVL tree is defined by the height difference of the left subtree and the right subtree.
private int checkBalance(Node x) { return height(x.left) - height(x.right); }
1
2
3
4. Rotation
The insert or delete operation may make the AVL tree come to imbalance. A simple modification of the tree, called rotation, can restore the AVL property. We have 4 types of rotation corresponding to 4 violation cases that make the tree imbalance.
4.1. Left rotation
When a new node is inserted into a AVL tree and makes it a right-right-unbalancedtree. The tree can be re-balanced using left rotation as following:
Figure 2: Left rotation
This is the code of left rotation:
private Node rotateLeft(Node x) {
Node y = x.right; x.right = y.left;
y.left = x;
x.height = 1 + Math.max(height(x.left), height(x.right));
y.height = 1 + Math.max(height(y.left), height(y.right)); return y;
}
1
2
3
4
5
6
7
8
4.2. Right rotation
When a new node is inserted into a AVL tree and make it a left-left-unbalanced-tree. The tree can be re-balanced using right rotation as following:
Figure 3: Right rotation
private Node rotateRight(Node x) {
//your turn }
1
2
3
4.3. Left-Right rotation
When a new node is inserted into a AVL tree and make it a left-right-unbalancedtree. The tree can be re-balanced using left-right rotation.
Figure 4: Left-Right rotation
First, we perform a left rotation on node A (the left subtree of C).
Figure 5: Left-Right rotation
This makes A come to the left subtree of B. And B replaces A to become the left subtree of C.
Figure 6: Left-Right rotation
Now, node C is remaining unbalanced but it has become case left-left-unbalancedtree and right rotation can be used to balance the tree.
4.4. Right-Left rotation
When a new node is inserted into a AVL tree and make it a right-left-unbalancedtree. The tree can be re-balanced using right-left rotation.
Figure 7: Right-Left rotation
First, we perform a right rotation on node C (the left subtree of A).
Figure 8: Right-Left rotation
This makes C come to the right subtree of B. And B replaces C to become the right subtree of A.
Figure 9: Right-Left rotation
Now, node A is remaining unbalanced but it has become case right-right-unbalancedtree and left rotation can be used to balance the tree.
5. Balance
This is the code to re-balance the tree:
private Node balance(Node x) { if (checkBalance(x) < -1) { if (checkBalance(x.right) 0) {
x.right = rotateRight(x.right); }
x = rotateLeft(x);
}
else if (checkBalance(x) 1) { if (checkBalance(x.left) < 0) {
x.left = rotateLeft(x.left); }
x = rotateRight(x);
} return x;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
6. Exercise
Exercise 1
Complete the class to build the AVL tree. You can re-use the BST code in the previous lab (insertion, deletion).
