平衡二叉树

引入

我们曾经学习过二叉搜索树（Binary Search Tree，(BST))。它的插入和查找效率可以达到 o(log2nlog_2n) ，但是在一些情况下，比如输入序列为{1, 2, 3, 4, 5, 6}，二叉搜索树将会退化成为一个单链表，这样对于插入和查找效率又回到了 o(n) 。因此引出平衡二叉树

性质

平衡二叉树具有以下性质

  1. 任意结点的左右子树也是平衡二叉树
  2. 任意结点的左右子树高度差的绝对值小于等于1

我们定义某个结点的左右子树高度差为平衡因子，平衡二叉树的所有结点的平衡因子都小于属于{-1, 0, 1}

结点组成结构

1
2
3
4
5
typedef struct AVLNode {
    int data;
    int height;
    struct AVLNode *left, *right;
} Node, *Nodeprt;

失衡

对于一颗平衡二叉树来说，插入一个结点可能导致失衡

我们在原本平衡的树上插入20结点，导致失衡，因为13结点的左右子树高度差的绝对值大于1

这时我们需要相应的操作对这颗树进行调整，我们需要先了解最小不平衡子树的概念

最小不平衡子树

从新插入的结点向上寻找，找到第一个不平衡点（左右子树差值的绝对值大于1）（平衡因子绝对值大于1），上图中，最小不平衡子树为13号结点为根的树。

往往很多时候第一个不平衡点并不是整棵树的树根，只是一颗子树，这时我们只需要调整子树即可

旋转

通过旋转操作调整最小不平衡子树，从而最终形成平衡二叉树，以下所有操作的描述起点都是当前对应的第一个不平衡点，也就是最小不平衡子树的树根，以下分类按照不平衡点的位置划分，

按照引起不平衡的点进行四种类比划分——左左，右右，左右，右左

左旋（右孩子的右子树）

  • 节点（20）的右孩子（25）代替当前节点（20）的位置
  • 右孩子（25）的左孩子（24）作为当前结点（20）的右孩子【前提是右孩子（25）有左孩子（24）】
  • 当前结点（20）变成右孩子（25）的左子树

例子：

插入结点20之后，二叉树失衡，进行左旋调整

左旋调整代码（右孩子的右子树）

1
2
3
4
5
6
7
8
9
10
Nodeprt right_right(Nodeprt tree) {//左旋
    //结点调整
    Nodeprt k = tree->right;//保存右孩子，最终成为子树根节点
    tree->right = k->left;//k的左孩子作为tree的右子树
    k->left = tree;//tree作为k的左子树
    //高度调整
    k->height = max(k->left->height, k->right->height) + 1;
    tree->height = max(tree->left->height, tree->right->height) + 1;
    return k;
}

右旋（左孩子的左子树）

  • 当前结点（20）的左孩子（16）代替当前结点（20）的位置
  • 左孩子（16）的右子树（18）变成当前结点（20）的左孩子【前提是左孩子（16）有右子树（18）】
  • 当前结点（20）变成左孩子（16）的右子树

例子：

插入结点1之后，二叉树失衡，进行右旋调整

右旋调整代码（左孩子的左子树）

1
2
3
4
5
6
7
8
9
10
Nodeprt left_left(Nodeprt tree) {//右旋
    //结点调整
    Nodeprt k = tree->left;//保存右孩子，最终成为子树根节点
    tree->left = k->right;//k的右孩子作为tree的左子树
    k->right = tree;//tree作为k的右子树
    //高度调整
    k->height = max(k->left->height, k->right->height) + 1;
    tree->height = max(tree->left->height, tree->right->height) + 1;
    return k;
}

先左旋再右旋（左孩子的右子树）

新插入的9号结点造成二叉树失衡，向上寻找最小不平衡子树的根节点为13，9在13的左孩子的右子树。先对13的左孩子进行左旋，再对13进行右旋。

左旋再右旋（左孩子的右子树）

1
2
3
4
5
Nodeprt left_right(Nodeprt tree){
    tree->left=right_right(tree->left);//左子树左旋
    tree=left_left(tree);//自身右旋
    return tree;
}

先右旋再左旋（右孩子的右子树）

新插入的14号结点造成二叉树失衡，向上寻找最小不平衡子树的根节点13，14在13的右孩子的左子树，先对右孩子18右旋，再对13左旋。

右旋再左旋（右孩子的左子树）

1
2
3
4
5
Nodeprt right_left(Nodeprt tree) {
    tree->right = left_left(tree->right);
    tree = right_right(tree);
    return tree;
}

失衡调整总结

以A结点作为最小不平衡子树的根节点

插入位置 描述 调整方式

​ LL 在结点A的左孩子的左子树插入导致A失衡 A右旋

​ RR 在结点A的右孩子的右子树插入导致A失衡 A左旋

​ LR 在结点A的左孩子的右子树插入导致A失衡 A的左子左旋，A右旋

​ RL 在结点A的右孩子的左子树插入导致A失衡 A的右子右旋，A左旋

插入的最终代码

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
Nodeprt insert(Nodeprt tree, int key) {
    if (tree == NULL) {
        Nodeprt p = build_node(key);
        tree = p;
    } else if (key < tree->data) {
        tree->left = insert(tree->left, key);//递归插入左子树
        //在左侧插入，只可能左侧比右侧高了2导致失衡
        if (tree->left->height - tree->right->height == 2) {
            //判断左子树还是右子树是插入位置
            if (key < tree->left->data) {//左左
                tree = left_left(tree);
            } else tree = left_right(tree);//左右
        }
    } else if (key > tree->data) {//递归插入右子树
        tree->right = insert(tree->right, key);
        ///在右侧插入，只可能右侧比左侧高2导致失衡
        if (tree->right->height - tree->left->height == 2) {
            //判断左子树还是右子树插入
            if (key > tree->right->data) {//右右
                tree = right_right(tree);
            } else tree = right_left(tree);//右左
        }
    } else printf("不允许插入重复值\n");
    tree->height = max(tree->left->height, tree->right->height) + 1;
    return tree;
}

删除结点

删除操作过于复杂，后面有机会再补充，和普通二叉树的删除操作一起补充。

上述代码或者描述有问题的请联系作者（代码还未测试…）

感谢博主文章平衡二叉树（详细解释+完整C语言）_～在下小吴的博客-CSDN博客