Height balanced tree or AVL TREE
AVL TREE एक self balancing binary search tree होती है। AVL TREE को height balanced tree भी कहा जाता है। AVL TREE का नाम इसके inventors( Georgy Adelson-Velsky और Evgenii Landis ) के कारण पड़ा। AVL TREE का प्रयोग डेटा को organise करने के लिए किया जाता है। यदि AVL TREE के N nodes हैं, तो इसकी height log2 (N + 1) होगी।
एक Binary tree तब height balanced होगी जब वह निम्नलिखित rules को satisfy करेगी:-
- यदि Binary tree का left subtree balanced हो।
2. यदि Binary tree का right subtree balanced हो।
3. और, Right subtree की height तथा left subtree की height के मध्य अंतर1 से अधिक नही होना चाहिए। एक empty tree भी height balanced tree होती है।
Application Of Binary Tree
- बाइनरी सर्च ट्री का प्रयोग बहुत सारीं सर्च applications में किया जाता है।
2. Binary Space Partition का प्रयोग आजकल प्रत्येक 3D गेम्स के लिए किया जाता है।
3. बाइनरी tries का प्रयोग प्रत्येक हाई बैंडविड्थ राऊटर में किया जाता है जो कि राऊटर टेबल्स को स्टोर करता है।
4. Heaps का प्रयोग queues में इम्प्लीमेंट करने के लिए किया जाता है। रोबोटिक्स तथा वीडियो गेम्स में भी इसका प्रयोग किया जाता है।
5. Huffman coding tree का प्रयोग compression algorithms(जैसे-.jpeg तथा .mp3) में किया जाता है।
6. GMG trees का प्रयोग cryptography applications में pseudo-random numbers को generate करने के लिए किया जाता है।
7. Treap का प्रयोग वायरलेस नेटवर्किंग तथा मेमोरी एलोकेशन में किया जाता है।
8. T-tree का प्रयोग डेटाबेस में B-tree की तरह डेटा को स्टोर करने के लिए किया जाता है।