इस stackoverflow अपवाद से कैसे बचें?

Question

यहां स्थिति है, मैं एक बाइनरी सर्च पेड़ विकसित कर रहा हूं और पेड़ के प्रत्येक नोड में मैं एवल पेड़ गठन के दौरान पेड़ को संतुलित करने के लिए अपनी ऊंचाई को स्टोर करना चाहता हूं। पहले मैंने पेड़ को संतुलित करने के दौरान नोड की ऊंचाई की गणना करने के लिए एक पुनरावृत्ति दृष्टिकोण किया था।

protected virtual int GetBalance(BinaryTreeNode<T> node) 
     { 
      if(node != null) 
      { 
       IEnumerable<BinaryTreeNode<T>> leftSubtree = null, righSubtree = null; 

       if (node.Left != null) 
        leftSubtree = node.Left.ToEnumerable(BinaryTreeTraversalType.InOrder); 

       if (node.Right != null) 
        righSubtree = node.Right.ToEnumerable(BinaryTreeTraversalType.InOrder); 


       var leftHeight = leftSubtree.IsNullOrEmpty() ? 0 : leftSubtree.Max(x => x.Depth) - node.Depth; 
       var righHeight = righSubtree.IsNullOrEmpty() ? 0 : righSubtree.Max(x => x.Depth) - node.Depth; 


       return righHeight - leftHeight; 
      } 
      return 0;    
     } 

(निम्नलिखित कोड एक वर्ग जो BinarySearchTree<T> का एक बच्चा वर्ग है AVLTree<T> कहा जाता है के अंतर्गत आता है) लेकिन यह प्रदर्शन भूमि के ऊपर का एक बहुत खर्च किया गया था।

Performance of an AVL Tree in C#

तो मैं BinarySearchTree<T> में प्रविष्टि के समय में प्रत्येक नोड में ऊंचाई मूल्य के भंडारण के लिए चला गया। अब संतुलन के दौरान मैं इस पुनरावृत्ति से बचने में सक्षम हूं और मैं AVLTree<T> में वांछित प्रदर्शन प्राप्त कर रहा हूं।

लेकिन अब समस्या यह है कि यदि मैं बड़ी संख्या में डेटा डालने का प्रयास करता हूं तो BinarySearchTree<T> में क्रमशः 1-50000 कहें (इसे संतुलित किए बिना), मुझे StackoverflowException मिल रहा है। मैं कोड प्रदान कर रहा हूं जो इसे उत्पन्न कर रहा है। क्या आप कृपया मुझे समाधान ढूंढने में मदद कर सकते हैं जो इस अपवाद से बचें और अपने बच्चे वर्ग AVLTree<T> में प्रदर्शन के साथ समझौता भी नहीं करेगा?

public class BinaryTreeNode<T> 
    { 
     private BinaryTreeNode<T> _left, _right; 
     private int _height; 

     public T Value {get; set; } 
     public BinaryTreeNode<T> Parent; 
     public int Depth {get; set; } 

     public BinaryTreeNode() 
     {} 

     public BinaryTreeNode(T data) 
     { 
      Value = data; 
     } 

     public BinaryTreeNode<T> Left 
     { 
      get { return _left; } 
      set 
      { 
       _left = value; 
       if (_left != null) 
       { 
        _left.Depth = Depth + 1;  
        _left.Parent = this; 
       }     
       UpdateHeight(); 
      } 
     } 

     public BinaryTreeNode<T> Right 
     { 
      get { return _right; } 
      set 
      { 
       _right = value; 
       if (_right != null) 
       { 
        _right.Depth = Depth + 1; 
        _right.Parent = this; 
       } 
       UpdateHeight(); 
      } 
     } 

     public int Height 
     { 
      get { return _height; } 
      protected internal set 
      { 
       _height = value; 
       if (Parent != null) { 
        Parent.UpdateHeight(); 
       }    
      } 
     } 

     private void UpdateHeight() 
     { 
      if (Left == null && Right == null) { 
       return; 
      } 
      if(Left != null && Right != null) 
      { 
       if (Left.Height > Right.Height) 
        Height = Left.Height + 1; 
       else 
        Height = Right.Height + 1; 
      } 
      else if(Left == null) 
       Height = Right.Height + 1; 
      else 
       Height = Left.Height + 1; 
     } 

    } 

---

public class BinarySearchTree<T> 
    { 
     private readonly Comparer<T> _comparer = Comparer<T>.Default; 

     public BinarySearchTree() 
     { 
     } 

     public BinaryTreeNode<T> Root {get; set;} 

     public virtual void Add(T value) 
     { 
      var n = new BinaryTreeNode<T>(value); 
      int result; 

      BinaryTreeNode<T> current = Root, parent = null; 
      while (current != null) 
      { 
       result = _comparer.Compare(current.Value, value); 
       if (result == 0) 
       { 
        parent = current; 
        current = current.Left; 
       } 
       if (result > 0) 
       { 
        parent = current; 
        current = current.Left; 
       } 
       else if (result < 0) 
       { 
        parent = current; 
        current = current.Right; 
       } 
      } 

      if (parent == null) 
       Root = n; 
      else 
      { 
       result = _comparer.Compare(parent.Value, value); 
       if (result > 0) 
        parent.Left = n; 
       else 
        parent.Right = n; 
      } 
     } 
    } 

