2010-09-10 20 views
5

Hier ist die Situation, ich entwickle einen binären Suchbaum und in jedem Knoten des Baumes beabsichtige ich, die eigene Höhe zu speichern, um den Baum während der avl-Baumbildung weiter auszugleichen. Zuvor hatte ich einen iterativen Ansatz, um die Höhe eines Knotens beim Ausgleichen des Baums wie folgt zu berechnen.Wie kann diese stackoverflow-Ausnahme vermieden werden?

(Der folgende Code gehört zu einer Klasse namens AVLTree<T>, die ein Kind Klasse von BinarySearchTree<T> ist)

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;    
     } 

Aber es war eine Menge Performance-Overhead zu verursachen.

Performance of an AVL Tree in C#

So ging ich in jedem Knoten zum Zeitpunkt des Einsetzens in den BinarySearchTree<T> den Höhenwert zu speichern. Jetzt kann ich beim Iterieren diese Iteration vermeiden und erhalte die gewünschte Performance in AVLTree<T>.

Aber jetzt ist das Problem, wenn ich versuche, eine große Anzahl von Daten sagen, sagen 1-50000 sequentiell in BinarySearchTree<T> (ohne es auszugleichen), bekomme ich StackoverflowException. Ich stelle den Code zur Verfügung, der es verursacht. Können Sie mir bitte helfen, eine Lösung zu finden, die diese Ausnahme vermeidet und auch keine Kompromisse mit der Leistung in seiner Kindklasse AVLTree<T> eingeht?

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; 
      } 
     } 
    } 

ich die Stackoverflow bin immer die Höhe auf der folgenden Zeile

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

in der Height Eigenschaft BinaryTreeNode<T> Klasse bei der Berechnung. Wenn möglich, schlagen Sie mir bitte ein wenig vor. BTW

, vielen Dank für Ihre Aufmerksamkeit so lange Frage zu lesen :)

+1

In vor stackoverflow.com Witze. – BoltClock

Antwort

2

Wenn Sie einen Knoten hinzufügen, können Sie die Höhe berechnen, indem rekursiv über alle übergeordneten Knoten iteriert. Ein .NET-Prozess hat begrenzten Speicherplatz und bei einem großen Baum verbrauchen Sie den gesamten Speicherplatz und erhalten eine StackOverflowException. Sie können die Rekursion in eine Iteration umwandeln, um zu vermeiden, dass Stapelspeicher belegt wird. Andere Sprachen wie funktionale Sprachen können mit einer Technik namens Tail-Rekursion rekursiv arbeiten, ohne Stack-Speicherplatz zu verbrauchen. In C# müssen Sie Ihren Code jedoch manuell ändern.

Hier sind modifizierte Versionen von Height und UpdateHeight in BinaryTreeNode<T> die nicht Rekursion nicht verwendet:

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; 
    } 
} 
+0

Ya ich weiß das, aber das Problem ist, ich bin nicht in der Lage, eine gute Lösung zu finden, deshalb habe ich die Frage gestellt :) –

+0

Dank Martin, sieht aus wie die ähnliche Lösung, die ich gefunden habe. Obwohl ich es vor dir herausgefunden habe, aber deine Lösung verdient, als eine Antwort ausgewählt zu werden, weil du etwas Zeit für mich verbracht hast. :) Danke noch einmal. –

0

Sie einen Schwanz hinzufügen können. Rufen Sie il auf, dekompilieren Sie die Datei und kompilieren Sie sie erneut.

Beispiel:

.... IL_0002:

Schweif.

IL_0003: Anruf ...

IL_0008: RET

Beispiel auf sie wieder zusammenzustellen:

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

(dies ist wahrscheinlich nicht, was du willst, aber wieder ist es nur ein Beispiel)

Ich bin sicher, dass du es herausfinden kannst und es funktioniert, es ist nicht zu h ard.

Der große Nachteil ist, dass die Neukompilierung Ihren Tail Call loswerden wird, also empfehle ich, eine Build-Aufgabe in Msbuild einzurichten, um es automatisch für Sie zu tun.

0

Ich glaube, ich die Lösung gefunden, modifizierte ich den Code wie folgt und es funktionierte wie ein Zauber

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;    
      }   

     } 

Vielen Dank Leute, die für mich einige Zeit verbringen, um versucht, die Lösung zu finden.

0

Wenn Sie große Datenmengen auf einmal einfügen, würde ich denken, Sie wären besser im Batch-Einfügen der Daten ohne den Aufruf von Parent.UpdateHeight dann gehen Sie den Baum, um die Höhe, wie Sie gehen.

Hinzufügen von zukünftigen Knoten Ich würde den Baum gehen, beginnend an der Wurzel, erhöhen Sie die Höhe, wie Sie gehen.

+0

Es ist keine gute Lösung. Ich habe diesen Ansatz früher versucht, aber es war ein großer Leistungsaufwand. Ich habe es auch hier erwähnt. –

+0

Sie erwähnten den Aufruf von GetBalance als Overhead. Ich habe nicht vorgeschlagen, dass Sie das tun sollten. – TedTrippin

Verwandte Themen