平衡二叉树(AVL树)的基本操作

发布于 / 数据结构与算法 / Comments Off on 平衡二叉树(AVL树)的基本操作

0x00、平衡二叉树的定义

    平衡二叉树(AVL树)是一种特殊的二叉搜索树,只是在二叉搜索树上增加了对"平衡"的需求。

    假如一棵二叉搜索树,按照“1,2,3,4,5”的顺序插入数据,会发现二叉树甚至变成了一个线性的链表状结构,这样查找数据的时间复杂度就会达到O(n),为了优化这一点,使二叉查找树时间复杂度保持O(log n)的级别,我们就需要调整树的插入方式,使之保持住树的结构。

    

    这里引入一个定义:

        平衡因子:二叉树的某个节点的左子树与右子树高度之差称为结点的平衡因子

    

而平衡二叉树就是要保证平衡因子绝对值不能超过1。也就是左子树高度比右子树高度最多大1

0x01、平衡二叉树的C语言实现

首先定义平衡二叉树,这和定义二叉搜索树有些不同,定义的结构体必须加上当前子树的高度。也就是这样:

struct node{
    int data;    //数据域
    int height;  //当前子树高度
    node* lchild, *rchild;        //左右孩子
};

这样定义的好处是方便上一节点计算平衡因子。

计算平衡因子之前我们先定义计算高度的函数,直接返回root->height即可。如果root为NULL,说明是叶子节点,返回0即可

int getHeight(node* root){
    return root == NULL ? 0 : root->height;
}

接着我们计算平衡因子,即左子树比右子树高了多少:

int getBalanceFactor(node* root){
    return getHeight(root->lchild) - getHeight(root->rchild);
}

当我们执行了插入操作,二叉树发生改变的时候,我们需要重新计算高度。

某节点的高度值等于左右子树高度值最大的,加上1。(这是高度值的定义)

更新高度值:

void updateHeight(node* root){
    root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}

0x02、平衡二叉树的查找

    AVL树的查找与一般二叉搜索树的查找方法一样。代码如下:

void search(node* root, int data){
    if(!root) return;    //查找失败
    if(root->data == data)//找到了
        printf("%d", root->data);
    if(root->data > data) //大了,访问左节点
        search(root->lchild, data);
    else search(root->rchild, data);
}

0x03、平衡二叉树的插入操作

    平衡二叉树的插入操作较为复杂,我们为了保持二叉树的平衡状态,就要在二叉树失衡的时候对二叉树进行旋转。

    常见的旋转方式有LL型(单次右旋)、RR型(单次左旋)、LR型(先左旋,再右旋)、RL型(先右旋,再左旋)

    下面我们进行详细介绍:

1、LL型(单次右旋)

假设一棵平衡二叉树再插入数据后,成了这个样子:

图中的 4 和 12 的高度分别是 3 和 1 ,高度差为 2 ,此时,二叉树不平衡了。对于这种由根节点的左子树的左子树造成平衡因子为2的失衡,我们要使用LL型旋转,即单次右旋,使其平衡。

正确的旋转方式是:使原二叉树的 根节点(K2) 的 左孩子(k1) 做为 新根节点,新根节点(k1) 原来的 右子树(Y) ,做为 原来的根节点(K2) 的左子树

如果记不住的话可以按照这个思路来记忆:

既然左边高度比右边高,就让左子树的根节点称为新根,这样高度就减小了1,我们把左子树K1"揪起来",让原根节点k2"掉下去",这样K1就多了一个孩子,而X小于K1,K2大于K1,Y大于K1且Y小于K2,这样把Y"拽下来"插到K2的左边,仍然符合二叉搜索树的规则,而且还处理好了K1的关系,多么完美!

转转后,K1和K2(新根与原来的根)的高度发生了变化,而XYZ(三个子树)没有发生变化,所以我们只需要更新K1和K2的高度值即可。

用C语言实现,就是:

void LLrotation(node* &root){
    node* temp = root->lchild;    //让temp=K1
    root->lchild = temp->rchild;    //让root的左节点变为Y
    temp->rchild = root;    //让新根K1的右节点指向K2
    //以上,旋转完毕
    updateHeight(temp);    //更新新根的节点高度
    updateHeight(root);    //更新老根的节点高度
    root = temp;    //把树的根换成我们定义的新根
}

2、RR型(单次左旋)

假设一棵二叉树插入数据后的状态:

很显然,失衡了。平衡因子为-2。对于这种根节点的右子树的右子树造成平衡因子为-2的失衡,我们采用RR旋转,即单次左旋。

单次左旋的思路就是单次右旋倒过来想,我们先将原根节点的右节点K2当做新根,将K2的左子树当做原根K1的右子树。

同样的,只有K1和K2的高度发生了变化,所以我们只需要更新K1和K2的高度即可。

C语言实现:

