搜索树中，由于结点插入顺序不同，将导致不同的深度和不同的平均查找长度（ASL） 二叉搜索树一般ASL计算方法：（每层结点个数 * 层数）之和 / 结点个数

平衡因子（Balance Factor BF）：

BF(T) = \(h_L\) - \(h_R\) (注：\(h_L\) 和 \(h_R\)分别为左右子树的高度)

平衡二叉树（Balance Binary Tree）：AVL树 空树，或者任意结点左右子树高度差绝对值不超过1，即|BF(T)| <= 1

平衡二叉树是为了提升查找效率而提出的一种树的结构，其是基于二叉搜索树的，也就是满足二叉搜索树右大左小的道理。 所以给定节点数为n的AVL树，其最大高度为O(\(log_2n\))

AVL树的结构代码：

1
2
3
4
5
6
7
8
9
10
/* AVL树的类型 */
typedef struct AVLNode *Position;
typedef Position AVLTree;

struct AVLNode{
    ElementType Data;   // 结点数据
    AVLTree Left;   // 左子树
    AVLTree Right;  // 右子树
    int Height; // 树高
};

平衡二叉树要保持平衡态是不容易的，插入一个元素之后，很可能就会破坏平衡，所以为了保证其一直处于平衡态，我们就需讨论在插入元素并破坏平衡态之后如何再次调整为平衡态，同时，还要保证其是二叉搜索树。

平衡二叉树的调整

相关说明： 破坏平衡的结点又可称之为 “麻烦节点” 被破坏平衡的结点又可称之为 “发现者”

RR旋转

也就是 “麻烦节点” 在 “发现者” 右子树的右边

调整方式： 将 “发现者” 右子树的根节点提上来代替 “发现者” 的位置，“发现者”连同其左子树作为新的左子树，而 “发现者” 右子树根节点原来的左子树作为 “发现者” 的右子树，右边不变，如图： RR旋转

代码实现：

调整平衡如上解释，只采用三步即可完成：

  1. 将 “发现者” 右子树的根节点提上来代替 “发现者” 的位置，即将 “发现者” 右子树赋值给一个新结点
  2. “发现者” 右子树根节点原来的左子树作为 “发现者” 的右子树，即将“发现者” 右子树根节点原来的左子树赋值给 “发现者” 的右子树
  3. “发现者” 连同其左子树作为新的左子树，即将 “发现者” 赋值给新树树的左节点
1
2
3
4
5
6
7
8
9
10
11
/* 右单旋 更新高度并返回新结点 B */
AVLTree SingRightRotation(AVLTree A){
    /* 调整平衡树 */
    AVLTree B = A->Right;
    A->Right = B->Left;
    B->Left = A;
    /* 更新高度 */
    A->Height = Max(A->Right->Height, A->Left->Height) + 1;
    B->Height = Max(B->Right->Height, A->Height) + 1;
    return B;
}

LL旋转

也就是 “麻烦节点” 在 “发现者” 左子树的左边

理论以及实现和RR旋转相同，只不过操作位置相反，省去解释

代码： 代码实现的前提：A必须要有一个左子节点B

1
2
3
4
5
6
7
8
9
/* 左单旋 更新高度并返回新结点 B */
AVLTree SingleLeftRotation(AVLTree A){
    AVLTree B = A->Left;    // 将A左子树给B
    A->Left = B->Right; // 将B的右子树给A 成为新A的左子树
    B->Right = A;   // A给B的右子树
    A->Height = Max(A->Left->Height, A->Right->Height) + 1;
    B->Height = Max(B->Left->Height, A->Height) + 1;
    return B;
}

LR旋转

也就是 “麻烦结点” 在左子树的右边

对于LR旋转，我们可以将其分为两步： 1. 首先将 “发现者” 的左子树进行RR旋转

  1. 再将 “发现者” 本身进行LL旋转，返回即可

示意图如下： LR旋转

** 代码：**

1
2
3
4
5
6
7
/* 将B与C做右单旋，C被返回 */
AVLTree DoubleLeftRightRotation(AVLTree A){
    
    /* 注意：A必须有一个左子结点B，且B必须有一个右子结点C */
    A->Left = SingRightRotation(A->Left);
    return SingleLeftRotation(A);
}

RL旋转

也就是 “麻烦结点” 在右子树的左边

与LR旋转对称，RL仍然何以分为两步： 1. 首先将 “发现者” 的右子树进行LL旋转 2. 再将 “发现者” 本身进行RR旋转，返回即可

代码简略，直接省去

平衡二叉树的插入

解决了平衡二叉树的调整问题，我们便可以方便地讨论其插入问题

问题简单，直接上代码

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
AVLTree Insert(AVLTree T, ElementType X){

    if (!T){    // 空树中插入，建立新树
        T = (AVLTree)malloc(sizeof(struct AVLNode));
        T->Data = X;
        T->Height = 0;
        T->Left = T->Right = NULL;
    } else if (X < T->Data){    // 小值 插入左树
        T->Left = Insert(T->Left, X);
        if (T->Left->Height - T->Right->Height == 2)
            if (X < T->Left->Data)  // 判断X插入到左边还是右边
                // 左子树左边
                T = SingleLeftRotation(T);
            else
                // 左子树右边
                T = DoubleLeftRightRotation(T);
    } else if (X > T->Data){    // 大值 插入右树
        T->Right = Insert(T->Right, X);
        if (T->Left->Height - T->Right->Height == -2){
            if (X > T->Right->Data) // 判断X插入到左边还是右边
                // 右子树右边
                T = SingleRightRotation(T);
            else
                // 右子树左边
                T = DoubleRightLeftRotation(T);
        }
    } /* else X == T->Data，无须插入 */ 

    // 更新树高
    T->Height = Max(T->Left->Height, T->Right->Height) + 1;
    return T;
}