Let us consider that we want to delete node having value 7.

We will then find out the inorder successor

of node 7. We will then find out the inorder successor of node 7. The inorder successor will be simply
copied at location of node 7.
That means copy 8 at the position where value of node is 7. Set left pointer of 9 as NULL. This
completes the deletion procedure.

Searching for a node in binary search tree.

In searching, the node which we want to search is called a key node. The key node will be compared
with each node starting from root node if value of key node is greater than current node then we
search for it on right sub branch otherwise on left sub branch. If we reach to leaf node and still we do
not get the value of key node then we declare “node is not present in the tree”.

125
In the above tree, if we want to search for value 9. Then we will compare 9 with root node 10. As 9 is
less than 10 we will search on left sub branch. Now compare 9 with 5, but 9 is greater than 5. So we
will move on right sub tree. Now compare 9 with 8 but 9 is greater than 8 we will move on right sub
branch. As the node we will get holds the value 9. Thus the desired node can be searched.

AVL TREES
Adelsion Velski and Lendis in 1962 introduced binary tree structure that is balanced with
respect to height of sub trees. The tree can be made balanced and because of this retrieval
of any node can be done in Ο(log n) times, where n is total number of nodes. From the
name of these scientists the tree is called AVL tree.

Definition:

An empty tree is height balanced if T is a non empty binary tree with T L and TR as
its left and right sub trees. The T is height balanced if and only if
i. TL and TR are height balanced.
ii. hL-hR <= 1 where hL and hR are heights of TL and TR.
The idea of balancing a tree is obtained by calculating the balance factor of a tree.

Definition of Balance Factor:

The balance factor BF(T) of a node in binary tree is defined to be hL-hR where hL and hR
are heights of left and right sub trees of T.

For any node in AVL tree the balance factor i.e. BF(T) is -1, 0 or +1.

126
Height of AVL Tree:
Theorem: The height of AVL tree with n elements (nodes) is O(log n).

Proof: Let an AVL tree with n nodes in it. Nh be the minimum number of nodes in an AVL tree of
height h.

In worst case, one sub tree may have height h-1 and other sub tree may have height h-2. And both these
sub trees are AVL trees. Since for every node in AVL tree the height of left and right sub trees differ
by at most 1.

Hence

Nh = Nh-1+Nh-2+1

Where Nh denotes the minimum number of nodes in an AVL tree of height h.

N0=0 N1=2

127
We can also write it as
N > Nh = Nh-1+Nh-2+1

> 2Nh-2

> 4Nh-4
.
.
> 2iNh-2i

If value of h is even, let i = h/2-1

Then equation becomes

N > 2h/2-1N2

= N > 2(h-1)/2x4 (N2 = 4)

= O(log N)

If value of h is odd, let I = (h-1)/2 then equation becomes

N > 2(h-1)/2 N1
N > 2(h-1)/2 x 1
H = O(log N)

This proves that height of AVL tree is always O(log N). Hence search, insertion and deletion can
be carried out in logarithmic time.

Representation of AVL Tree

 The AVL tree follows the property of binary search tree. In fact AVL trees are
basically binary search trees with balance factors as -1, 0, or +1.
 After insertion of any node in an AVL tree if the balance factor of any node
becomes other than -1, 0, or +1 then it is said that AVL property is violated. Then
we have to restore the destroyed balance condition. The balance factor is denoted at
right top corner inside the node.

128
  After insertion of a new node if balance condition gets destroyed, then the nodes on that
path(new node insertion point to root) needs to be readjusted. That means only the affected sub
tree is to be rebalanced.
 The rebalancing should be such that entire tree should satisfy AVL property.
In above given example-

129
Insertion of a node.

There are four different cases when rebalancing is required after insertion of new node.

1. An insertion of new node into left sub tree of left child. (LL).
2. An insertion of new node into right sub tree of left child. (LR).
3. An insertion of new node into left sub tree of right child. (RL).
4. An insertion of new node into right sub tree of right child.(RR).

Some modifications done on AVL tree in order to rebalance it is called rotations of AVL tree

There are two types of rotations:

Single rotation Double rotation

Left-Left(LL rotation) Left-Right(LR rotation)

Right-Right(RR rotation) Right-Left(RL rotation)

Insertion Algorithm:
1. Insert a new node as new leaf just as an ordinary binary search tree.
2. Now trace the path from insertion point(new node inserted as leaf) towards root. For each node
‘n’ encountered, check if heights of left (n) and right (n) differ by at most 1.
a) If yes, move towards parent (n).
b) Otherwise restructure by doing either a single rotation or a double rotation.
Thus once we perform a rotation at node ‘n’ we do not require to perform any rotation at any
ancestor on ‘n’.

130
When node ‘1’ gets inserted as a left child of node ‘C’ then AVL property gets destroyed i.e. node
A has balance factor +2.
The LL rotation has to be applied to rebalance the nodes.

2. RR rotation:

When node ‘4’ gets attached as right child of node ‘C’ then node ‘A’ gets unbalanced. The rotation
which needs to be applied is RR rotation as shown in fig.

131
When node ‘3’ is attached as a right child of node ‘C’ then unbalancing occurs because of LR.
Hence LR rotation needs to be applied.

When node ‘2’ is attached as a left child of node ‘C’ then node ‘A’ gets unbalanced as its balance
factor becomes -2. Then RL rotation needs to be applied to rebalance the AVL tree.
Example:

Insert 1, 25, 28, 12 in the following AVL tree.

132
Insert 1

To insert node ‘1’ we have to attach it as a left child of ‘2’. This will unbalance the tree as follows.
We will apply LL rotation to preserve AVL property of it.

Insert 25

We will attach 25 as a right child of 18. No balancing is required as entire tree preserves the AVL
property

133
Insert 28
The node ‘28’ is attached as a right child of 25. RR rotation is required to rebalance.

134
Insert 12

To rebalance the tree we have to apply LR rotation.

135
Deletion:

Even after deletion of any particular node from AVL tree, the tree has to be restructured in order to
preserve AVL property. And thereby various rotations need to be applied.

Algorithm for deletion:

The deletion algorithm is more complex than insertion algorithm.

1. Search the node which is to be deleted.
2. a) If the node to be deleted is a leaf node then simply make it NULL to remove.
b) If the node to be deleted is not a leaf node i.e. node may have one or two children, then the
node must be swapped with its inorder successor. Once the node is swapped, we can remove
this node.
3. Now we have to traverse back up the path towards root, checking the
balance factor of every node along the path. If we encounter unbalancing
in some sub tree
then balance that sub tree using appropriate single or double
rotations. The deletion algorithm takes O(log n) time to delete any node.

136
The tree becomes

137
Searching:

The searching of a node in an AVL tree is very simple. As AVL tree is basically binary search tree, the
algorithm used for searching a node from binary search tree is the same one is used to search a node
from AVL tree.

The searching of a node from AVL tree takes O(log n) time.

BTREES
 Multi-way trees are tree data structures with more than two branches at a node. The data
structures of m-way search trees, B trees and Tries belong to this category of tree
structures.
 AVL search trees are height balanced versions of binary search trees, provide efficient
retrievals and storage operations. The complexity of insert, delete and search operations on
AVL search trees id O(log n).
 Applications such as File indexing where the entries in an index may be very large,
maintaining the index as m-way search trees provides a better option than AVL search trees
which are but only balanced binary search trees.
 While binary search trees are two-way search trees, m-way search trees are extended binary
search trees and hence provide efficient retrievals.
 B trees are height balanced versions of m-way search trees and they do not recommend
representation of keys with varying sizes.
 Tries are tree based data structures that support keys with varying sizes.

138