AVL树在C＃中的表现 [英] Performance of an AVL Tree in C#
本文介绍了AVL树在C＃中的表现的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
我已经实现AVL树在C＃中的插入矩阵如下
的拍摄时间元素数量插入（秒）
-------------------------------------------------- ----
10 0.067
100 0.073
200 0.112
500 0.388
900 1.205
1000 1.466
5000 44.314
10000 195.435
现在我的问题是，它是一个AVL树有不错的表现还是我必须重新考虑改变算法或重构code？
编辑： 元素是整数，从0开始到移位#of元件 测试code如下：
[测试]
公共无效InsertionTest（）
{
AVLTree＆LT; INT＆GT; _tree =新AVLTree＆LT;诠释＆GT;（）;
_stopWatch.Start（）;
的for（int i = 0; I＆LT; 5000;我++）{
_tree.Add（ⅰ）;
}
_stopWatch.Stop（）;
Console.WriteLine（时代取=+ _stopWatch.Elapsed）;
}
编辑：实现code
BinarySearchTree
[Serializable接口]
公共类BinarySearchTree＆LT; T＆GT; ：ICollection的＆LT; T＆GT;
{
私人只读的Comparer＆LT; T＆GT; _comparer =的Comparer＆LT; T＆GT; .DEFAULT;
公共BinarySearchTree（）
{
}
公共BinarySearchTree（IEnumerable的＆LT; T＆GT;集合）
{
的AddRange（collection.ToArray（））;
}
公共BinarySearchTree（的Comparer＆LT; T＆GT;比较器）
{
_comparer =比较器;
}
公共BinaryTreeNode＆LT; T＆GT;根{获得;保护套; }
＃地区的ICollection＆LT; T＆GT;会员
///＆LT;总结＆gt;
///增加一个项目的＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /总结＆gt;
///＆LT;参数名称=值＆gt;到添加到对象的＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /参数＆GT;
///＆LT;异常CREF =T：System.NotSupportedException＆GT;的＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/＆GT;为只读。
///＆LT; /异常＆GT;
公共虚拟无效添加（T值）
{
变种N =新BinaryTreeNode＆LT; T＆GT;（值）;
INT结果;
BinaryTreeNode＆LT; T＆GT;目前=根，父= NULL;
而（电流！= NULL）
{
结果= _comparer.Compare（current.Value，价值）;
如果（结果== 0）
{
父=电流;
电流= current.Left;
}
如果（结果大于0）
{
父=电流;
电流= current.Left;
}
否则如果（结果℃，）
{
父=电流;
电流= current.Right;
}
}
伯爵++;
如果（家长== NULL）
根= N;
其他
{
结果= _comparer.Compare（parent.Value，价值）;
如果（结果大于0）
parent.Left = N;
其他
parent.Right = N;
}
}
///＆LT;总结＆gt;
///移除的＆lt所有项目;看到CREF =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /总结＆gt;
///＆LT;异常CREF =T：System.NotSupportedException＆GT;的＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/＆GT;为只读。
///＆LT; /异常＆GT;
公共无效清除（）
{
根= NULL;
计数= 0;
}
///＆LT;总结＆gt;
///确定是否在＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/＆GT;包含特定值。
///＆LT; /总结＆gt;
///＆LT;返回＆GT;
///真实的，如果＆LT; paramref名称=项/＆GT;被发现在＆lt;见的cref =T：System.Collections.Generic.ICollection`1/取代;否则为false。
///＆LT; /回报＆GT;
///＆LT; PARAM NAME =项目＆gt;在定位对象的＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /参数＆GT;
公共虚拟BOOL包含（T项）
{
BinaryTreeNode＆LT; T＆GT;电流=根;
而（电流！= NULL）
{
INT结果= _comparer.Compare（current.Value，项目）;
如果（结果== 0）
返回true;
如果（结果大于0）
电流= current.Left;
否则如果（结果℃，）
电流= current.Right;
}
返回false;
}
公共无效CopyTo从（T []数组，INT指数）
{
CopyTo从（数组，索引，BinaryTreeTraversalType.InOrder）;
}
///＆LT;总结＆gt;
///移除的＆lt特定对象的第一个匹配;看到CREF =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /总结＆gt;
///＆LT;返回＆GT;
///真实的，如果＆LT; paramref名称=项/＆GT;成功地从在＆lt删除;看到CREF =T：System.Collections.Generic.ICollection`1/取代;否则为false。这种方法也返回假，如果＆LT; paramref名称=项/＆GT;未在原始＆其中找到;见的cref =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /回报＆GT;
///＆所述; PARAM NAME =项＆gt;将对象从在＆lt除去;见的cref =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /参数＆GT;
///＆LT;异常CREF =T：System.NotSupportedException＆GT;的＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/＆GT;为只读。
///＆LT; /异常＆GT;
公共虚拟BOOL删除（T项目）
{
如果（根== NULL）
返回false;
BinaryTreeNode＆LT; T＆GT;目前=根，父= NULL;
INT结果= _comparer.Compare（current.Value，项目）;
而（结果！= 0）
{
如果（结果大于0）
{
父=电流;
电流= current.Left;
}
否则如果（结果℃，）
{
父=电流;
电流= current.Right;
}
如果（当前== NULL）
返回false;
结果= _comparer.Compare（current.Value，项目）;
}
计数 - ;
//现在我们需要再穿入树
//案例1：如果当前没有合适的孩子，那么当前的左子变
//指向的节点由父
如果（current.Right == NULL）
{
如果（家长== NULL）
根= current.Left;
其他
{
结果= _comparer.Compare（parent.Value，current.Value）;
如果（结果大于0）
parent.Left = current.Left;
否则如果（结果℃，）
parent.Right = current.Left;
}
//案例2：如果当前的右孩子没有左孩子，那么当前的右子
//替换目前的在树
}
否则，如果（current.Right.Left == NULL）
{
current.Right.Left = current.Left;
如果（家长== NULL）
根= current.Right;
其他
{
结果= _comparer.Compare（parent.Value，current.Value）;
如果（结果大于0）
parent.Left = current.Right;
否则如果（结果℃，）
parent.Right = current.Right;
}
//案例3：如果当前的右孩子有左孩子，取代目前现行的
//右孩子的最左边的后代
}
其他
{
BinaryTreeNode＆LT; T＆GT;最左边= current.Right.Left，lmParent = current.Right;
而（leftmost.Left！= NULL）
{
lmParent =最左边;
最左边= leftmost.Left;
}
lmParent.Left = leftmost.Right;
leftmost.Left = current.Left;
leftmost.Right = current.Right;
如果（家长== NULL）
根=最左边;
其他
{
结果= _comparer.Compare（parent.Value，current.Value）;
如果（结果大于0）
parent.Left =最左边;
否则如果（结果℃，）
parent.Right =最左边;
}
}
current.Left = current.Right = NULL;
返回true;
}
///＆LT;总结＆gt;
///获取包含在＆lt元件的数量;见的cref =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /总结＆gt;
///＆LT;返回＆GT;
///包含在＆lt元素的数目;见的cref =T：System.Collections.Generic.ICollection`1/取代。
///＆LT; /回报＆GT;
公众诠释计数{获得;私定; }
///＆LT;总结＆gt;
///获取一个值，指示是否在＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/＆GT;为只读。
///＆LT; /总结＆gt;
///＆LT;返回＆GT;
/// true，如果在＆lt;看到CREF =T：System.Collections.Generic.ICollection`1/＆GT;是只读;否则为false。
///＆LT; /回报＆GT;
公共BOOL的IsReadOnly
{
获得{返回false; }
}
#endregion
公共无效的AddRange（IEnumerable的＆LT; T＆GT;项目）
{
的foreach（在项目VAR项）
{
添加（项目）;
}
}
公共无效CopyTo从（T []数组，INT指数，BinaryTreeTraversalType traversalType）
{
Root.ToEnumerable（traversalType）。选择（X =＆GT; x.Value）。.ToArray（）CopyTo从（数组索引）;
}
公共BinaryTreeNode＆LT; T＆GT;查找（T值）
{
BinaryTreeNode＆LT; T＆GT;电流=根;
而（电流！= NULL）
{
INT结果= _comparer.Compare（current.Value，价值）;
如果（结果== 0）
返回电流;
如果（结果大于0）
电流= current.Left;
否则如果（结果℃，）
电流= current.Right;
}
返回null;
}
的IEnumerable的＃地区实施
///＆LT;总结＆gt;
///通过收集返回一个枚举迭代。
///＆LT; /总结＆gt;
///＆LT;返回＆GT;
/// A＆LT;见CREF =T：System.Collections.Generic.IEnumerator`1/＆GT;可用于遍历集合。
///＆LT; /回报＆GT;
///＆其中; filterpriority→1＆其中; / filterpriority＆GT;
公众的IEnumerator＆LT; T＆GT;的GetEnumerator（）
{
返回Root.ToEnumerable（BinaryTreeTraversalType.InOrder）。选择（X =＆GT; x.Value）.GetEnumerator（）;
}
///＆LT;总结＆gt;
///通过集合返回一个枚举迭代。
///＆LT; /总结＆gt;
///＆LT;返回＆GT;
///一个＆LT;见CREF =T：System.Collections.IEnumerator/＆GT;对象可用于遍历集合。
///＆LT; /回报＆GT;
///＆其中; filterpriority→2＆其中; / filterpriority＆GT;
IEnumerator的IEnumerable.GetEnumerator（）
{
返回的GetEnumerator（）;
}
#endregion
}
AVLTree
公共类AVLTree＆LT; T＆GT; ：BinarySearchTree＆LT; T＆GT;
{
公共AVLTree（）
{
}
公共AVLTree（IEnumerable的＆LT; T＆GT;集合）
：基地（集合）
{
}
公共AVLTree（的Comparer＆LT; T＆GT;比较器）
：基地（比较器）
{
}
公众覆盖无效添加（T值）
{
base.Add（值）;
VAR节点=查找（值）;
是AbstractNode＆LT; T＆GT; parentNode = node.Parent;
而（parentNode！= NULL）
{
INT余额=为getBalance（parentNode为BinaryTreeNode＆LT; T＆GT;）;
如果（Math.Abs（余量）== 2）
{
BalanceAt（parentNode为BinaryTreeNode＆LT; T＆GT ;,平衡）;
}
parentNode = parentNode.Parent;
}
}
公众覆盖BOOL删除（T项目）
{
如果（根== NULL）
返回false;
BinaryTreeNode＆LT; T＆GT; valueNode =查找（项目）;
是AbstractNode＆LT; T＆GT; parentNode = valueNode.Parent;
布尔删除= base.Remove（项目）;
如果（！删除）
返回false;
而（parentNode！= NULL）
{
INT余额=为getBalance（parentNode为BinaryTreeNode＆LT; T＆GT;）;
如果（Math.Abs（余量）== 1）
打破;
如果（Math.Abs（余量）== 2）
{
BalanceAt（parentNode为BinaryTreeNode＆LT; T＆GT ;,平衡）;
}
parentNode = parentNode.Parent;
}
返回true;
}
///＆LT;总结＆gt;
///余额AVL树节点
///＆LT; /总结＆gt;
受保护的虚拟无效BalanceAt（BinaryTreeNode＆LT; T＆gt;节点，INT余额）
{
如果（余量== 2）
{
INT rightBalance =为getBalance（node.Right）;
如果（rightBalance == 1 || rightBalance == 0）
{
RotateLeft（节点）;
}
否则，如果（rightBalance == -1）
{
RotateRight（node.Right）;
RotateLeft（节点）;
}
}
否则，如果（平衡== -2）
{
INT leftBalance =为getBalance（node.Left）;
如果（leftBalance == 1）
{
RotateLeft（node.Left）;
RotateRight（节点）;
}
否则，如果（leftBalance == -1 || leftBalance == 0）
{
RotateRight（节点）;
}
}
}
///＆LT;总结＆gt;
///确定给定节点的平衡
///＆LT; /总结＆gt;
受保护的虚拟INT所以getBalance（BinaryTreeNode＆LT; T＆gt;节点）
{
如果（节点！= NULL）
{
IEnumerable的＆LT; BinaryTreeNode＆LT; T＆GT;＆GT; leftSubtree = NULL，righSubtree = NULL;
如果（node.Left！= NULL）
leftSubtree = node.Left.ToEnumerable（BinaryTreeTraversalType.InOrder）;
如果（node.Right！= NULL）
righSubtree = node.Right.ToEnumerable（BinaryTreeTraversalType.InOrder）;
// ReSharper的禁用AssignNullToNotNullAttribute
VAR leftHeight = leftSubtree.IsNullOrEmpty（）？ 0：leftSubtree.Max（X =＆GT; x.Depth） - node.Depth;
VAR righHeight = righSubtree.IsNullOrEmpty（）？ 0：righSubtree.Max（X =＆GT; x.Depth） - node.Depth;
// ReSharper的恢复AssignNullToNotNullAttribute
返回righHeight - leftHeight;
}
返回0;
}
///＆LT;总结＆gt;
///旋转内的AVL树的节点向左
///＆LT; /总结＆gt;
受保护的虚拟无效RotateLeft（BinaryTreeNode＆LT; T＆gt;节点）
{
如果（节点== NULL）
返回;
BinaryTreeNode＆LT; T＆GT;透视= node.Right;
如果（支点== NULL）
返回;
VAR rootParent = node.Parent为BinaryTreeNode＆LT; T＆GT ;;
布尔isLeftChild =（rootParent！= NULL）及和放大器; rootParent.Left ==节点;
布尔makeTreeRoot =节点==根;
node.Right = pivot.Left;
pivot.Left =节点;
node.Parent =支点;
pivot.Parent = rootParent;
如果（node.Right！= NULL）
node.Right.Parent =节点;
如果（makeTreeRoot）
根=支点;
如果（isLeftChild）
rootParent.Left =支点;
否则，如果（rootParent！= NULL）
rootParent.Right =支点;
}
///＆LT;总结＆gt;
///旋转一个节点内的AVL树权
///＆LT; /总结＆gt;
受保护的虚拟无效RotateRight（BinaryTreeNode＆LT; T＆gt;节点）
{
如果（节点== NULL）
返回;
BinaryTreeNode＆LT; T＆GT;透视= node.Left;
如果（支点== NULL）
返回;
VAR rootParent = node.Parent为BinaryTreeNode＆LT; T＆GT ;;
布尔isLeftChild =（rootParent！= NULL）及和放大器; rootParent.Left ==节点;
布尔makeTreeRoot =根==节点;
node.Left = pivot.Right;
pivot.Right =节点;
node.Parent =支点;
pivot.Parent = rootParent;
如果（node.Left！= NULL）
node.Left.Parent =节点;
如果（makeTreeRoot）
根=支点;
如果（isLeftChild）
rootParent.Left =支点;
否则，如果（rootParent！= NULL）
rootParent.Right =支点;
}
}
解决方案
标杆code在.NET中，您需要考虑到JIT编译时间。要做到这一点最简单的方法，就是让你的测试code运行code的两倍 - 并丢弃第一时序结果
这一边 - 你的基准测试结果似乎暗示增幅比预期的更糟糕Ò（log n）的时间AVL树插入
你什么都没有张贴在这里是code为 BinaryTreeNode＆LT;＆GT; 类。我怀疑你可能有一些有方法的实现一个问题 - 我特别可疑像深物业的和 ToEnumerable 。
I have implemented an AVL tree in C# whose insertion matrix is as follows
Number of Elements Time taken to insert (sec)
------------------------------------------------------
10 0.067
100 0.073
200 0.112
500 0.388
900 1.205
1000 1.466
5000 44.314
10000 195.435
Now my question is, is it a good performance for an AVL tree or do I have to re-consider changing the algorithm or refactoring the code?
Edit: The elements are integer starting from 0 to #of elements Test code is as follows
[Test]
public void InsertionTest()
{
AVLTree<int> _tree = new AVLTree<int>();
_stopWatch.Start();
for (int i = 0; i < 5000; i++) {
_tree.Add(i);
}
_stopWatch.Stop();
Console.WriteLine("Time taken = " + _stopWatch.Elapsed);
}
Edit: Implementation code
BinarySearchTree
[Serializable]
public class BinarySearchTree<T> : ICollection<T>
{
private readonly Comparer<T> _comparer = Comparer<T>.Default;
public BinarySearchTree()
{
}
public BinarySearchTree(IEnumerable<T> collection)
{
AddRange(collection.ToArray());
}
public BinarySearchTree(Comparer<T> comparer)
{
_comparer = comparer;
}
public BinaryTreeNode<T> Root { get; protected set; }
#region ICollection<T> Members
/// <summary>
/// Adds an item to the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </summary>
/// <param name = "value">The object to add to the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </param>
/// <exception cref = "T:System.NotSupportedException">The <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
/// </exception>
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;
}
}
Count++;
if (parent == null)
Root = n;
else
{
result = _comparer.Compare(parent.Value, value);
if (result > 0)
parent.Left = n;
else
parent.Right = n;
}
}
/// <summary>
/// Removes all items from the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </summary>
/// <exception cref = "T:System.NotSupportedException">The <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
/// </exception>
public void Clear()
{
Root = null;
Count = 0;
}
/// <summary>
/// Determines whether the <see cref = "T:System.Collections.Generic.ICollection`1" /> contains a specific value.
/// </summary>
/// <returns>
/// true if <paramref name = "item" /> is found in the <see cref = "T:System.Collections.Generic.ICollection`1" />; otherwise, false.
/// </returns>
/// <param name = "item">The object to locate in the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </param>
public virtual bool Contains(T item)
{
BinaryTreeNode<T> current = Root;
while (current != null)
{
int result = _comparer.Compare(current.Value, item);
if (result == 0)
return true;
if (result > 0)
current = current.Left;
else if (result < 0)
current = current.Right;
}
return false;
}
public void CopyTo(T[] array, int index)
{
CopyTo(array, index, BinaryTreeTraversalType.InOrder);
}
/// <summary>
/// Removes the first occurrence of a specific object from the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </summary>
/// <returns>
/// true if <paramref name = "item" /> was successfully removed from the <see cref = "T:System.Collections.Generic.ICollection`1" />; otherwise, false. This method also returns false if <paramref name = "item" /> is not found in the original <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </returns>
/// <param name = "item">The object to remove from the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </param>
/// <exception cref = "T:System.NotSupportedException">The <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
/// </exception>
public virtual bool Remove(T item)
{
if (Root == null)
return false;
BinaryTreeNode<T> current = Root, parent = null;
int result = _comparer.Compare(current.Value, item);
while (result != 0)
{
if (result > 0)
{
parent = current;
current = current.Left;
}
else if (result < 0)
{
parent = current;
current = current.Right;
}
if (current == null)
return false;
result = _comparer.Compare(current.Value, item);
}
Count--;
// We now need to "rethread" the tree
// CASE 1: If current has no right child, then current's left child becomes
// the node pointed to by the parent
if (current.Right == null)
{
if (parent == null)
Root = current.Left;
else
{
result = _comparer.Compare(parent.Value, current.Value);
if (result > 0)
parent.Left = current.Left;
else if (result < 0)
parent.Right = current.Left;
}
// CASE 2: If current's right child has no left child, then current's right child
// replaces current in the tree
}
else if (current.Right.Left == null)
{
current.Right.Left = current.Left;
if (parent == null)
Root = current.Right;
else
{
result = _comparer.Compare(parent.Value, current.Value);
if (result > 0)
parent.Left = current.Right;
else if (result < 0)
parent.Right = current.Right;
}
// CASE 3: If current's right child has a left child, replace current with current's
// right child's left-most descendent
}
else
{
BinaryTreeNode<T> leftmost = current.Right.Left, lmParent = current.Right;
while (leftmost.Left != null)
{
lmParent = leftmost;
leftmost = leftmost.Left;
}
lmParent.Left = leftmost.Right;
leftmost.Left = current.Left;
leftmost.Right = current.Right;
if (parent == null)
Root = leftmost;
else
{
result = _comparer.Compare(parent.Value, current.Value);
if (result > 0)
parent.Left = leftmost;
else if (result < 0)
parent.Right = leftmost;
}
}
current.Left = current.Right = null;
return true;
}
/// <summary>
/// Gets the number of elements contained in the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </summary>
/// <returns>
/// The number of elements contained in the <see cref = "T:System.Collections.Generic.ICollection`1" />.
/// </returns>
public int Count { get; private set; }
/// <summary>
/// Gets a value indicating whether the <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only.
/// </summary>
/// <returns>
/// true if the <see cref = "T:System.Collections.Generic.ICollection`1" /> is read-only; otherwise, false.
/// </returns>
public bool IsReadOnly
{
get { return false; }
}
#endregion
public void AddRange(IEnumerable<T> items)
{
foreach (var item in items)
{
Add(item);
}
}
public void CopyTo(T[] array, int index, BinaryTreeTraversalType traversalType)
{
Root.ToEnumerable(traversalType).Select(x => x.Value).ToArray().CopyTo(array, index);
}
public BinaryTreeNode<T> Find(T value)
{
BinaryTreeNode<T> current = Root;
while (current != null)
{
int result = _comparer.Compare(current.Value, value);
if (result == 0)
return current;
if (result > 0)
current = current.Left;
else if (result < 0)
current = current.Right;
}
return null;
}
#region Implementation of IEnumerable
/// <summary>
/// Returns an enumerator that iterates through the collection.
/// </summary>
/// <returns>
/// A <see cref = "T:System.Collections.Generic.IEnumerator`1" /> that can be used to iterate through the collection.
/// </returns>
/// <filterpriority>1</filterpriority>
public IEnumerator<T> GetEnumerator()
{
return Root.ToEnumerable(BinaryTreeTraversalType.InOrder).Select(x => x.Value).GetEnumerator();
}
/// <summary>
/// Returns an enumerator that iterates through a collection.
/// </summary>
/// <returns>
/// An <see cref = "T:System.Collections.IEnumerator" /> object that can be used to iterate through the collection.
/// </returns>
/// <filterpriority>2</filterpriority>
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
#endregion
}
AVLTree
public class AVLTree<T> : BinarySearchTree<T>
{
public AVLTree()
{
}
public AVLTree(IEnumerable<T> collection)
: base(collection)
{
}
public AVLTree(Comparer<T> comparer)
: base(comparer)
{
}
public override void Add(T value)
{
base.Add(value);
var node = Find(value);
AbstractNode<T> parentNode = node.Parent;
while (parentNode != null)
{
int balance = GetBalance(parentNode as BinaryTreeNode<T>);
if (Math.Abs(balance) == 2)
{
BalanceAt(parentNode as BinaryTreeNode<T>, balance);
}
parentNode = parentNode.Parent;
}
}
public override bool Remove(T item)
{
if (Root == null)
return false;
BinaryTreeNode<T> valueNode = Find(item);
AbstractNode<T> parentNode = valueNode.Parent;
bool removed = base.Remove(item);
if (!removed)
return false;
while (parentNode != null)
{
int balance = GetBalance(parentNode as BinaryTreeNode<T>);
if (Math.Abs(balance) == 1)
break;
if (Math.Abs(balance) == 2)
{
BalanceAt(parentNode as BinaryTreeNode<T>, balance);
}
parentNode = parentNode.Parent;
}
return true;
}
/// <summary>
/// Balances an AVL Tree node
/// </summary>
protected virtual void BalanceAt(BinaryTreeNode<T> node, int balance)
{
if (balance == 2)
{
int rightBalance = GetBalance(node.Right);
if (rightBalance == 1 || rightBalance == 0)
{
RotateLeft(node);
}
else if (rightBalance == -1)
{
RotateRight(node.Right);
RotateLeft(node);
}
}
else if (balance == -2)
{
int leftBalance = GetBalance(node.Left);
if (leftBalance == 1)
{
RotateLeft(node.Left);
RotateRight(node);
}
else if (leftBalance == -1 || leftBalance == 0)
{
RotateRight(node);
}
}
}
/// <summary>
/// Determines the balance of a given node
/// </summary>
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);
// ReSharper disable AssignNullToNotNullAttribute
var leftHeight = leftSubtree.IsNullOrEmpty() ? 0 : leftSubtree.Max(x => x.Depth) - node.Depth;
var righHeight = righSubtree.IsNullOrEmpty() ? 0 : righSubtree.Max(x => x.Depth) - node.Depth;
// ReSharper restore AssignNullToNotNullAttribute
return righHeight - leftHeight;
}
return 0;
}
/// <summary>
/// Rotates a node to the left within an AVL Tree
/// </summary>
protected virtual void RotateLeft(BinaryTreeNode<T> node)
{
if (node == null)
return;
BinaryTreeNode<T> pivot = node.Right;
if (pivot == null)
return;
var rootParent = node.Parent as BinaryTreeNode<T>;
bool isLeftChild = (rootParent != null) && rootParent.Left == node;
bool makeTreeRoot = node == Root;
node.Right = pivot.Left;
pivot.Left = node;
node.Parent = pivot;
pivot.Parent = rootParent;
if (node.Right != null)
node.Right.Parent = node;
if (makeTreeRoot)
Root = pivot;
if (isLeftChild)
rootParent.Left = pivot;
else if (rootParent != null)
rootParent.Right = pivot;
}
/// <summary>
/// Rotates a node to the right within an AVL Tree
/// </summary>
protected virtual void RotateRight(BinaryTreeNode<T> node)
{
if (node == null)
return;
BinaryTreeNode<T> pivot = node.Left;
if (pivot == null)
return;
var rootParent = node.Parent as BinaryTreeNode<T>;
bool isLeftChild = (rootParent != null) && rootParent.Left == node;
bool makeTreeRoot = Root == node;
node.Left = pivot.Right;
pivot.Right = node;
node.Parent = pivot;
pivot.Parent = rootParent;
if (node.Left != null)
node.Left.Parent = node;
if (makeTreeRoot)
Root = pivot;
if (isLeftChild)
rootParent.Left = pivot;
else if (rootParent != null)
rootParent.Right = pivot;
}
}
解决方案
Benchmarking code in .NET requires that you take into account JIT compilation time. The easiest way to do this, is to have your test code run the code twice - and discard the first timing results.
That aside - your benchmark results seem to imply a growth rate worse than the expected O(log n) time for AVL tree insertion.
What you haven't posted here is the code for the BinaryTreeNode<> class. I suspect you may have a problem in the implementation of some of the methods there - I'm particularly suspicious of properties like Depth and ToEnumerable.
这篇关于AVL树在C＃中的表现的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
