Data structures की दुनिया में, binary search trees (BST) बहुत महत्वपूर्ण होते हैं, लेकिन जब BST unbalanced हो जाता है, तब उसकी performance degrade हो जाती है। इसी problem को solve करने के लिए AVL Tree introduce किया गया। AVL Tree एक self-balancing binary search tree है, जो हर insertion और deletion के बाद खुद को balance रखता है।

 

AVL Tree क्या है? - AVL Tree in Hindi

 

AVL Tree एक balanced binary search tree है, जिसका नाम इसके inventors Adelson-Velsky और Landis के नाम पर रखा गया है। AVL Tree की खासियत यह है कि यह अपने हर node के left और right subtree की height को balance रखता है, ताकि tree कभी unbalanced न हो।

 

AVL Tree की Properties:

 

1. यह एक binary search tree (BST) है।

2. हर node का height balance factor (-1, 0, या 1) के बीच होना चाहिए।

3. अगर balance factor इस range से बाहर चला जाता है, तो tree को rotations द्वारा balance किया जाता है।

 

Balance Factor क्या है? - What is Balance Factor in AVL Tree

 

Balance Factor को node के left और right subtree की heights का difference कहा जाता है।

 

Balance Factor = Height of Left Subtree − Height of Right Subtree

 

Balance factor values:

 

1. -1: Right subtree taller है।

2. 0: Left और Right subtree balanced हैं।

3. 1: Left subtree taller है।

 

अगर balance factor -1, 0, या 1 के अलावा कुछ और हो जाता है, तो tree को balancing की ज़रूरत होती है, जिसे हम rotations द्वारा achieve करते हैं।

 

AVL Tree Operations in Data Structure

 

1. Insertion

Insertion AVL Tree में ठीक उसी प्रकार होती है जैसे binary search tree में होती है, लेकिन एक extra step के साथ। हर new node insert होने के बाद, हमें tree का balance check करना होता है। अगर balance factor -1, 0, या 1 से बाहर हो जाता है, तो rotations की मदद से tree को फिर से balance किया जाता है।

 

Rotations:

AVL Tree में balance बनाए रखने के लिए चार प्रकार की rotations होती हैं:

• Left Rotation (LL)

• Right Rotation (RR)

• Left-Right Rotation (LR)

• Right-Left Rotation (RL)

 

2. Deletion

Deletion AVL Tree में थोड़ा complex होता है। पहले node को delete किया जाता है, फिर deletion के बाद हर ancestor node का balance factor check किया जाता है। अगर tree unbalanced हो जाता है, तो उसी तरह से rotations का इस्तेमाल किया जाता है जैसे insertion के case में किया गया था।

 

Rotations in AVL Tree in Hindi

 

AVL Tree की balancing rotations को समझने के लिए चार मुख्य cases होते हैं:

 

1. Left-Left (LL) Rotation:

जब किसी subtree का balance factor +2 हो और उसके left child का balance factor +1 हो, तो LL rotation किया जाता है। इसमें हम root को right rotate करते हैं।

 

2. Right-Right (RR) Rotation:

जब किसी subtree का balance factor -2 हो और उसके right child का balance factor -1 हो, तो RR rotation किया जाता है। इसमें हम root को left rotate करते हैं।

 

3. Left-Right (LR) Rotation:

यह तब किया जाता है जब subtree का balance factor +2 हो लेकिन left child का balance factor -1 हो। सबसे पहले left child को left rotate किया जाता है और फिर root को right rotate किया जाता है।

 

4. Right-Left (RL) Rotation:

जब subtree का balance factor -2 हो और right child का balance factor +1 हो, तब पहले right child को right rotate किया जाता है और फिर root को left rotate किया जाता है।

 

---

 

AVL Tree Example

 

मान लीजिए कि हमें AVL Tree में 10, 20, 30, 40, 50, 25 elements को insert करना है। नीचे दिए गए steps को follow करके हम tree को balanced रखेंगे:

1. 10 को insert करें। यह पहला node है, तो balance factor 0 रहेगा।

2. 20 को insert करें। Balance factor -1 हो जाएगा, लेकिन tree अब भी balanced है।

3. 30 को insert करने पर balance factor -2 हो जाएगा, तो हमें LL rotation करनी पड़ेगी।

4. इसी प्रकार, हर insertion के बाद tree का balance factor check करें और अगर tree unbalanced हो तो proper rotation का उपयोग करें।

 

AVL Tree Advantages in Hindi

 

1. Self-Balancing: AVL Tree insertion और deletion के बाद खुद को balance रखता है, जिससे operations efficient रहते हैं।

2. Fast Searching: AVL Tree balanced होने के कारण searching में O(log n) time complexity मिलती है, जो BST की average complexity से बेहतर है।

3. Efficient Rotations: Rotations की मदद से tree को आसानी से balance किया जा सकता है।

 

Conclusion

 

AVL Tree एक powerful data structure है जो binary search tree की limitations को overcome करता है। इसकी self-balancing property इसे बहुत ही efficient बनाती है, खासकर जब frequent insertion और deletion operations की ज़रूरत हो। Rotations का सही understanding आपको tree को हमेशा balanced रखने में मदद करेगा। अगर आपको AVL Tree के बारे में और सवाल हों, तो comment section में पूछें!