Adelson-Velsky and Landis Tree / AVL Tree
Adelson-Velsky and Landis Tree / AVL Tree दो रूसी वैज्ञानिक G. M. Adelson-Velsky and E. M. Landis के नाम पर रखा गया है | इन्होंने 1962 में पहला self-balancing binary search tree introduce किया था, जिसे आज हम AVL Tree कहते हैं।
AVL Tree एक Self-Balancing Binary Search Tree है, जिसमें हर node के left और right subtree की height का अंतर (Balance Factor) हमेशा –1, 0 या +1 के बीच रहता है। इसी height difference को Balance Factor (BF) कहते हैं |
Balance Factor = height (left subtree) – height (right subtree)
Possible values : {–1}, {0}, {+1}
- BF < –1 → Right Heavy → Rotation needed
- BF > +1 → Left Heavy → Rotation needed
अगर किसी भी node का Balance Factor इस range से बाहर चला जाए , तो AVL Tree rotation करके अपने आप balanced हो जाता है।
Why AVL Tree is Needed? (AVL ट्री की आवश्यकता क्यों है?)
- Binary Search Tree को balanced रखना बहुत ज़रूरी है, जिससे searching, insertion और deletion जैसे operations हर बार fast, (O(log n)) में perform हों।
- Normal BST में एक बड़ी समस्या होती है — अगर data sorted order में insert कर दिया जाए, तो पूरा tree एक लंबी सी linked list जैसा बन सकता है। जिससे time complexity O(n) हो जाती है।
- इसी problem को solve करने के लिए AVL Tree बनाया गया। यह अपनी rotations की मदद से tree को अपने-आप balance कर देता है, जिससे worst case में भी performance खराब नहीं होती और पूरा tree हमेशा structured व efficient बना रहता है।
Features of AVL Tree (AVL Tree की मुख्य विशेषताएँ)
1. Self-Balancing Property
- AVL Tree हमेशा अपने आप balanced रहता है।
- हर node का balance factor सिर्फ {–1}, {0} या {+1} की range में रहता है।
2. Height Control (Minimum Height Tree)
- AVL Tree की height हमेशा O(log n) के लगभग रहती है। इससे searching, insertion और deletion बहुत fast होते हैं।
3. Fast Searching
- tree balanced है, इसलिए searching हमेशा logarithmic time लेती है।
- यह normal BST की तुलना में काफी तेज है।
4. Rotations for Balancing
- अगर tree unbalanced हो जाए, तो इसे balance करने के लिए 4 types की rotations प्रयोग होती हैं :
- LL Rotation
- RR Rotation
- LR Rotation
- RL Rotation
5. Strictly Balanced Structure
- AVL Tree, Red-Black Tree की तुलना में ज्यादा strictly balanced रहता है।
- इसलिए इसकी searching सबसे fast मानी जाती है।
6. Predictable Performance
- चूंकि height कभी बहुत ज्यादा नहीं बढ़ती, इसलिए AVL Tree की performance stable और predictable रहती है।
7. Ordered Data Storage
- Binary Search Tree की तरह AVL Tree भी data को sorted order में store करता है। इससे traversals (Inorder, Preorder, Postorder) आसान और useful बनते हैं।
8. Suitable for Search-Intensive Applications
- AVL Tree उन situations में बहुत useful है, जहां बार-बार searching करनी होती है — जैसे databases, memory lookup, file systems, आदि।
Types of Rotations in AVL Tree (AVL Tree में Rotations के प्रकार)
AVL Tree में Rotations दो तरह की होती हैं :
- Single Rotation (LL, RR)
- Double Rotation (LR, RL)
1. LL Rotation (Left-Left Rotation)
जब node का left subtree left-heavy हो, यानी left child के left subtree की height ज्यादा हो।
Balance Factor :
- Unbalanced node का BF = +2
- Left child का BF = +1
Solution : Right Rotation on unbalanced node
Step-by-Step Example : Insert order : 30, 20, 10
Step 1 : Normal BST insert
30
/
20
/
10
Step 2 : Check Balance Factor
- BF(30) = height(Left) – height(Right) = 2 – 0 = +2 → Unbalanced
- BF(20) = +1 → Left-heavy
Step 3 : Right Rotation at 30
20
/ \
10 30
2. RR Rotation (Right-Right Rotation)
जब node का right subtree right-heavy हो, यानी right child के right subtree की height ज्यादा हो।
Balance Factor :
- Unbalanced node BF = –2
- Right child BF = –1
Solution : Left Rotation on unbalanced node
Step-by-Step Example : Insert order : 10, 20, 30
Step 1: Normal BST insert
10
\
20
\
30
Step 2 : Check Balance Factor
- BF(10) = height(Left) – height(Right) = 0 – 2 = –2 → Unbalanced
- BF(20) = –1 → Right-heavy
Step 3 : Left Rotation at 10
20
/ \
10 30
3. LR Rotation (Left-Right Rotation)
जब node का left child right-heavy हो, यानी left child के right subtree की height ज्यादा हो।
Balance Factor :
- Unbalanced node BF = +2
- Left child BF = –1
Solution : Double Rotation
- Left Rotation on left child
- Right Rotation on unbalanced node
Step-by-Step Example : Insert order : 30, 10, 20
Step 1 : Normal BST insert
30
/
10
\
20
Step 2 : Check Balance Factor
- BF(30) = +2 → Unbalanced
- BF(10) = –1 → Left child right-heavy
Step 3 : Perform Rotations
- Left Rotation on 10 → Makes 20 as new left child
30
/
20
/
10
- Right Rotation on 30 → Makes 20 as root
20
/ \
10 30
4. RL Rotation (Right-Left Rotation)
जब node का right child left-heavy हो, यानी right child के left subtree की height ज्यादा हो।
Balance Factor :
- Unbalanced node का BF = –2
- Right child का BF = +1
Solution : Double Rotation
- Right Rotation on right child
- Left Rotation on unbalanced node
Step-by-Step Example : Insert order : 10, 30, 20
Step 1 : Normal BST insert
10
\
30
/
20
Step 2 : Check Balance Factor
- BF(10) = –2 → Unbalanced
- BF(30) = +1 → Right child left-heavy
Step 3 : Perform Rotations
- Right Rotation on 30 → Makes 20 as right child
10
\
20
\
30
Left Rotation on 10 → Makes 20 as root
20
/ \
10 30
AVL Tree Operations (AVL ट्री ऑपरेशन्स)
1. AVL Tree Insertion
AVL Tree में Insertion हमेशा 3 steps में होता है :
Step 1 : BST की तरह insert करो
- Value को normal BST rules से add किया जाता है।
Step 2 : Balance Factor निकालो
- हर ancestor node का BF check करें।
Step 3 : Rotate if needed
- जिस भी node का BF –1 से कम या +1 से ज़्यादा हो → rotation।
2. AVL Tree Deletion
Deletion थोड़ा tricky है, क्योंकि height imbalance हो सकता है।
Deletion Steps :
Step 1 : Node delete करो (BST rules से)
- leaf delete
- one child delete
- two child delete → inorder successor लगाओ
Step 2 : Balance Factor निकालो
- Parent तक ऊपर जाते जाओ।
Step 3 : Appropriate rotation
- LL, RR, LR, RL — जो case बने।
3. Height of AVL Tree
Height always minimal होती है :
- O(log n)
- Balanced Tree = Fast Performance
Applications of AVL Tree (AVL Tree के उपयोग)
1. Database Indexing
- Databases जैसे MySQL, Oracle, PostgreSQL में large datasets stored होते हैं। Fast searching के लिए AVL Tree use होती है।
- Example : Student record, employee database, product catalog में indexing।
2. File Systems
- Operating System के file systems में fast file retrieval के लिए AVL Tree useful है।
- Example : Linux file system (Ext3/Ext4) में indexing structure।
3. Memory Management
- Operating System में memory blocks allocate और deallocate होते हैं।
- AVL Tree maintain करती है free memory blocks की size और address order।
- Fast allocation और deallocation के लिए perfect।
4. Compiler Design
- Variables, functions और identifiers का fast searching AVL Tree से होता है।
- Compiler efficiency बढ़ती है।
5. Networking & Routing Tables
- Router के routing tables में fast IP address search करना होता है, AVL Tree maintain करती है sorted routing entries।
- Network packet processing fast और efficient।
6. Real-Time Applications
- Banking systems, IRCTC ticket booking, airline reservation, stock market software में Fast search और consistent performance की जरूरत होती है।
- AVL Tree ensures predictable and quick operations।
Advantages of AVL Tree (लाभ)
1. Searching is always fast
- AVL Tree में nodes का balance बना रहता है। इसी वजह से किसी भी element को Search करने में ज्यादा time नहीं लगता। Search का time लगभग हमेशा O(log n) ही रहता है।
2. Insertion and deletion run smoothly
- जब भी कोई नया data insert किया जाता है, या delete होता है, tree अपने आप को balance कर लेता है। Rotations की वजह से operations जल्दी पूरे होते हैं।
3. Data retrieval is easy
- Balanced structure की वजह से traversal करना simple रहता है।
4. Reliable in real-time systems
- AVL Tree में operations predictable होते हैं, और worst-case भी O(log n) रहता है। इसलिए यह real-time systems में useful होता है, जहाँ fast response जरूरत होती है।
5. Prevents the formation of a skewed structure like a linked list
- Sorted data insert करने पर BST एक long chain बन जाता है। AVL Tree इस समस्या को होने नहीं देता और tree हमेशा balanced रहता है।
Disadvantages of AVL Tree (हानि)
1. Implementation is complex
- Normal BST की तुलना में AVL Tree समझना मुश्किल होता है, क्योंकि इसमें balance factor और rotations manage करनी पड़ती हैं।
2. Insertion and deletion involve extra work
- हर insert या delete के बाद tree को balance करना पड़ सकता है। यह balancing (rotations) extra time और processing लेती है, जबकि simple BST में यह काम नहीं करना पड़ता।
3. More memory usage
- हर node में balance factor या height store करनी पड़ती है, जिससे memory थोड़ा बढ़ जाती है।
4. Rotationsare are time-consuming
- कुछ operations में कई बार rotations करनी पड़ सकती हैं। इससे performance slow हो सकती है, especially continuous insert/delete वाले cases में।
5. Search is fast, but insertion is not as fast
- Search हमेशा O(log n) रहता है, लेकिन insertion कभी-कभी balancing की वजह से BST से slow हो सकता है।
6. Coding and debugging are hard
- Beginners के लिए AVL Tree को implement करना, errors ढूँढना या debugging करना आसान नहीं होता।
