AVL Tree

AVL Tree is invented by GM Adelson - Velsky and EM Landis in 1962. The tree is named
AVL in honour of its inventors.

AVL Tree can be defined as height balanced binary search tree in which each node is
associated with a balance factor which is calculated by subtracting the height of its
right sub-tree from that of its left sub-tree.

Tree is said to be balanced if balance factor of each node is in between -1 to 1,

otherwise, the tree will be unbalanced and need to be balanced.

Balance Factor (k) = height (left(k)) - height (right(k))

If balance factor of any node is 1, it means that the left sub-tree is one level higher
than the right sub-tree.

28.7M
632
C++ vs Java

If balance factor of any node is 0, it means that the left sub-tree and right sub-tree
contain equal height.

If balance factor of any node is -1, it means that the left sub-tree is one level lower
than the right sub-tree.

An AVL tree is given in the following figure. We can see that, balance factor associated
with each node is in between -1 and +1. therefore, it is an example of AVL tree.
Complexity

Algorithm Average case Worst case

Space o(n) o(n)

Search o(log n) o(log n)

Insert o(log n) o(log n)

Delete o(log n) o(log n)

Operations on AVL tree

Due to the fact that, AVL tree is also a binary search tree therefore, all the operations
are performed in the same way as they are performed in a binary search tree. Searching
and traversing do not lead to the violation in property of AVL tree. However, insertion
and deletion are the operations which can violate this property and therefore, they
need to be revisited.

SN Operation Description

1 Insertion Insertion in AVL tree is performed in the same way as it is performed in a

However, it may lead to violation in the AVL tree property and therefore
balancing. The tree can be balanced by applying rotations.

2 Deletion Deletion can also be performed in the same way as it is performed in a binary s
may also disturb the balance of the tree therefore, various types of rotations a
the tree.

Why AVL Tree?

AVL tree controls the height of the binary search tree by not letting it to be skewed.
The time taken for all operations in a binary search tree of height h is O(h). However,
it can be extended to O(n) if the BST becomes skewed (i.e. worst case). By limiting this
height to log n, AVL tree imposes an upper bound on each operation to be O(log
n) where n is the number of nodes.

AVL Rotations
We perform rotation in AVL tree only in case if Balance Factor is other than -1, 0, and
1. There are basically four types of rotations which are as follows:

1. L L rotation: Inserted node is in the left subtree of left subtree of A

2. R R rotation : Inserted node is in the right subtree of right subtree of A
3. L R rotation : Inserted node is in the right subtree of left subtree of A
4. R L rotation : Inserted node is in the left subtree of right subtree of A

Where node A is the node whose balance Factor is other than -1, 0, 1.

The first two rotations LL and RR are single rotations and the next two rotations LR and
RL are double rotations. For a tree to be unbalanced, minimum height must be at least
2, Let us understand each rotation

1. RR Rotation
When BST becomes unbalanced, due to a node is inserted into the right subtree of the
right subtree of A, then we perform RR rotation, RR rotation
is an anticlockwise rotation, which is applied on the edge below a node having balance factor
-2

In above example, node A has balance factor -2 because a node C is inserted in the
right subtree of A right subtree. We perform the RR rotation on the edge below A.

2. LL Rotation
When BST becomes unbalanced, due to a node is inserted into the left subtree of the
left subtree of C, then we perform LL rotation, LL rotation

is clockwise rotation, which is applied on the edge below a node having balance factor 2.

In above example, node C has balance factor 2 because a node A is inserted in the left
subtree of C left subtree. We perform the LL rotation on the edge below A.

3. LR Rotation
Double rotations are bit tougher than single rotation which has already explained
above. LR rotation = RR rotation + LL rotation, i.e., first RR rotation is performed on
subtree and then LL rotation is performed on full tree, by full tree we mean the first
node from the path of inserted node whose balance factor is other than -1, 0, or 1.

Let us understand each and every step very clearly:

State Action
 A node B has been inserted into the right subtree of A the left subtree of C,
has become an unbalanced node having balance factor 2. This case is L R rota
node is in the right subtree of left subtree of C

As LR rotation = RR + LL rotation, hence RR (anticlockwise) on subtree roote

first. By doing RR rotation, node A, has become the left subtree of B.

After performing RR rotation, node C is still unbalanced, i.e., having balance

node A is in the left of left of C

Now we perform LL clockwise rotation on full tree, i.e. on node C. node C h

right subtree of node B, A is left subtree of B

Balance factor of each node is now either -1, 0, or 1, i.e. BST is balanced now.

4. RL Rotation
As already discussed, that double rotations are bit tougher than single rotation which
has already explained above. R L rotation
= LL rotation + RR rotation, i.e., first LL rotation is performed on subtree and then RR
rotation is performed on full tree, by full tree we mean the first node from the path of inserted
node whose balance factor is other than -1, 0, or 1.

State Action

