UNIT-3: AVL Trees & B-Trees
Advanced Data Structures
Topics
What is AVL Tree?
AVL tree is a height-balanced binary search tree. That means, an AVL tree is also a binary search tree but it is a balanced tree. A binary tree is said to be balanced if, the difference between the heights of left and right subtrees of every node in the tree is either -1, 0 or +1.
In an AVL tree, every node maintains an extra information known as balance factor. The balance factor of a node is calculated as:
BalanceFactor(N)=height(Left subtree)−height(Right subtree)
Each node in an AVL Tree must satisfy the balance criterion
(i.e, N in -1, 0, 1) to maintain self-balancing.
For example, the given tree is a binary search tree and
every node is satisfying balance factor condition.
So, this tree is said to be an AVL tree.
Note: Every AVL Tree is a binary search tree but
every Binary Search Tree need not be AVL tree.
1. a) AVL Tree and It’s Advantages
Scenario: Balancing a BST
Question: A BST has become unbalanced due to a series of insertions or deletions, leading to poor search performance. How can you address this issue?
Answer: Unbalanced BSTs can be rebalanced using various techniques like AVL trees. AVL trees use rotations to maintain a balanced structure during insertions and deletions.
AVL Tree Advantages
AVL Tree Rotations
In AVL tree, after performing operations like insertion and deletion we need to check the balance factor of every node in the tree. If every node satisfies the balance factor condition, then we conclude the operation otherwise we must make it balanced. Whenever the tree becomes imbalanced due to any operation, we use rotation operations to make the tree balanced. There are four rotations and they are classified into two types.
1. b) AVL Tree Rotations
Single Left Rotation (LL Rotation): In LL Rotation, every node moves one position to left from the current position. To understand LL Rotation, let us consider the following insertion operation in AVL Tree:
@ AVL Tree LL Rotation
Single Right Rotation (RR Rotation): In RR Rotation, every node moves one position to right from the current position. To understand RR Rotation, let us consider the following insertion operation in AVL Tree:
@ AVL Tree RR Rotation
Left Right Rotation (LR Rotation): The LR Rotation is a sequence of single left rotation followed by a single right rotation. In LR Rotation, at first, every node moves one position to the left and one position to right from the current position. To understand LR Rotation, let us consider the following insertion operation in AVL Tree.
@ AVL Tree LR Rotation
Right Left Rotation (RL Rotation): The RL Rotation is sequence of single right rotation followed by single left rotation. In RL Rotation, at first every node moves one position to right and one position to left from the current position. To understand RL Rotation, let us consider the following insertion operation in AVL Tree.
@ AVL Tree RL Rotation
AVL Tree Operations
The following three basic operations are performed on AVL tree:
Insertion Operation in AVL Tree
In an AVL tree, the insertion operation is performed with O(log n) time complexity. In AVL Tree, a new node is always inserted as a leaf node. The insertion operation is performed as follows:
Step 1 - Insert the new element into the tree using Binary Search Tree insertion logic.
Step 2 - After insertion, check the Balance Factor of every node.
Step 3 - If the Balance Factor of every node is 0 or 1 or -1 then go for next operation.
Step 4 - If the Balance Factor of any node is other than 0 or 1 or -1 then that tree is said to be imbalanced. In this case, perform suitable Rotation to make it balanced and go for next operation.
1. c) AVL Operations
Example: Construct an AVL Tree by inserting numbers from 1 to 8.
Deletion Operation in AVL Tree
The deletion operation in an AVL Tree is similar to deletion operation in a Binary Search Tree (BST). But after every deletion operation, we need to check with the Balance Factor condition. If the tree is balanced after deletion go for next operation otherwise perform suitable rotation to make the tree Balanced. The steps for deletion operation in an AVL tree is as follows:
1. Locate and Delete the Node (BST Deletion):
i. Leaf node: If the node has no children, simply remove it.
ii. Node with one child: Remove the node and link its parent directly to its single child.
iii. Node with two children: Find the in-order successor (smallest node in the right subtree) or in-order predecessor (largest node in the left subtree). Copy its value to the node being deleted, and then recursively delete the successor/predecessor node from its original position.
2. Rebalance the Tree (AVL Specific):
This process ensures that after every deletion, the AVL tree remains balanced, preserving its logarithmic time complexity for subsequent operations.
Example: Suppose to delete key 32 from the given AVL tree
B-Tree
B-Tree is a self-balanced binary search tree in which every node contains multiple keys and has more than two children. B-Tree maintains sorted data and allows sequential access, insertions, deletions, and searches in logarithmic time.
A B-Tree of order m can have at most m-1 keys and m children. One of the main reasons of using B-Tree is its capability to store large number of keys in a single node and large key values by keeping the height of the tree relatively small.
B- Tree Properties:
2. a) B-Tree and It’s Advantages
Advantages of B-Tree:
Disadvantages of B-Tree:
Applications of B-Tree:
For example, B-Tree of order 4 contains a maximum of 3 key values in a node and maximum of 4 children for a node.
Calculate the maximum (m−1) and, minimum ([m/2[−1) number of keys a node can hold, where m is denoted by the order of the B Tree.
Order -> m = 4
Maximum keys -> m-1 = 3 Maximum children -> m = 4
Minimum keys -> m/2 - 1 = 1 Minimum children -> m/2 = 2
2. b) B-Tree of order m
Example 1: Construct a B-Tree of order 3 by inserting numbers from 1 to 10.
2. c) B-Tree Insertion Operation
This is a final B-Tree of order 3.
Example 2: Construct a B-Tree of order 4 by inserting numbers 5, 3, 21, 9, 13, 22, 7, 10, 11, 14, 8, 16
Step 1 − Calculate the maximum (m−1) and, minimum ([m/2[−1) number of keys a node can hold, where m is denoted by the order of the B Tree.
Order -> m = 4
Maximum keys -> m-1 = 3 Maximum children -> m = 4
Minimum keys -> m/2 - 1 = 1 Minimum children -> m/2 = 2
Step 2 − The data is inserted into the tree using the binary search insertion and once the keys reach the maximum number, the node is split into half and the median key becomes the internal node while the left and right keys become its children
Step 3 − All the leaf nodes must be on the same level.
The keys, 5, 3, 21, 9, 13 are all added into the node according to the binary search property but if we add the key 22, it will violate the maximum key property. Hence, the node is split in half, the median key is shifted to the parent node and the insertion is then continued.
Another hiccup occurs during the insertion of 11, so the node is split and median is shifted to the parent.
The final B tree after inserting all the elements is achieved
Red-Black Tree:
Red-Black Tree is another variant of Binary Search Tree in which every node is colored either RED or BLACK. In Red Black Tree, the color of a node is decided based on the properties of Red-Black Tree.
Properties of Red-Black Tree: In Red Black Tree, the colour of a node is decided based on the properties of Red-Black Tree. Every Red Black Tree has the following properties:
Property #1: Red - Black Tree must be a Binary Search Tree.
Property #2: Every new node must be inserted with RED colour.
Property #3: The ROOT node must be coloured BLACK.
Property #4: The children of RED coloured node must be coloured BLACK. (There should not be two consecutive RED nodes).
Property #5: In all the paths of the tree, there should be same number of BLACK coloured nodes.
Property #6: Every leaf (i.e. NULL node) must be coloured BLACK.
Note: Every Red Black Tree is a binary search tree but every Binary Search Tree need not be Red Black tree.
3. a) Red-Black Tree
Red Black Tree
Insertion Operation in RED-BLACK Tree
In the Red-Black tree, we use two methods to do the insertion operation.
Recolouring is the change in colour of the node i.e. if it is red then change it to black and vice versa. It must be noted that the colour of the NULL node is always black. Moreover, we always try recolouring first, if recolouring doesn't work, then we go for rotation.
The algorithms have mainly two cases depending upon the colour of the uncle.
(G) Grandparent
/ \
(P) Parent (U) Uncle
/
(N) New Node
Algorithm
a) If x's uncle is RED
b) If x's uncle is BLACK, then there can be four configurations for x, x's parent (p) and x's grandparent (g) (This is similar to AVL Tree)
i. Left Left Case (p is left child of g and x is left child of p).
ii. Left Right Case (p is left child of g and x is the right child of p).
iii. Right Right Case (Mirror of case i).
iv. Right Left Case (Mirror of case ii).
Re-colouring after rotations:
Example: Creating a red-black tree with elements 3, 21, 32 and 15.
Solution:
Step-1: Inserting element 3 as new node. When the first element is inserted as a root node so it must be color BLACK
Step-2: Inserting next element 21, the new element is always inserted with a RED colour and as 21 > 3, So it becomes the part of the right sub-tree of the root node.
Step-3: Inserting element 32, Now, as we insert 32 we see there is a red father-child pair which violates the Red-Black tree rule so we have to rotate it. Moreover, we see the conditions of RR rotation (considering the null node of the root node as black) so after rotation as the root node can’t be Red so we have to perform recoloring in the tree resulting in the tree shown below.
Step-4: Inserting element 15, Now, as we insert 15 we see that as two red nodes are not possible and also, we perform recoloring in the tree which result in red colored root node. So, we simply color it to black.
Final Tree Structure
Red-Black Tree Examples:
4 a) Splay Tree
A splay tree is a self-balancing binary search tree with the additional property that recently accessed elements are quick to access again. A splay tree performs basic operations such as insertion, deletion and search in O(log n) time. A splay tree contains one more operation, i.e., splaying. By splaying elements, we bring more frequently used elements closer to the root of the tree so that any operation on those elements is performed quickly.
For searching, we will perform the binary search method.
Let’s say we want to search for element 9. As 9 is less than 11, we will come to the left of the root node. After performing a search operation, we need to do one thing called splaying. This means, splaying an element is the process of bringing it to the root position by performing suitable rotation operations.
Note: Every Splay tree must be a binary search tree but it is need not to be balanced tree.
Rotations in Splay Tree
To rearrange the tree, we need to perform some rotations. The rotations given below are the rotations that we are going to perform in the splay tree:
4 b) Rotations in Splay Tree
Zig rotation: This rotation is similar to the right rotation in the AVL tree. In zig rotation, every node moves one position to the right of its current position. We use Zig rotation when the item which is to be searched is either a root node or a left child of the root node.
Let’s take a scenario where the search item 3 is the left child of the root node 5.
In the above diagram, we can see that node 3 has become the root node of the tree, this shows that the searching is completed.
Zag rotation: This rotation is similar to the left rotation in the AVL tree. In zag rotation, every node moves one position to the left of its current position. We use Zag rotation when the item which is to be searched is either a root node or a right child of the root node.
Let’s take a scenario where the search item 5 is the right child of the root node 3.
In the above diagram, we can see that node 5 has become the root node of the tree, this shows that the searching is completed.
Zig-Zig rotation: In Zig-Zig rotation, every node moves two positions to the right of its current position. We use Zig-Zig rotation when the item which is to be searched is either a root node or a left child of the root node.
Let’s take a scenario where the search item 2 is the left child of the node 3 and root node 5.
In the above diagram, we can see that node 2 has become the root node of the tree, this shows that the searching is completed.
Zag-Zag Rotation: In Zag-Zag rotation, every node moves two positions to the left of its current position. We use Zag-Zag rotation when the item which is to be searched is either a root node or a right child of the root node.
Let’s take a scenario where the search item 6 is the right child of the node 5 and root node 3.
In the above diagram, we can see that node 6 has become the root node of the tree, this shows that the searching is completed.
Zig-Zag rotation: This type of rotation is a sequence of zig rotations followed by zag rotations. So far, we've seen that both the parent and the grandparent are in a RR or LL relationship. Now, here we will see the RL and LR kinds of relationships between parent and grandparent. Every node moves one position to the right, followed by one position to the left of its current position.
Let’s take a scenario where the search item 4 is the left child of the node 5 and right child of the root node 3.
In the above diagram, we can see that node 4 has become the root node of the tree, this shows that the searching is completed.
Zag-Zig Rotation: This rotation is similar to the Zig-zag rotation, the only difference is that here every node moves one position to the left, followed by one position to the right of its current position.
Let’s take a scenario where the search item 4 is the right child of the node 3 and left child of the root node 5.
In the above diagram, we can see that node 4 has become the root node of the tree, this shows that the searching is completed.