RobbEr's Blog

Welcome

数据结构-二叉平衡树

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 2.8k 阅读时长 ≈ 3 分钟

简介

什么是二叉平衡树

二叉平衡树，又叫AVL树，它可以是一颗空树，或者具有以下性质的二叉排序树：它的左子树和右子树的高度之差(平衡因子)的绝对值不超过1且它的左子树和右子树都是一颗平衡二叉树

平衡因子

平衡因子 = 左子树高度 - 右子树高度

为什么要有二叉平衡树

二叉搜索树可以在一定程度上提高搜索效率，但当原序列有序，如{ 1, 2, 3, 4, 5, 6}，二叉树的结构如图，此时构造的二叉搜索树为右斜树，同时二叉树退化成单链表

此时查找元素6所需的的次数为6

二叉搜索树的查询效率取决于树的高度，因此保持树的高度最小，即可保证树的查找效率。同样的序列 A，将其改为下图的方式存储，查找元素 6 时只需比较 3 次，查找效率提升一倍

由上面可得：当节点数目一定时，树的左右两端保持平衡，查询效率最高，由此引出二叉平衡树

失衡与调整

失衡

如图为一颗二叉平衡树

插入一个 92 后

此时根节点 59 的左子树高度为 1 右子树高度为 3，平衡因子为 -2，树失去平衡，且以 59 为节点的树就称为最小失衡子树

最小失衡子树

在新插入的结点向上查找，以第一个平衡因子的绝对值超过 1 的结点为根的子树称为最小不平衡子树。也就是说，一棵失衡的树，是有可能有多棵子树同时失衡的。而这个时候，我们只要调整最小的不平衡子树，就能够将不平衡的树调整为平衡的树

调整

平衡二叉树的失衡调整主要是通过旋转最小失衡子树来实现的

根据旋转的方向有两种处理方式，左旋与右旋

左旋

当树的右子树高于左子树时，对该树进行左旋操作：

  1. 节点的右孩子替代此节点位置
  2. 右孩子的左子树变为该节点的右子树
  3. 节点本身变为右孩子的左子树

右旋

右旋操作与左旋类似，操作流程为：

  1. 节点的左孩子代表此节点
  2. 节点的左孩子的右子树变为节点的左子树
  3. 将此节点作为左孩子节点的右子树

二叉平衡树的四种插入节点情况

假设一颗 AVL 树的某个节点为 A，有四种操作会使 A 的左右子树高度差大于 1，从而破坏了原有 AVL 树的平衡性。平衡二叉树插入节点的情况分为以下四种：

插入方式 描述 旋转方式
LL 在 A 的左子树根节点的左子树上插入节点而破坏平衡 右旋
RR 在 A 的右子树根节点的右子树上插入节点而破坏平衡 左旋
LR 在A的左子树根节点的右子树上插入节点而破坏平衡 先左旋后右旋
RL 在 A 的右子树根节点的左子树上插入节点而破坏平衡 先右旋后左旋

LL

代码实现右旋

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
34
//返回值:新父节点
Tree LL_rotate(Tree node){
    //node为离操作结点最近的失衡的结点
    Tree parent=NULL,son;
    //获取失衡结点的父节点
    parent=node->parent;
    //获取失衡结点的左孩子
    son=node->lchild;
    //设置son结点右孩子的父指针
    if (son->rchild!=NULL)  son->rchild->parent=node;
    //失衡结点的左孩子变更为son的右孩子
    node->lchild=son->rchild;
    //更新失衡结点的高度信息
    update_depth(node);
    //失衡结点变成son的右孩子
    son->rchild=node;
    //设置son的父结点为原失衡结点的父结点
    son->parent=parent;
    //如果失衡结点不是根结点，则开始更新父节点
    if (parent!=NULL){
        //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son
        if (parent->lchild==node){
            parent->lchild=son;
        }else{
             //父节点的右孩子是失衡结点
              parent->rchild=son;
        }
     }
    //设置失衡结点的父亲
    node->parent=son;
    //更新son结点的高度信息
    update_depth(son);
    return son;
}

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
34
35
36
//返回值:新父节点
Tree RR_rotate(Tree node){
    //node为离操作结点最近的失衡的结点
    Tree parent=NULL,son;
    //获取失衡结点的父节点
    parent=node->parent;
    //获取失衡结点的右孩子
    son=node->rchild;
    //设置son结点左孩子的父指针
    if (son->lchild!=NULL){
          son->lchild->parent=node;
    }
    //失衡结点的右孩子变更为son的左孩子
    node->rchild=son->lchild;
    //更新失衡结点的高度信息
    update_depth(node);
    //失衡结点变成son的左孩子
    son->lchild=node;
    //设置son的父结点为原失衡结点的父结点
    son->parent=parent;
    //如果失衡结点不是根结点，则开始更新父节点
    if (parent!=NULL){
        //如果父节点的左孩子是失衡结点，指向现在更新后的新孩子son
        if (parent->lchild==node){
            parent->lchild=son;
        }else{
            //父节点的右孩子是失衡结点
            parent->rchild=son;
        } 
    }
    //设置失衡结点的父亲
    node->parent=son;
    //更新son结点的高度信息
    update_depth(son);
    return son;
}

LR

LR 需要进行两部操作：

  1. 对失衡节点的左孩子进行左旋操作，即上述 RR 情形操作
  2. 对失衡节点做右旋操作，即上述 LL 情形操作

代码实现

1
2
3
4
5
//返回值：新父节点
Tree LR_rotate(Tree node){
    RR_rotate(node->lchild);
    return LL_rotate(node);
}

RL

RL 需要进行两部操作：

  1. 对失衡节点的右孩子进行右旋操作，即上述 LL 情形操作
  2. 对失衡节点做左旋操作，即上述 RR 情形操作

代码实现

1
2
3
4
5
//返回值：新父节点
Tree RL_rotate(Tree node){
    LL_rotate(node->lchild);
    return RR_rotate(node);
}

小结

  1. 在所有的不平衡情况中，都是按照先 寻找最小不平衡树，然后 寻找所属的不平衡类别，再 根据 4 种类别进行固定化程序的操作
  2. LL , LR ，RR ，RL 其实已经为我们提供了最后哪个结点作为新的根指明了方向，只要记住这四种情况，可以很快地推导出所有的情况