मैं निम्न पंक्ति

if (Parent != null) { 
        Parent.UpdateHeight(); 
       } 

BinaryTreeNode<T> वर्ग के Height संपत्ति में कम से ऊंचाई की गणना में StackoverflowException हो रही है। यदि संभव हो तो कृपया मुझे कुछ काम सुझाएं।

Btw, धन्यवाद आपका ध्यान के लिए एक बहुत इतने लंबे सवाल :) पढ़ने के लिए

Answer 1

जब आप एक नोड आप सभी माता पिता नोड्स रिकर्सिवली से अधिक पुनरावृत्ति द्वारा ऊंचाई की गणना जोड़ें। एक .NET प्रक्रिया में स्टैक स्पेस सीमित है और एक बड़ा पेड़ दिया गया है, आप सभी स्टैक स्पेस का उपभोग करेंगे और StackOverflowException प्राप्त करेंगे। स्टैक स्पेस लेने से बचने के लिए आप पुनरावृत्ति को पुनरावृत्ति में बदल सकते हैं। कार्यात्मक भाषाओं जैसी अन्य भाषाएं पूंछ रिकर्सन नामक तकनीक का उपयोग करके स्टैक स्पेस के बिना रिकर्स करने में सक्षम हैं। हालांकि, सी # में आपको अपने कोड को मैन्युअल रूप से संशोधित करना होगा।

यहाँ BinaryTreeNode<T> में Height और UpdateHeight के संस्करण संशोधित कर रहे हैं कि प्रत्यावर्तन का उपयोग नहीं करता:

public int Height { 
    get { return _height; } 
    private set { _height = value; } 
} 

void UpdateHeight() { 
    var leftHeight = Left != null ? Left.Height + 1 : 0; 
    var rightHeight = Right != null ? Right.Height + 1 : 0; 
    var height = Math.Max(leftHeight, rightHeight); 
    var node = this; 
    while (node != null) { 
    node.Height = height; 
    height += 1; 
    node = node.Parent; 
    } 
} 

Answer 2

आप एक पूंछ जोड़ सकते हैं। आईएल में कॉल करें, फ़ाइल को डीकंपाइल करें और फिर इसे फिर से संकलित करें।

उदाहरण:

.... IL_0002: जोड़ने

पूंछ।

IL_0003: कॉल करें ...

IL_0008: सेवानिवृत्त

इसे फिर से संकलन पर उदाहरण:

ilasm C: \ test.il /out=C:\TestTail.exe

(यह है शायद आप जो चाहते हैं वह नहीं, लेकिन फिर यह सिर्फ एक उदाहरण है)

मुझे यकीन है कि आप इसे समझ सकते हैं और इसे काम कर सकते हैं, यह एच नहीं है अर्द।

बड़ा नकारात्मक पक्ष यह है कि पुनर्मूल्यांकन आपकी पूंछ कॉल से छुटकारा पा जाएगा, इसलिए मैं इसे आपके लिए स्वचालित रूप से करने के लिए msbuild में एक बिल्ड कार्य सेट अप करने की अनुशंसा करता हूं।

Answer 3

मुझे लगता है मैं समाधान नहीं मिला, मैं कोड इस प्रकार संशोधित और यह एक आकर्षण की तरह काम किया

public int Height 
     { 
      get { return _height; } 
      protected internal set 
      { 
       _height = value;         
      } 
     } 

     private void UpdateHeight() 
     { 
      if (Left == null && Right == null) { 
       return; 
      } 
      if(Left != null && Right != null) 
      { 
       if (Left.Height > Right.Height) 
        Height = Left.Height + 1; 
       else 
        Height = Right.Height + 1; 
      } 
      else if(Left == null) 
       Height = Right.Height + 1; 
      else 
       Height = Left.Height + 1; 

      var parent = Parent; 
      while (parent != null) { 
       parent.Height++; 
       parent = parent.Parent;    
      }   

     } 

धन्यवाद एक बहुत लोग समाधान जानने की कोशिश करने के लिए मेरे लिए कुछ समय बिताते हैं।

Answer 4

यदि आप एक ही समय में बड़ी मात्रा में डेटा डाल रहे हैं तो मुझे लगता है कि आप बैच के माता-पिता को कॉल किए बिना डेटा डालने से बेहतर होंगे। अद्यतन करें, फिर पेड़ को ऊंचाई के साथ सेट करते समय चलें।

भविष्य के नोड्स जोड़ना मैं रूट पर शुरू होने पर पेड़ पर चलता हूं, ऊंचाई बढ़ने के साथ ही ऊंचाई बढ़ाता हूं।