如何避免这个stackoverflow异常？

Question

情况是这样的，我正在开发一个二叉搜索树，在树的每个节点中我打算存储它自己的高度，以便在 avl 树形成过程中进一步平衡树。以前，我有一种迭代方法来计算平衡树期间节点的高度，如下所示。

（以下代码属于名为 AVLTree 的类，它是 BinarySearchTree 的子类）

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

但它会产生大量性能开销。

C# 中 AVL 树的性能

所以我去存储高度插入 BinarySearchTree 时每个节点的值。现在，在平衡过程中，我能够避免这种迭代，并且在 AVLTree 中获得所需的性能。

但现在的问题是，如果我尝试在 BinarySearchTree 中按顺序插入大量数据（例如 1-50000）（不平衡它），我会收到 StackoverflowException。我提供了导致它的代码。您能否帮我找到一个解决方案，既可以避免此异常，又不会影响其子类 AVLTree 的性能？

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

我在计算BinaryTreeNode 类的 Height 属性中的 。如果可能的话请建议我一些解决方法。

顺便说一句，非常感谢您关注阅读这么长的问题:)

Answer 1

添加节点时，您可以通过递归迭代所有父节点来计算高度。 .NET 进程的堆栈空间有限，并且给定一棵大树，您将消耗所有堆栈空间并获得 StackOverflowException。您可以将递归更改为迭代以避免消耗堆栈空间。其他语言（例如函数式语言）能够通过使用称为尾递归的技术进行递归而不消耗堆栈空间。但是，在 C# 中，您必须手动修改代码。

以下是 BinaryTreeNode 中不使用递归的 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，反编译该文件，然后再次编译。

例子：

...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

如果您一次性插入大量数据，我认为您最好批量插入数据而不调用 Parent.UpdateHeight，然后遍历树设置高度。

添加未来的节点时，我会遍历树，从根部开始，逐渐增加高度。