AVL TREE

An AVL Tree is a type of self-balancing binary search tree (BST) where the
difference between the heights of the left and right subtrees (also known as the
balance factor) of any node is no more than one. This ensures that the tree
remains balanced, allowing for operations like search, insertion, and deletion to
be performed in O(log n) time.

Table of Contents

1. Introduction to AVL Tree

2. Properties of AVL Tree
3. AVL Tree Rotations
o Single Right Rotation (LL)
o Single Left Rotation (RR)
o Double Left-Right Rotation (LR)
o Double Right-Left Rotation (RL)
4. Insertion in AVL Tree
5. Deletion in AVL Tree
6. Time Complexity
7. Applications of AVL Trees

1. Introduction to AVL Tree

 Named after its inventors: Adelson-Velsky and Landis, who introduced the
concept in 1962.
 An AVL tree is a balanced binary search tree where the height of the subtrees of
a node differs by at most 1.
 Balance is ensured by performing rotations on nodes after insertion or deletion
when necessary.

Balance Factor:
For any node in the AVL tree:

Balance Factor=Height of Left Subtree−Height of Right Subtree\text{Balance

Factor} = \text{Height of Left Subtree} - \text{Height of Right
Subtree}Balance Factor=Height of Left Subtree−Height of Right Subtree

 Balance Factor = 0: Perfectly balanced subtree.

 Balance Factor = +1: Left subtree is taller by one.
 Balance Factor = -1: Right subtree is taller by one.
 If the balance factor becomes greater than 1 or less than -1, the tree needs
rebalancing using rotations.

2. Properties of AVL Tree

1. Binary Search Tree Property: The left subtree contains nodes with values less
than the node, and the right subtree contains nodes with values greater than the
node.
2. Height-Balanced: For every node, the difference between the heights of the left
and right subtrees (balance factor) is either -1, 0, or +1.
3. Height: For an AVL tree with n nodes, the height is bounded by:
h≤1.44log 2(n)

This ensures logarithmic time complexity for insertion, deletion, and lookup
operations.

3. AVL Tree Rotations

Rotations are used to rebalance the AVL tree when the balance factor condition is
violated after insertion or deletion. There are four types of rotations:

A. Single Right Rotation (LL Rotation)

 Used when: A node is inserted into the left subtree of the left child of a node,
causing an imbalance.
 Action: Perform a right rotation on the unbalanced node.

Example:
markdown

30
/
20
/
10

Right rotation on node 30:

markdown
 20
/ \
10 30

B. Single Left Rotation (RR Rotation)

 Used when: A node is inserted into the right subtree of the right child of a node,
causing an imbalance.
 Action: Perform a left rotation on the unbalanced node.

Example:
markdown

10
\
20
\
30

Left rotation on node 10:

markdown

20
/ \
10 30

C. Double Left-Right Rotation (LR Rotation)

 Used when: A node is inserted into the right subtree of the left child of a node,
causing an imbalance.
 Action: First, perform a left rotation on the left child, then perform a right
rotation on the unbalanced node.

Example:
markdown

30
/
10
\
20

First, left rotation on node 10, then right rotation on node 30:
markdown

20
/ \
10 30
 D. Double Right-Left Rotation (RL Rotation)

 Used when: A node is inserted into the left subtree of the right child of a node,
causing an imbalance.
 Action: First, perform a right rotation on the right child, then perform a left
rotation on the unbalanced node.

Example:
markdown

10
\
30
/
20

First, right rotation on node 30, then left rotation on node 10:
markdown

20
/ \
10 30

4. Insertion in AVL Tree

1. Perform BST Insertion: Insert the node as you would in a normal binary search
tree.
2. Update Heights: After insertion, update the height of the nodes.
3. Check Balance Factor: For each ancestor of the inserted node, check if the
balance factor is still within the acceptable range (-1, 0, 1).
4. Rebalance if needed: If a node becomes unbalanced, perform one of the four
rotations (LL, RR, LR, RL) to restore balance.

Example:
Insert 10 into the following AVL tree:
markdown

20
/ \
15 30

After inserting 10:

markdown

20
/ \
 15 30
/
10

Now, node 20 has a balance factor of 2 (left subtree height = 2, right subtree
height = 1), so a right rotation (LL rotation) is performed on node 20:
markdown

15
/ \
10 20
\
30

5. Deletion in AVL Tree

1. Perform BST Deletion: Delete the node as you would in a regular BST.
2. Update Heights: After deletion, update the height of the affected nodes.
3. Check Balance Factor: For each ancestor of the deleted node, check the balance
factor.
4. Rebalance if needed: If a node becomes unbalanced, perform one of the
rotations (LL, RR, LR, RL) to restore balance.

Example:
Delete 10 from the following AVL tree:
markdown

15
/ \
10 20
\
30

After deletion:
markdown

15
\
20
\
30

Node 15 now has a balance factor of -2, so a left rotation (RR rotation) is
performed on node 15:
markdown

20
 / \
15 30

6. Time Complexity of AVL Tree Operations

Operation Time Complexity

Search O(log n)
Insertion O(log n)
Deletion O(log n)

 The time complexity of these operations is logarithmic because the AVL tree
remains balanced, keeping its height proportional to O(log n).

7. Applications of AVL Trees

 Databases: AVL trees are used where quick lookups and updates are required,
such as indexing.
 Memory management: In dynamic memory allocation systems, AVL trees help
manage free blocks of memory efficiently.
 Multimedia search systems: Used to search for media by certain properties
efficiently.
 Compiler design: Helps in symbol table construction and management.

Summary

 AVL Tree is a balanced binary search tree that ensures operations like search,
insertion, and deletion occur in logarithmic time by maintaining a balance factor
at each node.
 When balance is disturbed due to insertion or deletion, rotations (single or
double) are performed to restore the balance.
 It is particularly useful in applications where read-heavy operations need to be
performed efficiently.

This covers the full concept of AVL trees with a focus on understanding how
balance is maintained and why it's crucial for the efficiency of tree-based data
structures.