Wie vermeide ich diese Stackoverflow-Ausnahme?

Question

Hier ist die Situation, ich entwickle einen binären Suchbaum und in jedem Knoten des Baums beabsichtige ich, die Höhe seines eigenen zu speichern, um den Baum während der AVL-Baumbildung weiter auszugleichen. Zuvor hatte ich einen iterativen Ansatz, um die Höhe eines Knotens während des Ausgleichs des Baums zu berechnen, wie folgt.

(Der folgende Code gehört zu einer Klasse namens AVLTree, die eine Unterklasse von BinarySearchTree ist)

geschützt virtual int GetBalance(BinaryTreeNode node)
        {
            wenn(node != null)
            {
                IEnumerable> leftSubtree = null, righSubtree = null;

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

                wenn (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;
            }
            rückkehr 0;            
        }

Aber das brachte eine Menge Performance-Overhead.

Leistung eines AVL-Baums in C#

Also entschied ich mich dafür, den Höhenwert in jedem Knoten zum Zeitpunkt der Einfügung im BinarySearchTree zu speichern. Jetzt kann ich während des Ausgleichs diese Iteration vermeiden und erziele die gewünschte Leistung in AVLTree.

Das Problem jetzt ist jedoch, wenn ich versuche, eine große Anzahl von Daten nacheinander in BinarySearchTree einzufügen (ohne sie auszugleichen), erhalte ich eine StackoverflowException. Ich gebe den Code an, der dies verursacht. Können Sie mir bitte helfen, eine Lösung zu finden, die diese Ausnahme vermeidet und auch in seiner Unterklasse AVLTree die Leistung nicht beeinträchtigt?

public class BinaryTreeNode
    {
        private BinaryTreeNode _left, _right;
        private int _height;

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

        public BinaryTreeNode()
        {}

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

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

        public BinaryTreeNode 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
    {
        private readonly Comparer _comparer = Comparer.Default;

        public BinarySearchTree()
        {
        }

        public BinaryTreeNode Root {get; set;}

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

            BinaryTreeNode 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 erhalte die StackoverflowException beim Berechnen der Höhe in der folgenden Zeile

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

im Height-Eigenschaft von BinaryTreeNode-Klasse. Wenn möglich, bitte schlagen Sie mir einen Workaround vor.

Übrigens vielen Dank für Ihre Aufmerksamkeit, um eine so lange Frage zu lesen :)

Answer 1

Wenn Sie einen Knoten hinzufügen, berechnen Sie die Höhe, indem Sie rekursiv über alle Elternknoten iterieren. Ein .NET-Prozess verfügt über begrenzten Stapelspeicher, und bei einem großen Baum wird der gesamte Stapelspeicher verbraucht, und es tritt eine StackOverflowException auf. Sie können die Rekursion in eine Iteration ändern, um den Stapelspeicher nicht zu verbrauchen. Andere Sprachen wie funktionale Sprachen können rekursiv ohne Stapelverbrauch durch Verwendung einer Technik namens Endrekursion durchgeführt werden. In C# müssen Sie jedoch Ihren Code manuell ändern.

Hier sind modifizierte Versionen von Höhe und UpdateHöhe in BinaryTreeNode, die keine Rekursion verwenden:

public int Höhe {
  get { return _höhe; }
  private set { _höhe = value; }
}

void UpdateHöhe() {
  var linkeHöhe = Links != null ? Links.Höhe + 1 : 0;
  var rechteHöhe = Rechts != null ? Rechts.Höhe + 1 : 0;
  var höhe = Math.Max(linkeHöhe, rechteHöhe);
  var knoten = this;
  while (knoten != null) {
    knoten.Höhe = höhe;
    höhe += 1;
    knoten = knoten.Elternknoten;
  }
}

Answer 2

Sie können einen Tail-Call in IL hinzufügen, die Datei dekompilieren und dann erneut kompilieren.

Beispiel:

.... IL_0002: add

tail.

IL_0003: call ...

IL_0008: ret

Beispiel zur erneuten Kompilierung:

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

(Dies ist wahrscheinlich nicht das, was Sie möchten, aber es ist nur ein Beispiel)

I am sicher, dass Sie es herausfinden und zum Laufen bringen können, es ist nicht so schwer.

Der große Nachteil ist, dass durch die erneute Kompilierung Ihr Tail-Call verschwinden wird, daher empfehle ich, eine Build-Aufgabe in msbuild einzurichten, um dies automatisch für Sie zu erledigen.

Answer 3

Ich denke, ich habe die Lösung gefunden, ich habe den Code wie folgt geändert und es hat wunderbar funktioniert

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 an alle, die sich die Zeit genommen haben, um mir bei der Lösungssuche zu helfen.

Answer 4

Wenn Sie große Datenmengen auf einmal einfügen, würden Sie meiner Meinung nach besser sein, die Daten chargenweise einzufügen, ohne den Aufruf von Parent.UpdateHeight, und dann den Baum entlanggehen und die Höhe währenddessen setzen.

Beim Hinzufügen zukünftiger Knoten würde ich den Baum durchlaufen, beginnend beim Wurzelknoten, und dabei die Höhe inkrementieren.