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 :)
In vor stackoverflow.com Witze. – BoltClock