एवीएल पेड़ को यथासंभव लापरवाही के रूप में कैसे उत्पन्न करें?

Question

मैंने इसे कुछ पेपर में देखा और किसी ने तर्क दिया कि जब हम एवीएल पेड़ के नोड को हटाते हैं तो अधिकांश लॉग (एन) बार घूर्णन हो सकते हैं। मेरा मानना ​​है कि हम एक एवीएल पेड़ को यथासंभव लापरवाही के रूप में उत्पन्न करके इसे प्राप्त कर सकते हैं। समस्या यह है कि यह कैसे करें। इससे मुझे हटाने की रोटेशन चीज की खोज करने में बहुत मदद मिलेगी। बहुत बहुत धन्यवाद!

Answer 1

आप एक अधिकतम एकतरफा AVL पेड़ बनाना चाहते हैं, तो आप एक Fibonacci tree, जो उपपादन द्वारा परिभाषित किया गया है इस प्रकार के लिए देख रहे हैं:

• एक फाइबोनैचि आदेश 0 के वृक्ष खाली है।
• ऑर्डर 1 का एक फाइबोनैकी पेड़ एक एकल नोड है।
आदेश n + 2 की
• एक फाइबोनैचि पेड़ एक नोड जिसका बाईं बच्चे आदेश n और जिसका सही बच्चे का एक फाइबोनैचि पेड़ है n आदेश की एक फाइबोनैचि पेड़ + 1.

उदाहरण के लिए है, यहाँ एक फाइबोनैचि है आदेश 5 के पेड़:

फाइबोनैचि पेड़, तिरछा की अधिकतम राशि एक AVL पेड़ हो सकता है प्रतिनिधित्व करते हैं के बाद से रखा करता है, तो संतुलन कारक किसी भी अधिक एकतरफा प्रत्येक नोड के संतुलन कारक सीमाएं पार हो जाएंगी थे एवीएल पेड़ों द्वारा।

आप बहुत आसानी से अधिकतम एकतरफा AVL पेड़ उत्पन्न करने के लिए इस परिभाषा का उपयोग कर सकते हैं:

function FibonacciTree(int order) { 
    if order = 0, return the empty tree. 
    if order = 1, create a single node and return it. 
    otherwise: 
     let left = FibonacciTree(order - 2) 
     let right = FibonacciTree(order - 1) 
     return a tree whose left child is "left" and whose right child is "right." 

आशा इस मदद करता है!