Scribd
Upload
4 views1 page

AVL Tree Advanced Data Structure With Example

An AVL Tree is a self-balancing Binary Search Tree that maintains a balance factor of at most 1 for each node, requiring rotations when this condition is violated. Key operations such as insertion, deletion, and search all have a time complexity of O(log n), making AVL Trees efficient for various applications like database indexing and memory management. The tree structure ensures faster searching compared to normal BSTs due to its strict balance.

Uploaded by

lingalamounika555
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views1 page

AVL Tree Advanced Data Structure With Example

An AVL Tree is a self-balancing Binary Search Tree that maintains a balance factor of at most 1 for each node, requiring rotations when this condition is violated. Key operations such as insertion, deletion, and search all have a time complexity of O(log n), making AVL Trees efficient for various applications like database indexing and memory management. The tree structure ensures faster searching compared to normal BSTs due to its strict balance.

Uploaded by

lingalamounika555
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

AVL Tree - Advanced Data Structure (With

Example)

1. Introduction:
An AVL Tree is a self-balancing Binary Search Tree (BST) where the difference between heights of
left and right subtrees (Balance Factor) is at most 1 for every node. If the balance factor becomes
less than -1 or greater than +1, rotations are performed.

2. Balance Factor:
Balance Factor = Height of Left Subtree - Height of Right Subtree
Possible values: -1, 0, +1

3. Rotations in AVL Tree:


1. LL Rotation (Right Rotation)
2. RR Rotation (Left Rotation)
3. LR Rotation (Left-Right Rotation)
4. RL Rotation (Right-Left Rotation)

4. Example of Insertion:
Insert elements: 10, 20, 30 Step 1: Insert 10 (Root node)
Step 2: Insert 20 (Right of 10)
Step 3: Insert 30 (Right of 20)
Now the tree becomes unbalanced at node 10 (RR case).
Perform Left Rotation at node 10. After Rotation:
20
/\
10 30
Tree becomes balanced.

5. Operations:
Insertion: O(log n)
Deletion: O(log n)
Search: O(log n)

6. Advantages:
• Maintains strict balance
• Faster searching than normal BST
• Height is always O(log n)

7. Applications:
• Database indexing
• Dictionary implementation
• Memory management systems

You might also like