void RRrotation(node* &root){
    node* temp = root->rchild;    //另temp=K2
    root->rchild = temp->lchild;    //旧根的右节点为新根的左节点
    temp->lchild = root;    //新根的右节点等于旧根
    //以上,旋转完毕
    updateHeight(temp);    //更新节点高度
    updateHeight(root);
    root = temp;    //重赋值
}

3、LR型(先单次左旋,后单次右旋)

一棵二叉树,插入数据后形成了这个鬼样子

4的高度为3; 而12的高度为1,平衡因子即高度差为2,这是由于根节点的左子树的右子树造成了平衡因子为2的失衡,通常采用LR型旋转,即先左旋,后右旋。

先左旋,也就是让K3的左孩子单次左旋,以K1为根节点,进行单次左旋,使得K2成为根节点,K1成为K2的左节点,K2原来的左节点B成为K1的右节点。这样就完成了单次左旋

接着对左旋后的二叉树,以K3为根节点,进行单次右旋,让K3的左节点K2成为新根,K2的右孩子C成为K3的左孩子,让K3做K2的右孩子。

这里K1、K2、K3的高度均发生了变化,ABCD的高度没有发生变化。

说起来很麻烦,其实实现起来很简单。因为我们有了前面LL旋转和RR旋转的基础,直接对子树操作即可。

C语言实现:

void LRrotation(node* &root){
    RRrotation(root->lchild);    //先对根节点的左孩子单次左旋
    LLrotation(root);
}

4、RL型(先单次右旋,后单次左旋)

二叉树数据插入后:

此时的状态是:由于根节点的右节点的左子树造成了平衡因子为-2的失衡,我们通常采用RL型旋转,即先单次右旋,后单次左旋。

其实就是把LR倒过来啦,不做详细解释了。(敲键盘敲的手指好痛,呜呜呜~~~~(>_<)~~~~)

C语言实现:

void RLrotation(node* &root){
    LLrotation(root->rchild);    //先对根节点的左孩子单次左旋
    RRrotation(root);
}

写了这么多,总结一下吧。根据这个表格进行判断AVL树以何种旋转类型保持平衡:

树型 判定条件 调整方法
LL(单次右旋) BF(root) = 2;BF(root->lchild) = 1 对root单次右旋
RR(单次左旋) BF(root) =-2;BF(root->rchild) =-1

对root单次左旋

LR(先左后右) BF(root) = 2;BF(root->lchild) =-1 对root->lchild进行左旋,再对root进行右旋
RL(先右后左) BF(root) =-2;BF(root->rchild) = 1 对root->rchild进行右旋,再对root进行左旋

*BF代表平衡因子

0x04、二叉平衡树的插入

还记得二叉搜索树是怎样插入数据的吗?

void insert(node* &root, int data){
    if(root == NULL){
        root = new node;
        root->data = data;
        root->lchild = root->rchild = NULL;
    }
    if(root->data <= data)
        insert(root->rchild, data);
    else insert(root->lchild, data);
}

这段代码是不考虑平衡关系的插入代码。我们要做的是在这串代码上稍加修改,使之能及时通过旋转,保证平衡关系。

我们的思路是:沿用上面代码进行插入,插入后更新树的高度,接着判断平衡因子,根据平衡因子判断四种类型的旋转,最后执行旋转。

C语言实现:

void insert(node* &root, int data){
    if(root == NULL){    //插入位置
        root = new node;
        root->data = data;
        root->lchild = root->rchild = NULL;
        root->height = 1;    //由于插入的时候是叶子节点,所以初始高度为1
        return;
    }
    if(root->data > data){    //节点数据大,往左插入
        insert(root->lchild, data);    //继续递归寻找插入位置
        updataHeight(root);        //因为插入了一个节点,所以树根的高度会发生变化
        if(getBalanceFactor(root) == 2)    //根节点平衡因子为2
            if(getBalanceFactor(root->lchild) == 1) //根节点左孩子平衡因子为1,根据表格,采用LL型
                LLrotation(root);
            else if(getBalanceFactor(root->lchild) == -1)   //根节点左孩子平衡因子为-1,LR型
                LRrotation(root);
    }
    else{    //节点数据小,往右插入
        insert(root->rchild, data);
        updataHeight(root);
        if(getBalanceFactor(root) == -2){
            if(getBalanceFactor(root->rchild) == -1) //RR型
                RRrotation(root)
            else if(getBalanceFactor(root->rchild) == 1)//RL型
                RLrotation(root);
        }
    }
}

这里往左插入后,只需要判断平衡因子是否为2,是因为如果树之前是平衡的,往左插入的时候,不可能造成平衡因子为-2,只有往右插入的时候才会是-2,所以判断平衡因子 是否为-2就多余了。

转载原创文章请注明,转载自: 斐斐のBlog » 平衡二叉树(AVL树)的基本操作
评论已关闭