Jak uniknąć tego wyjątku stackoverflow?

Question

Oto sytuacja, opracowuję drzewo wyszukiwania binarnego iw każdym węźle drzewa zamierzam przechowywać wysokość dla własnego zrównoważenia drzewa podczas tworzenia drzewa avl. Poprzednio miałem iteracyjne podejście do obliczania wysokości węzła podczas równoważenia drzewa, jak poniżej.

(Poniższy kod należy do klasy o nazwie AVLTree<T> który jest klasą dzieckiem BinarySearchTree<T>)

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

Ale to było ponoszenia dużo napowietrznych wydajności.

Performance of an AVL Tree in C#

Poszedłem więc do przechowywania wartości wysokości w każdym węźle w momencie wstawienia do BinarySearchTree<T>. Teraz podczas równoważenia jestem w stanie uniknąć tej iteracji i uzyskuję pożądaną wydajność w AVLTree<T>.

Ale teraz problem polega na tym, że jeśli spróbuję wstawić dużą liczbę danych, powiedz kolejno 1-50000 w BinarySearchTree<T> (bez równoważenia), otrzymuję StackoverflowException. Dostarczam kod, który go powoduje. Czy możesz mi pomóc znaleźć rozwiązanie, które pozwoli uniknąć tego wyjątku, a także nie pójdzie na kompromis z wydajnością w klasie potomnej 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; 
      } 
     } 
    } 

otrzymuję StackoverflowException obliczając wysokość w kolejnym wierszu

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

w mieniu BinaryTreeNode<T> klasy Height. Jeśli to możliwe, zaproponuj mi trochę pracy.

okazji, dziękuję za uwagę, aby czytać tak długiego pytanie :)

Answer 1

Po dodaniu węzła obliczyć wysokość przez iteracji nad wszystkimi węzłami macierzystymi rekurencyjnie. Proces .NET ma ograniczoną przestrzeń stosu i biorąc pod uwagę duże drzewo, zużyjesz całą przestrzeń stosu i uzyskasz StackOverflowException. Możesz zmienić rekurencję na iterację, aby uniknąć zużywania przestrzeni stosu. Inne języki, takie jak języki funkcjonalne, mogą rekursować się bez zużywania przestrzeni stosów za pomocą techniki zwanej rekurencją ogona. Jednak w języku C# będziesz musiał ręcznie zmodyfikować swój kod.

Tutaj są zmodyfikowane wersje Height i UpdateHeight w BinaryTreeNode<T> że nie używa rekursji:

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

Możesz dodać ogon. call in il, dekompiluj plik, a następnie skompiluj go ponownie.

przykład:

.... IL_0002: dodanie

ogon.

IL_0003: zadzwoń ...

IL_0008: ret

przykład na opracowaniu ponownie:

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

(to prawdopodobnie nie tego, co chcesz, ale znowu jest to tylko przykład)

Jestem pewien, że możesz to rozgryźć i sprawić, że zadziała, to nie jest h ard.

Dużym minusem jest to, że rekompilacja pozbędzie się ogona, więc zalecam skonfigurować zadanie kompilacji w msbuild, aby zrobił to automatycznie dla ciebie.

Answer 3

Chyba znalazłem rozwiązanie, że zmodyfikowany kod w następujący sposób i to działało jak czar

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

     } 

wielkie dzięki chłopaki dużo którzy spędzają trochę czasu dla mnie próbował dowiedzieć się rozwiązanie.

Answer 4

Jeśli wstawiasz duże ilości danych za jednym zamachem, myślę, że lepiej byłoby wsadowo wstawić dane bez połączenia z Parent.UpdateHeight, a następnie przejść drzewo ustawiając wysokość podczas podróży.

Dodawanie przyszłych węzłów Chodziłbym po drzewie, zaczynając od korzenia, zwiększając wysokość podczas podróży.