UNIT-I

1
2
3
4
5
6
7
8
9
10
11
12
13
AVL Trees

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights
of left and right subtrees cannot be more than one for all nodes.

The tree is named after its inventors Adelson, Velski & Landis, AVL trees are height balancing
binary search tree.

AVL tree checks the height of the left and the right sub-trees and assures that the difference is
not more than |1| i.e -1,0,1. This difference is called the Balance Factor.

Balance Factor = Height(Left-subtree) − Height(Right-subtree)

If the balance factor of a node is 1, then it means that the left subtree of the tree is one level
higher than the right subtree. Such a tree is called left heavy AVL tree

If the balance factor of a node is -1, then it means that the left subtree of the tree is one level
lesser than the right subtree. Such a tree is called right heavy AVL tree

If the balance factor of a node is 0, then it means that the height of left subtree is equal to the
height of the right subtree. Such a tree is called balanced AVL tree

Operations on AVL Trees

Searching for a node in an AVL Tree

Searching in an AVL tree is performed in the same way as it is performed in a binary search
tree. Due to the height balancing of the tree, the search operation takes O(log n) time to
complete.

Inserting a New node in an AVL Tree

Insertion is also done in the same way of BST, the new node is inserted as the leaf node. But
the step of insertion is followed by an additional step of rotations. Rotation is done to restore the
balance of the tree

14
 AVL Tree Rotations

LL Rotation

The new node is inserted in the left subtree of the left subtree of the critical node

Example:

15
RR Rotation

The new node is inserted in the right subtree of the right subtree of the critical node

Example:

Solution: Right Child node becomes Parent & Parent becomes as Left Child.
Here critical node is parent node.
LR Rotation

The new node is inserted in the right sub-tree of the left sub-tree of the critical node

Solution: First make RR Rotation and then LL rotation.

Grand child becomes Parent and Parent becomes Right child. Left child is as Left child only.
16
RL Rotation

The new node is inserted in the left sub-tree of the right sub-tree of the critical node

Example:

Solution: First make LL Rotation and then RR rotation.

Grand child becomes Parent and Parent becomes Left child. Right child is as Right child only.

17
Construct an AVL Tree with the following data :

Deleting a node from AVL Tree

Deleting a node from an AVL tree is similar to that in a binary search tree. Deletion may disturb
the balance factor of an AVL tree and therefore the tree needs to be rebalanced in order to
maintain the AVLness. For this purpose, we need to perform rotations. The two types of
rotations are L rotation and R rotation. Here, we will discuss R rotations. L rotations are the
mirror images of them.

If the node which is to be deleted is present in the left sub-tree of the critical node, then L
rotation needs to be applied else if, the node which is to be deleted is present in the right sub-tree
of the critical node, the R rotation will be applied.

Let us consider that, A is the critical node and B is the root node of its left sub-tree. If node X,
present in the right sub-tree of A, is to be deleted, then there can be three different situations:
R0,R1,R-1

Ro Rotation:

If the node B has 0 balance factor, and the balance factor of node A disturbed upon deleting the
node X, then the tree will be rebalanced by rotating tree using R0 rotation.
18
Example:

Delete the node 30 from the AVL tree shown in the following image.

In this case, the node B has balance factor 0, therefore the tree will be rotated by using R0
rotation as shown in the following image. The node B(10) becomes the root, while the node A is
moved to its right. The right child of node B will now become the left child of node A.

R1 Rotation (Node B has balance factor 1)

R1 Rotation is to be performed if the balance factor of Node B is 1. In R1 rotation, the critical

node A is moved to its right having sub-trees T2 and T3 as its left and right child respectively.
T1 is to be placed as the left sub-tree of the node B.

The process involved in R1 rotation is shown in the following image.

19
Example

Delete Node 55 from the AVL tree shown in the following image.

Deleting 55 from the AVL Tree disturbs the balance factor of the node 50 i.e. node A which
becomes the critical node. This is the condition of R1 rotation in which, the node A will be
moved to its right (shown in the image below). The right of B is now become the left of A (i.e.
45).

The process involved in the solution is shown in the following image.

20
R-1 Rotation (Node B has balance factor -1)

R-1 rotation is to be performed if the node B has balance factor -1. This case is treated in the
same way as LR rotation. In this case, the node C, which is the right child of node B, becomes
the root node of the tree with B and A as its left and right children respectively.

The sub-trees T1, T2 becomes the left and right sub-trees of B whereas, T3, T4 become the left
and right sub-trees of A.

The process involved in R-1 rotation is shown in the following image.

Example:

Delete the node 60 from the AVL tree shown in the following image.

in this case, node B has balance factor -1. Deleting the node 60, disturbs the balance factor of the
node 50 therefore, it needs to be R-1 rotated. The node C i.e. 45 becomes the root of the tree with
the node B(40) and A(50) as its left and right child.

21
Applications of AVL Trees:

1) Database Indexing: AVL trees are often used to index large databases, where quick
retrieval of records is critical. The balanced nature of AVL trees ensures that the lookup time
remains logarithmic, which is essential for maintaining performance in large datasets.
2) Memory Management: In memory management, particularly in operating systems, AVL
trees can be used to manage free memory blocks. They help in efficiently allocating and
deallocating memory blocks by keeping the memory free lists balanced.
3) Routing Algorithms: In networking, AVL trees can be used in routing algorithms to
efficiently manage routing tables. The balanced structure ensures that lookup times remain
consistent, which is crucial in high-speed networks.
4) Symbol Table Management: Compilers and interpreters use symbol tables to store
information about variables, functions, classes, etc. AVL trees can be employed to manage
these symbol tables, providing fast insertion, deletion, and lookup operations.
5) File Systems: Some file systems use AVL trees to keep track of file allocation data. The
balanced nature of AVL trees helps in maintaining fast access to file blocks, improving file
system performance.
6) Scheduling Algorithms: AVL trees can be used in scheduling algorithms, where tasks need
to be managed efficiently. For example, in a priority queue, the balanced nature of an AVL
tree ensures that the highest or lowest priority task can be accessed quickly.
7) Game Development: In game development, AVL trees can be used to manage dynamic
datasets like game objects. For example, in managing a large number of game objects in a
scene, an AVL tree can help keep track of objects in a balanced manner, allowing for quick
addition, removal, or retrieval of objects.
8) Version Control Systems: AVL trees can be used in version control systems to manage
changes to code or documents efficiently. The balancing nature ensures that accessing
different versions remains quick and consistent.
9) Geographic Information Systems (GIS): In GIS, AVL trees can be used to manage spatial
data. The balance ensures efficient querying of spatial data, which is critical for applications
that require fast retrieval of geographic information.

22
B-TREES

23
24
25
26
27
28
29