एक संतुलित बाइनरी खोज पेड़ का निर्माण

Question

क्या संतुलित बाइनरी खोज पेड़ बनाने का कोई तरीका है?

उदाहरण:

1 2 3 4 5 6 7 8 9 

     5 
    /\ 
    3 etc 
    /\ 
    2 4 
/
1 

मैं सोच रहा हूँ वहाँ और अधिक जटिल आत्म संतुलन के पेड़ का उपयोग किए बिना ऐसा करने के लिए, एक विधि है। अन्यथा मैं इसे अपने आप कर सकता हूं, लेकिन किसी ने शायद यह पहले से ही किया है :)

---

उत्तर के लिए धन्यवाद!

def _buildTree(self, keys): 
    if not keys: 
     return None 

    middle = len(keys) // 2 

    return Node(
     key=keys[middle], 
     left=self._buildTree(keys[:middle]), 
     right=self._buildTree(keys[middle + 1:]) 
     ) 

Answer 1

प्रत्येक सबट्री के लिए:

• सबट्री के बीच तत्व का पता लगाएं और पेड़ के शीर्ष पर है कि डाल दिया।
• मध्य तत्व से पहले सभी तत्वों को ढूंढें और बाएं उपट्री प्राप्त करने के लिए इस एल्गोरिदम का पुनरावृत्ति उपयोग करें।
• मध्य तत्व के बाद सभी तत्व खोजें और सही उपट्री प्राप्त करने के लिए इस एल्गोरिदम का पुनरावृत्ति उपयोग करें।

यदि आप अपने तत्वों को पहले क्रमबद्ध करते हैं (जैसा कि आपके उदाहरण में) एक उपट्री के मध्य तत्व को निरंतर समय में किया जा सकता है।

यह एक-एक संतुलित पेड़ बनाने के लिए एक साधारण एल्गोरिदम है। यह आत्म-संतुलन वृक्ष के लिए एक एल्गोरिदम नहीं है।

यहाँ सी # में कुछ स्रोत कोड है कि आप खुद के लिए कोशिश कर सकते हैं:

public class Program 
{ 
    class TreeNode 
    { 
     public int Value; 
     public TreeNode Left; 
     public TreeNode Right; 
    } 

    TreeNode constructBalancedTree(List<int> values, int min, int max) 
    { 
     if (min == max) 
      return null; 

     int median = min + (max - min)/2; 
     return new TreeNode 
     { 
      Value = values[median], 
      Left = constructBalancedTree(values, min, median), 
      Right = constructBalancedTree(values, median + 1, max) 
     }; 
    } 

    TreeNode constructBalancedTree(IEnumerable<int> values) 
    { 
     return constructBalancedTree(
      values.OrderBy(x => x).ToList(), 0, values.Count()); 
    } 

    void Run() 
    { 
     TreeNode balancedTree = constructBalancedTree(Enumerable.Range(1, 9)); 
     // displayTree(balancedTree); // TODO: implement this! 
    } 

    static void Main(string[] args) 
    { 
     new Program().Run(); 
    } 
} 

Answer 2

इस पत्र में विस्तार से बताते हैं::

ट्री इष्टतम समय में पुनर्संतुलन और अंतरिक्ष
http://www.eecs.umich.edu/~qstout/abs/CACM86.html

इसके अलावा यहाँ: यह अंतिम अजगर कोड है

एक- समय बाइनरी खोज वृक्ष संतुलन: दिन/स्टउट/वॉरेन (डीएसडब्ल्यू) एल्गोरिदम
http://penguin.ewu.edu/~trolfe/DSWpaper/

यदि आप वास्तव में इसे उड़ान भरना चाहते हैं, तो आपको एक स्व-संतुलन वृक्ष की आवश्यकता है।

यदि आप बस एक साधारण पेड़ बनाना चाहते हैं, इसे संतुलित करने की परेशानी के बिना, बस पेड़ में डालने से पहले तत्वों को यादृच्छिक बनाएं।

Answer 3

अपने आंकड़ों की माध्यिका करें (या अधिक सटीक, मंझला करने के लिए अपने सरणी में निकटतम तत्व) की जड़ पेड़। और फिर रिकर्सिव पर।