A node B has been inserted into the left subtree of C the right subtree of A,
has become an unbalanced node having balance factor - 2. This case is RL rota
node is in the left subtree of right subtree of A

As RL rotation = LL rotation + RR rotation, hence, LL (clockwise) on sub

performed first. By doing RR rotation, node C has become the right subtree o

After performing LL rotation, node A is still unbalanced, i.e. having balance

because of the right-subtree of the right-subtree node A.

Now we perform RR rotation (anticlockwise rotation) on full tree, i.e. on node

become the right subtree of node B, and node A has become the left subtree
 Balance factor of each node is now either -1, 0, or 1, i.e., BST is balanced now.

Q: Construct an AVL tree having the following elements

H, I, J, B, A, E, C, F, D, G, K, L

1. Insert H, I, J

On inserting the above elements, especially in the case of H, the BST becomes
unbalanced as the Balance Factor of H is -2. Since the BST is right-skewed, we will
perform RR Rotation on node H.

The resultant balance tree is:

2. Insert B, A

On inserting the above elements, especially in case of A, the BST becomes unbalanced
as the Balance Factor of H and I is 2, we consider the first node from the last inserted
node i.e. H. Since the BST from H is left-skewed, we will perform LL Rotation on node
H.

The resultant balance tree is:

3. Insert E

On inserting E, BST becomes unbalanced as the Balance Factor of I is 2, since if we

travel from E to I we find that it is inserted in the left subtree of right subtree of I, we
will perform LR Rotation on node I. LR = RR + LL rotation

3 a) We first perform RR rotation on node B

The resultant tree after RR rotation is:

3b) We first perform LL rotation on the node I

The resultant balanced tree after LL rotation is:

4. Insert C, F, D

On inserting C, F, D, BST becomes unbalanced as the Balance Factor of B and H is -2,

since if we travel from D to B we find that it is inserted in the right subtree of left
subtree of B, we will perform RL Rotation on node I. RL = LL + RR rotation.

4a) We first perform LL rotation on node E

The resultant tree after LL rotation is:

4b) We then perform RR rotation on node B

The resultant balanced tree after RR rotation is:

5. Insert G
On inserting G, BST become unbalanced as the Balance Factor of H is 2, since if we
travel from G to H, we find that it is inserted in the left subtree of right subtree of H,
we will perform LR Rotation on node I. LR = RR + LL rotation.

5 a) We first perform RR rotation on node C

The resultant tree after RR rotation is:

5 b) We then perform LL rotation on node H

The resultant balanced tree after LL rotation is:

6. Insert K

On inserting K, BST becomes unbalanced as the Balance Factor of I is -2. Since the BST
is right-skewed from I to K, hence we will perform RR Rotation on the node I.

The resultant balanced tree after RR rotation is:

7. Insert L

On inserting the L tree is still balanced as the Balance Factor of each node is now either,
-1, 0, +1. Hence the tree is a Balanced AVL tree

B Tree
B Tree is a specialized m-way tree that can be widely used for disk access. A B-Tree of
order m can have at most m-1 keys and m children. One of the main reason 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.

A B tree of order m contains all the properties of an M way tree. In addition, it contains
the following properties.

1. Every node in a B-Tree contains at most m children.

2. Every node in a B-Tree except the root node and the leaf node contain at least
m/2 children.
3. The root nodes must have at least 2 nodes.
4. All leaf nodes must be at the same level.

It is not necessary that, all the nodes contain the same number of children but, each
node must have m/2 number of nodes.

A B tree of order 4 is shown in the following image.

Difference between JDK, JRE, and JVM

While performing some operations on B Tree, any property of B Tree may violate such
as number of minimum children a node can have. To maintain the properties of B Tree,
the tree may split or join.

Operations
Searching :
Searching in B Trees is similar to that in Binary search tree. For example, if we search
for an item 49 in the following B Tree. The process will something like following :
 1. Compare item 49 with root node 78. since 49 < 78 hence, move to its left sub-
tree.
2. Since, 40<49<56, traverse right sub-tree of 40.
3. 49>45, move to right. Compare 49.
4. match found, return.

Searching in a B tree depends upon the height of the tree. The search algorithm takes
O(log n) time to search any element in a B tree.

Inserting
Insertions are done at the leaf node level. The following algorithm needs to be followed
in order to insert an item into B Tree.

1. Traverse the B Tree in order to find the appropriate leaf node at which the node
can be inserted.
2. If the leaf node contain less than m-1 keys then insert the element in the
increasing order.
3. Else, if the leaf node contains m-1 keys, then follow the following steps.
o Insert the new element in the increasing order of elements.
o Split the node into the two nodes at the median.
o Push the median element upto its parent node.
o If the parent node also contain m-1 number of keys, then split it too by
following the same steps.

Example:
Insert the node 8 into the B Tree of order 5 shown in the following image.

8 will be inserted to the right of 5, therefore insert 8.

