C# 实现平衡查找树的完整攻略如下：
什么是平衡查找树
平衡查找树也称 AVL 树，是一种非常高效的数据结构，用于存储和查找有序的数据，平衡查找树的特点是保证了树的高度始终是 O(log n)，这样可以在 O(log n) 时间内查找任何一个元素。平衡查找树常用于数据库索引、文件系统和网络路由器中等需要高效查找的场景。
平衡查找树的实现
平衡查找树的实现需要满足两个条件：
- 每个节点的左右子树高度差不大于 1
- 每个节点存储的关键字大于它左子树的所有关键字，小于它右子树的所有关键字。
为了保证平衡查找树的高度始终是 O(log n)，我们需要对插入和删除操作进行维护，具体的实现过程包括：
插入操作
- 先按照二叉查找树的方式将新节点插入到树中。
- 插入后对节点的父节点进行旋转操作，使节点的左右子树高度差不大于 1，旋转的方式有四种，单旋转（LL 和 RR）和双旋转（LR 和 RL），具体实现如下：
左旋转（LL）
当某个节点的右子树高度比左子树高度大于 1 时，我们需要进行左旋转（也称单旋转），如下图所示：
p pl
/ \ / \
pl Pr ==> ll p
/ \ / \ / \
ll lr p1 p2 lr pr
/ \
p1 p2
右旋转（RR）
当某个节点的左子树高度比右子树高度大于 1 时，我们需要进行右旋转（也称单旋转），如下图所示：
p pr
/ \ / \
Pl Pr ==> p rr
/ \ / \ / \
rl rr pl pr1 pr2
/ \
pr1 pr2
双旋转（LR）
当某个节点的右子树高度比左子树高度小于 -1，同时右子树的左子树高度比右子树的右子树高度大于 1 时，我们需要进行双旋转（LR），具体的操作是先对右子节点进行右旋转，再对父节点进行左旋转，如下图所示：
p pl
/ \ / \
Pl Pr ==> pr p
/ \ / \ / \
bl pr ==> bl bll bll prr
/ \
bll prr
双旋转（RL）
当某个节点的左子树高度比右子树高度小于 -1，同时左子树的右子树高度比左子树的左子树高度大于 1 时，我们需要进行双旋转（RL），具体的操作是先对左子节点进行左旋转，再对父节点进行右旋转，如下图所示：
p pr
/ \ / \
Pl Pr ==> p pl
/ \ / \ / \
bl pr bl pr1 pl1 pr2
/ \
pl1 pr1
删除操作
- 先按照二叉查找树的方式将节点从树中删除。
- 删除后对节点的父节点进行旋转操作，同样保证节点的左右子树高度差不大于 1。
示例说明
以下是一个简单的示例，展示如何使用 C# 实现平衡查找树：
// 定义平衡查找树的节点
public class AVLNode<T>
{
public T Data;
public AVLNode<T> Left;
public AVLNode<T> Right;
public int Height;
}
// 定义平衡查找树
public class AVLTree<T>
{
private AVLNode<T> _root;
// 插入节点
public void Insert(T data)
{
_root = Insert(_root, data);
}
// 递归地插入节点
private AVLNode<T> Insert(AVLNode<T> node, T data)
{
if (node == null)
{
return new AVLNode<T>() { Data = data, Height = 1 };
}
if (Comparer<T>.Default.Compare(data, node.Data) < 0)
{
node.Left = Insert(node.Left, data);
}
else
{
node.Right = Insert(node.Right, data);
}
node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
int balance = GetBalance(node);
// 左旋转
if (balance > 1 && Comparer<T>.Default.Compare(data, node.Left.Data) < 0)
{
return RotateRight(node);
}
// 右旋转
if (balance < -1 && Comparer<T>.Default.Compare(data, node.Right.Data) > 0)
{
return RotateLeft(node);
}
// LR 双旋转
if (balance > 1 && Comparer<T>.Default.Compare(data, node.Left.Data) > 0)
{
node.Left = RotateLeft(node.Left);
return RotateRight(node);
}
// RL 双旋转
if (balance < -1 && Comparer<T>.Default.Compare(data, node.Right.Data) < 0)
{
node.Right = RotateRight(node.Right);
return RotateLeft(node);
}
return node;
}
// 删除节点
public void Delete(T data)
{
_root = Delete(_root, data);
}
// 递归地删除节点
private AVLNode<T> Delete(AVLNode<T> node, T data)
{
if (node == null)
{
return null;
}
if (Comparer<T>.Default.Compare(data, node.Data) < 0)
{
node.Left = Delete(node.Left, data);
}
else if (Comparer<T>.Default.Compare(data, node.Data) > 0)
{
node.Right = Delete(node.Right, data);
}
else
{
if (node.Left == null)
{
return node.Right;
}
else if (node.Right == null)
{
return node.Left;
}
AVLNode<T> temp = GetMinNode(node.Right);
node.Data = temp.Data;
node.Right = Delete(node.Right, temp.Data);
}
node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
int balance = GetBalance(node);
// 左旋转
if (balance > 1 && GetBalance(node.Left) >= 0)
{
return RotateRight(node);
}
// 右旋转
if (balance < -1 && GetBalance(node.Right) <= 0)
{
return RotateLeft(node);
}
// LR 双旋转
if (balance > 1 && GetBalance(node.Left) < 0)
{
node.Left = RotateLeft(node.Left);
return RotateRight(node);
}
// RL 双旋转
if (balance < -1 && GetBalance(node.Right) > 0)
{
node.Right = RotateRight(node.Right);
return RotateLeft(node);
}
return node;
}
// 节点右旋转
private AVLNode<T> RotateRight(AVLNode<T> node)
{
AVLNode<T> left = node.Left;
AVLNode<T> right = left.Right;
left.Right = node;
node.Left = right;
node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
left.Height = Math.Max(GetHeight(left.Left), GetHeight(left.Right)) + 1;
return left;
}
// 节点左旋转
private AVLNode<T> RotateLeft(AVLNode<T> node)
{
AVLNode<T> right = node.Right;
AVLNode<T> left = right.Left;
right.Left = node;
node.Right = left;
node.Height = Math.Max(GetHeight(node.Left), GetHeight(node.Right)) + 1;
right.Height = Math.Max(GetHeight(right.Left), GetHeight(right.Right)) + 1;
return right;
}
// 获取节点的高度
private int GetHeight(AVLNode<T> node)
{
return node == null ? 0 : node.Height;
}
// 获取节点的平衡因子
private int GetBalance(AVLNode<T> node)
{
return node == null ? 0 : GetHeight(node.Left) - GetHeight(node.Right);
}
// 获取以某个节点为根节点的最小节点
private AVLNode<T> GetMinNode(AVLNode<T> node)
{
while (node.Left != null)
{
node = node.Left;
}
return node;
}
}
以上代码展示了一个简单的平衡查找树的实现，包括插入和删除操作。我们可以通过以下代码测试平衡查找树的效果：
AVLTree<int> tree = new AVLTree<int>();
Random rnd = new Random();
for (int i = 0; i < 10; i++)
{
int n = rnd.Next(1, 100);
Console.WriteLine("Insert: " + n);
tree.Insert(n);
}
Console.WriteLine("===== InorderTraversal Result =====");
tree.InorderTraversal(tree.Root);
Console.WriteLine("===================================");
for (int i = 0; i < 5; i++)
{
int n = rnd.Next(1, 100);
Console.WriteLine("Delete: " + n);
tree.Delete(n);
}
Console.WriteLine("===== InorderTraversal Result =====");
tree.InorderTraversal(tree.Root);
Console.WriteLine("===================================");
以上代码随机生成了 10 个数插入平衡查找树中，然后随机删除其中 5 个数，并输出中序遍历的结果。我们可以通过不断运行这个测试代码，观察平衡查找树的高度是否一直保持在 O(log n)，可以看到平衡查找树的高度始终保持在 O(log n) 左右，证明了平衡查找树的实现是正确的。
本站文章如无特殊说明，均为本站原创，如若转载，请注明出处：C#实现平衡查找树 - Python技术站
微信扫一扫 
支付宝扫一扫 