AVL tree in data structure in hindi, avl tree in hindi, AVL tree kya hai,
- avl tree in data structure in hindi,
- Balance Factor (k) = height (left(k)) – height (right(k)),
- Complexity,
- Operations on AVL tree in hindi,
- Why AVL Tree? in hindi,
AVL Tree in Data Structure in Hindi
AVL tree का आविष्कार GM Adelson – Velsky और EM Landis ने 1962 में किया था। इस tree का नाम इसके आविष्कारकों के सम्मान में AVL रखा गया है।
AVL tree को height balanced binary search tree के रूप में परिभाषित किया जा सकता है, जिसमें प्रत्येक नोड एक balance factor से जुड़ा होता है, जिसकी गणना उसके right sub-tree से उसके left sub-tree की ऊंचाई घटाकर की जाती है।
Tree को संतुलित कहा जाता है यदि प्रत्येक नोड का balance factor -1 से 1 के बीच है, अन्यथा, tree असंतुलित हो जाएगा और संतुलित करने की आवश्यकता होगी।
Balance Factor (k) = height (left(k)) – height (right(k))
यदि किसी नोड का balance factor 1 है, तो इसका मतलब है कि left sub tree, राइट सब-ट्री से एक level high है।
यदि किसी नोड का balance factor 0 है, तो इसका मतलब है कि left sub-tree और right sub-tree में समान ऊंचाई है।
अगर किसी भी नोड का balance factor -1 है, तो इसका मतलब है कि left sub-tree, right sub-tree से एक level कम है।
एक AVL tree निम्नलिखित आकृति में दिया गया है। हम देख सकते हैं कि, प्रत्येक नोड के साथ जुड़े balance factor -1 और +1 के बीच है। इसलिए, यह AVL tree का एक उदाहरण है।
Complexity
| Algorithm | Average case | Worst case |
| Space | o(n) | o(n) |
| Search | o(log n) | o(log n) |
| Insert | o(log n) | o(log n) |
| Delete | o(log n) | o(log n) |
Operations on AVL tree
इस तथ्य के कारण कि, AVL tree भी एक binary search tree है इसलिए, सभी ऑपरेशन उसी तरह से किए जाते हैं जैसे वे एक binary search tree में किए जाते हैं।
| S.N. | Operation | Description |
| 1 | Insertion | AVL tree में insertion उसी तरह से की जाती है जैसे कि Binary search tree में की जाती है। हालांकि, यह AVL tree की property में उल्लंघन का कारण बन सकता है और इसलिए tree को संतुलन की आवश्यकता हो सकती है। trees को rotation लगाकर balance किया जा सकता है। |
| 2 | Deletion | Deletion उसी तरह से किया जा सकता है जैसे कि एक binary search tree में किया जाता है। deletion tree के संतुलन को भी बिगाड़ सकता है, इसलिए tree के rebalancing के लिए विभिन्न प्रकार के rotations का उपयोग किया जाता है। |
Why AVL Tree ?
AVL tree binary search tree की height को तिरछा नहीं होने देकर नियंत्रित करता है। height h के binary search tree में सभी operations के लिए लिया गया समय O (h) है । हालाँकि, इसे O (n) तक बढ़ाया जा सकता है यदि BST तिरछा हो जाता है (यानी सबसे खराब स्थिति)। log n करके इस ऊंचाई को सीमित करके, AVL tree O (log n) होने के लिए प्रत्येक ऑपरेशन पर एक ऊपरी बाउंड लगाता है जहां नोड्स की संख्या n है।
