Как избежать исключения stackoverflow?

Question

Вот ситуация, я разрабатываю двоичное дерево поиска, и в каждом узле дерева я намерен хранить собственную высоту для дальнейшей балансировки дерева при формировании дерева avl. Раньше у меня был итеративный подход для вычисления высоты узла при балансировке дерева, как показано ниже.

(Следующий код принадлежит к классу называется AVLTree<T>, который является классом ребенок 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;    
     } 

Но это было навлечь много накладных расходов.

Performance of an AVL Tree in C#

Так что я пошел для хранения значения высоты в каждом узле в момент вставки в BinarySearchTree<T>. Теперь во время балансировки я могу избежать этой итерации, и я набираю желаемую производительность в AVLTree<T>.

Но теперь проблема в том, что если я попытаюсь вставить большое количество данных, скажите 1-50000 последовательно в BinarySearchTree<T> (без балансировки), я получаю исключение 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; 
      } 
     } 
    } 

Я получаю StackOverflowException при вычислении высоты в следующей строке

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

в Height свойстве BinaryTreeNode<T> класса. Если возможно, предложите мне немного работы.

Кстати, большое спасибо за внимание, чтобы читать такой длинный вопрос :)

Answer 1

При добавлении узла вы вычислить высоту путем перебора всех родительских узлов рекурсивно. Процесс .NET имеет ограниченное пространство в стеке, и, учитывая большое дерево, вы будете потреблять все пространство стека и получить StackOverflowException. Вы можете изменить рекурсию на итерацию, чтобы избежать использования пространства стека. Другие языки, такие как функциональные языки, могут перезаписывать, не потребляя пространство стека, используя технику, называемую хвостовой рекурсией. Однако в C# вам придется вручную изменить свой код.

Вот модифицированные версии Height и UpdateHeight в BinaryTreeNode<T>, который не использует рекурсию:

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, декомпилируйте файл и затем скомпилируйте его снова.

Пример:

.... IL_0002: добавить

хвост.

IL_0003: звонок ...

IL_0008: RET

Пример по составлению его снова:

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

(это вероятно, не то, что вы хотите, но опять же это просто пример)

Я уверен, что вы можете понять это и заставить его работать, это не для h ARD.

Большой недостаток заключается в том, что перекомпиляция избавится от вашего хвостового вызова, поэтому я рекомендую настроить задачу сборки в 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

Если вы вставляете большие объемы данных за один раз, я бы подумал, что вам лучше вставлять данные без вызова Parent.UpdateHeight, а затем ходить по дереву, задавая высоту по мере того, как вы идете.

Добавление будущих узлов Я бы шел по дереву, начиная с корня, увеличивая высоту по мере продвижения.