The node, now contain 5 keys which is greater than (5 -1 = 4 ) keys. Therefore split the
node from the median i.e. 8 and push it up to its parent node shown as follows.

Deletion
Deletion is also performed at the leaf nodes. The node which is to be deleted can either
be a leaf node or an internal node. Following algorithm needs to be followed in order
to delete a node from a B tree.

1. Locate the leaf node.

2. If there are more than m/2 keys in the leaf node then delete the desired key
from the node.
3. If the leaf node doesn't contain m/2 keys then complete the keys by taking the
element from eight or left sibling.
 o If the left sibling contains more than m/2 elements then push its largest
element up to its parent and move the intervening element down to the
node where the key is deleted.
o If the right sibling contains more than m/2 elements then push its
smallest element up to the parent and move intervening element down
to the node where the key is deleted.
4. If neither of the sibling contain more than m/2 elements then create a new leaf
node by joining two leaf nodes and the intervening element of the parent node.
5. If parent is left with less than m/2 nodes then, apply the above process on the
parent too.

If the the node which is to be deleted is an internal node, then replace the node with
its in-order successor or predecessor. Since, successor or predecessor will always be
on the leaf node hence, the process will be similar as the node is being deleted from
the leaf node.

Example 1

Delete the node 53 from the B Tree of order 5 shown in the following figure.

53 is present in the right child of element 49. Delete it.

Now, 57 is the only element which is left in the node, the minimum number of elements
that must be present in a B tree of order 5, is 2. it is less than that, the elements in its
left and right sub-tree are also not sufficient therefore, merge it with the left sibling
and intervening element of parent i.e. 49.
The final B tree is shown as follows.

Application of B tree
B tree is used to index the data and provides fast access to the actual data stored on
the disks since, the access to value stored in a large database that is stored on a disk
is a very time consuming process.

Searching an un-indexed and unsorted database containing n key values needs O(n)
running time in worst case. However, if we use B Tree to index this database, it will be
searched in O(log n) time in worst case.

B+ Tree
B+ Tree is an extension of B Tree which allows efficient insertion, deletion and search
operations.

In B Tree, Keys and records both can be stored in the internal as well as leaf nodes.
Whereas, in B+ tree, records (data) can only be stored on the leaf nodes while internal
nodes can only store the key values.

The leaf nodes of a B+ tree are linked together in the form of a singly linked lists to
make the search queries more efficient.

B+ Tree are used to store the large amount of data which can not be stored in the
main memory. Due to the fact that, size of main memory is always limited, the internal
nodes (keys to access records) of the B+ tree are stored in the main memory whereas,
leaf nodes are stored in the secondary memory.

Difference between JDK, JRE, and JVM

The internal nodes of B+ tree are often called index nodes. A B+ tree of order 3 is
shown in the following figure.
Advantages of B+ Tree
1. Records can be fetched in equal number of disk accesses.
2. Height of the tree remains balanced and less as compare to B tree.
3. We can access the data stored in a B+ tree sequentially as well as directly.
4. Keys are used for indexing.
5. Faster search queries as the data is stored only on the leaf nodes.

B Tree VS B+ Tree

SN B Tree B+ Tree
 1 Search keys can not be repeatedly stored. Redundant search keys can be p

2 Data can be stored in leaf nodes as well as internal nodes Data can only be stored on the l

3 Searching for some data is a slower process since data can Searching is comparatively faste
be found on internal nodes as well as on the leaf nodes. found on the leaf nodes.

4 Deletion of internal nodes are so complicated and time Deletion will never be a comp
consuming. element will always be deleted f

5 Leaf nodes can not be linked together. Leaf nodes are linked together
operations more efficient.

Insertion in B+ Tree
Step 1: Insert the new node as a leaf node

Step 2: If the leaf doesn't have required space, split the node and copy the middle
node to the next index node.

Step 3: If the index node doesn't have required space, split the node and copy the
middle element to the next index page.

Example :
Insert the value 195 into the B+ tree of order 5 shown in the following figure.

195 will be inserted in the right sub-tree of 120 after 190. Insert it at the desired
position.

The node contains greater than the maximum number of elements i.e. 4, therefore split
it and place the median node up to the parent.
Now, the index node contains 6 children and 5 keys which violates the B+ tree
properties, therefore we need to split it, shown as follows.

Deletion in B+ Tree
Step 1: Delete the key and data from the leaves.

Step 2: if the leaf node contains less than minimum number of elements, merge down
the node with its sibling and delete the key in between them.

Step 3: if the index node contains less than minimum number of elements, merge the
node with the sibling and move down the key in between them.

Example
Delete the key 200 from the B+ Tree shown in the following figure.

200 is present in the right sub-tree of 190, after 195. delete it.
Merge the two nodes by using 195, 190, 154 and 129.

Now, element 120 is the single element present in the node which is violating the B+
Tree properties. Therefore, we need to merge it by using 60, 78, 108 and 120.

Now, the height of B+ tree will be decreased by 1.