深入理解AVL树的旋转操作（C#语言实现平衡二叉树的关键技术）

AVL树的四种旋转类型

根据失衡节点与其子节点的相对位置，旋转分为以下四种：

1. LL 型（右旋）：插入发生在失衡节点的左孩子的左侧。
2. RR 型（左旋）：插入发生在失衡节点的右孩子的右侧。
3. LR 型（先左旋再右旋）：插入发生在失衡节点的左孩子的右侧。
4. RL 型（先右旋再左旋）：插入发生在失衡节点的右孩子的左侧。

C# 实现：节点定义与辅助方法

首先，我们定义 AVL 树的节点结构和一些辅助方法：

public class AvlNode{    public int Value;    public AvlNode Left;    public AvlNode Right;    public int Height;    public AvlNode(int value)    {        Value = value;        Height = 1; // 新节点高度为1    }}// 获取节点高度（空节点高度为0）private int GetHeight(AvlNode node){    return node == null ? 0 : node.Height;}// 更新节点高度private void UpdateHeight(AvlNode node){    if (node != null)    {        node.Height = 1 + Math.Max(GetHeight(node.Left), GetHeight(node.Right));    }}// 计算平衡因子private int GetBalanceFactor(AvlNode node){    return node == null ? 0 : GetHeight(node.Left) - GetHeight(node.Right);}

1. 右旋（LL 型）

当发生 LL 型失衡时，我们需要对失衡节点进行右旋：

private AvlNode RotateRight(AvlNode y){    AvlNode x = y.Left;    AvlNode T2 = x.Right;    // 执行旋转    x.Right = y;    y.Left = T2;    // 更新高度（注意顺序：先更新y，再更新x）    UpdateHeight(y);    UpdateHeight(x);    return x; // 新的根节点}

2. 左旋（RR 型）

RR 型失衡则需要左旋：

private AvlNode RotateLeft(AvlNode x){    AvlNode y = x.Right;    AvlNode T2 = y.Left;    // 执行旋转    y.Left = x;    x.Right = T2;    // 更新高度    UpdateHeight(x);    UpdateHeight(y);    return y; // 新的根节点}

3. LR 型与 RL 型：组合旋转

这两种情况是前两种的组合：

• LR 型：先对左孩子做左旋，再对当前节点做右旋。
• RL 型：先对右孩子做右旋，再对当前节点做左旋。

在插入或删除后的平衡函数中，我们会根据平衡因子自动判断使用哪种旋转：

private AvlNode Balance(AvlNode node){    if (node == null) return node;    UpdateHeight(node);    int balance = GetBalanceFactor(node);    // LL 型    if (balance > 1 && GetBalanceFactor(node.Left) >= 0)        return RotateRight(node);    // RR 型    if (balance < -1 && GetBalanceFactor(node.Right) <= 0)        return RotateLeft(node);    // LR 型    if (balance > 1 && GetBalanceFactor(node.Left) < 0)    {        node.Left = RotateLeft(node.Left);        return RotateRight(node);    }    // RL 型    if (balance < -1 && GetBalanceFactor(node.Right) > 0)    {        node.Right = RotateRight(node.Right);        return RotateLeft(node);    }    return node;}

完整插入示例

最后，我们将旋转逻辑整合到插入方法中：

public AvlNode Insert(AvlNode node, int value){    // 1. 执行标准 BST 插入    if (node == null)        return new AvlNode(value);    if (value < node.Value)        node.Left = Insert(node.Left, value);    else if (value > node.Value)        node.Right = Insert(node.Right, value);    else        return node; // 不允许重复值    // 2. 更新当前节点高度    UpdateHeight(node);    // 3. 检查是否失衡并旋转    return Balance(node);}

总结

通过以上步骤，我们实现了 C# 平衡二叉树 的核心——旋转操作。掌握这四种旋转是理解 AVL树实现 的关键。在实际开发中，AVL 树适用于频繁查询、较少插入/删除的场景，如数据库索引、内存中的有序字典等。

希望这篇 C#数据结构教程 能帮助你彻底搞懂 AVL 树的旋转机制！动手写一遍代码，你会理解得更深刻。