AVL (Adelson, Velski and Landis) tree

AVL tree:-

Named after their inventor Adelson, Velski & Landis, AVL trees are height balancing binary search tree in which the difference between heights of left and right subtrees cannot be more than one for all nodes. This difference is called the Balance Factor, it stores value among 1,0,-1.

AVL ट्री का नाम, उसके निर्माताओं एडेलसन, वेलस्की एवं लेण्डीस के नाम पर रखा गया है। यह एक हाइट बैलेंस बाइनरी सर्च ट्री होता है जिसमे किसी ट्री के लेफ्ट सब ट्री एवं राइट सब ट्री की उचाईयो में अंतर 1 से अधिक नहीं होता है। इस अंतर को बैलेंस फैक्टर कहा जाता है इसका मान 1 ,0 या -1 हो सकता है।       

Balance Factor of each node= height of left-subtree - height of right-subtree

प्रत्येक नोड का बैलेंस फैक्टर= लेफ्ट सब ट्री की उचाई - राइट सब ट्री की उचाई

1.) If height of left sub tree is one more than height of right subtree of a node then balance factor of  that node is 1.

यदि किसी नोड के लेफ्ट सब ट्री की उचाई , राइट सब ट्री की उचाई से एक अधिक होती है तब उस नोड का बैलेंस फैक्टर 1 होता है।   

2.) If height of right sub tree is one more than height of left subtree of a node then balance factor of  that node is -1 and

यदि किसी नोड के राइट सब ट्री की उचाई , लेफ्ट सब ट्री की उचाई से एक अधिक होती है तब उस नोड का बैलेंस फैक्टर -1 होता है।   

3.) If height of left sub tree is equal to height of right subtree of a node then balance factor of that node is 0. Consider following diagram-

यदि किसी नोड के लेफ्ट सब ट्री की उचाई , राइट सब ट्री की उचाई के बराबर होती है तब उस नोड का बैलेंस फैक्टर 0  होता है। इसे निम्न चित्र द्वारा समझा जा सकता है -

If AVL tree is not balance then it may perform the following four kinds of rotations to balance itself-

यदि AVL ट्री बैलेंस्ड नहीं होता है तब यह निम्न चार में से एक रोटेशन कर स्वयं को बैलेंस करता है -

1.) Left rotation (लेफ्ट रोटेशन) 

2.) Right rotation (राइट रोटेशन)

3.)Left-Right rotation (लेफ्ट-राइट रोटेशन)

4.) Right-Left rotation (राइट-लेफ्ट रोटेशन)