平衡二叉树 AVL 的插入节点后旋转方法分析

平衡二叉树 AVL( 发明者为Adel'son-Vel'skii 和 Landis)是一种二叉排序树,其中每一个节点的左子树和右子树的高度差至多等于1。

首先我们知道,当插入一个节点,从此插入点到树根节点路径上的所有节点的平衡都可能被打破,如何解决这个问题呢?

这里不讲大多数书上提的什么平衡因子,什么最小不平衡子树,实际上让人(me)更加费解。实际上你首要做的就是先找到第一个出现不平衡的节点,也就是从插入点到root节点的路径上第一个出现不平衡的节点,即深度最深的那个节点A,对以它为根的子树做一次旋转或者两次旋转,此时这个节点的平衡问题解决了,整个往上路径经过的节点平衡问题也随之解决。

注:AVL 树也是一种二叉查找树,故删除策略可以参照前面文章来实现,只是删除节点后,如果平衡被打破,则也需要进行旋转以保持平衡。

After deletion, retrace the path back up the tree (parent of the replacement) to the root, adjusting the balance factors as needed.

下面先来分析下不平衡发生的四种情况:

1、An insertion into the left subtree of the left child of A; (LL)

2、An insertion into the right subtree of the left child of A;(RL)

3、An insertion into the left subtree of the right child of A;(LR)

4、An insertion into the right subtree of the right child of A;(RR)

旋转方法:

1、A 和 A's child 顺时针旋转 singlerotateLL()

4、A 和 A's child 逆时针旋转 singlerotateRR()

2、A's child 和 A's grandchild 逆时针旋转,A 和 A's new child 顺时针旋转  doublerotateRL()

3、A's child 和 A's grandchild 顺时针旋转,A 和 A's new child 逆时针旋转 doublerotateLR()

可以看出1,4对称;2,3对称,实际在实现 rotate 函数的时候实现1和4 即可,2和3直接调用1&4的实现。在实现1&4时需要传递需要旋转的子树的root node 作为参数,如 nodePtr doublerotateRL(A) { A->left = singlerotateRR(A->left);  return singlerotateLL(A);}  

当然,这样说还是对应不上,下面上图分析。

第一种情况举例:

现在想要插入的点是6,请看是否符合第一种情况的描述。8是不是深度最深的发生不平衡的点?6是不是插入在A的左孩子的左子树?符合是吧,那就直接按上述方法顺时针旋转7和8,效果是右图。当然这只是逻辑上的视图而已,真正函数实现也不难,就是修改两个指针指向,待会再谈。第4种情况是对称的,就不说了。

下面来看第三种情况示例:

现在要插入的点是14,请看是否符合第3种情况的描述。6是不是深度最深的发生不平衡的点?14是不是插入在A的右孩子的左子树?符合是吧,那就先顺时针旋转7和15,中间结果如下图所示:

现在7是A的new child了是吧,那就逆时针旋转6和7就可以了。

接着来分析singlerotateLL() 和doublerotateRL() 的实现,剩下两个函数就是对称的了。

首先是singlerotateLL(),看下图:

改动其实很简单,先把Y解绑当k2的左孩子,接着k2成为k1的右孩子,代码如下:

/* return pointer to the new root */
static AVLNodePtr singlerotateLL(AVLNodePtr k2)
{
    AVLNodePtr k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = Max(height(k2->left), height(k2->right)) + 1;
    k1->height = Max(height(k1->left), k2->height) + 1;
    return k1;
}

接着是doublerotateRL()的实现,看下图:

很明显B或者C的插入使得k3(A)不平衡了,那么首先应该是k1和k2逆时针旋转,所以调用

k3->left = singlerotateRR(k3->left);

接着是k3和new child 顺时针旋转,调用singlerotateLL(k3);

so easy, 代码如下:

static AVLNodePtr doublerotateRL(AVLNodePtr k3)
{
    k3->left = singlerotateRR(k3->left);
    return singlerotateLL(k3);
}

完整的测试代码如下:

#include <stdio.h>
#include <stdlib.h>

struct AVLNode;
typedef struct AVLNode *AVLNodePtr;

struct AVLNode
{
    int element;
    AVLNodePtr left;
    AVLNodePtr right;
    int height;
};

void makeempty(AVLNodePtr T)
{
    if (T == NULL)
        return;
    else
    {
        makeempty(T->left);
        makeempty(T->right);
        free(T);
    }
}

static int height(AVLNodePtr p)
{
    if (p == NULL)
        return -1;
    else
        return p->height;
}

static int Max(int ln, int rn)
{
    return ln > rn ? ln : rn;
}

/* return pointer to the new root */
static AVLNodePtr singlerotateLL(AVLNodePtr k2)
{
    AVLNodePtr k1 = k2->left;
    k2->left = k1->right;
    k1->right = k2;
    k2->height = Max(height(k2->left), height(k2->right)) + 1;
    k1->height = Max(height(k1->left), k2->height) + 1;
    return k1;
}

static AVLNodePtr singlerotateRR(AVLNodePtr k1)
{
    AVLNodePtr k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;
    k1->height = Max(height(k1->left), height(k1->right)) + 1;
    k2->height = Max(k1->height, height(k2->right)) + 1;
    return k2;
}

static AVLNodePtr doublerotateRL(AVLNodePtr k3)
{
    k3->left = singlerotateRR(k3->left);
    return singlerotateLL(k3);
}

static AVLNodePtr doublerotateLR(AVLNodePtr k3)
{
    k3->right = singlerotateLL(k3->right);
    return singlerotateRR(k3);
}


AVLNodePtr insert(int X, AVLNodePtr T)
{
    if (T == NULL)
    {
        /* create and return a one-node tree */
        T = (AVLNodePtr)malloc(sizeof(struct AVLNode));
        if (T == NULL)
        {
            printf("out of space!");
            exit(1);
        }
        else
        {
            T->element = X;
            T->height = 0;
            T->left = T->right = NULL;
        }
    }

    else if (X < T->element)
    {
        T->left = insert(X, T->left);
        if (height(T->left) - height(T->right) == 2)
        {
            if (X < T->left->element)
                T = singlerotateLL(T);
            else
                T = doublerotateRL(T);
        }
    }

    else if (X > T->element)
    {
        T->right = insert(X, T->right);
        if (height(T->right) - height(T->left) == 2)
        {
            if (X > T->right->element)
                T = singlerotateRR(T);
            else
                T = doublerotateLR(T);
        }
    }
    /* else X is in the tree already; we'll do nothing */
    T->height = Max(height(T->left), height(T->right)) + 1;
    return T;
}

void inorder(AVLNodePtr T)
{
    if (T == NULL)
        return;
    else
    {
        inorder(T->left);
        printf("%d ", T->element);
        inorder(T->right);
    }
}

int main(void)
{
    int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};
    AVLNodePtr T = NULL;
    for (int i = 0; i < sizeof(arr) / sizeof(arr[0]); i++)
        T = insert(arr[i], T);

    inorder(T);
    makeempty(T);
    return 0;
}

代码将数组元素插入后,中序遍历后输出,即1~16的顺序排列。

注意:输入数组元素就不要搞成有序的了,如果代码中没有调整的实现,整个树就是个右斜树,但即使实现了调整,也会使得每插入一次就调整一次,何必内耗啊。很显然,平衡二叉树的优势在于不会出现普通二叉查找树的最差情况。其查找的时间复杂度为O(logN)。

注:理解旋转函数的实现关键在于理解实现时的限制:

The key to understanding how a rotation functions is to understand its constraints. In particular the order of the leaves of the tree (when read left to right for example) cannot change (another way to think of it is that the order that the leaves would be visited in a depth first search must be the same after the operation as before ).

Another constraint is the main property of a binary search tree, namely that the right child is greater than the parent and the left child is lesser than the parent.

Detailed illustration:

Using the terminology of Root for the parent node of the subtrees to rotate, Pivot for the node which will become the new parent node,RS for rotation side upon to rotate and OS for opposite side of rotation. In the above diagram for the root Q, the RS is C and the OS is P. The pseudo code for the rotation is:

Pivot = Root.OS Root.OS = Pivot.RS Pivot.RS = Root Root = Pivot

参考:

《data structure and algorithm analysis in c》

《Data Structures》

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Leetcode名企之路

【Leetcode】62. 不同路径

一个机器人位于一个 m x n 网格的左上角 (起始点在下图中标记为“Start” )。

851
来自专栏数据结构与算法

P1774 最接近神的人_NOI导刊2010提高(02)

题目描述 破解了符文之语,小FF开启了通往地下的道路。当他走到最底层时,发现正前方有一扇巨石门,门上雕刻着一幅古代人进行某种活动的图案。而石门上方用古代文写着“...

2596
来自专栏闻道于事

JavaScript函数之递归

递归 递归的本质就是使用函数自身来解决问题的思路。 递归的定义(摘): 程序调用自身的编程技巧称为递归( recursion)。递归做为一种算法在程序设计语言中...

2888
来自专栏ACM算法日常

最高的牛Tallest Cow(前缀和)- POJ 3263

FJ's N (1 ≤ N ≤ 10,000) cows conveniently indexed 1..N are standing in a line. E...

931
来自专栏阮一峰的网络日志

快速排序(Quicksort)的Javascript实现

日本程序员norahiko,写了一个排序算法的动画演示,非常有趣。 这个周末,我就用它当做教材,好好学习了一下各种排序算法。 ? 排序算法(Sorting al...

2735
来自专栏屈定‘s Blog

算法回顾--如何写递归?

总之递归就是”装傻”的把原始的思路表现出来,不需要关心具体过程,只需要不停的缩小问题规模,然后答案自然就会被计算出来.

1272
来自专栏软件开发 -- 分享 互助 成长

模式分解是否为无损连接的判断方法

方法一:无损连接定理 关系模式R(U,F)的一个分解,ρ={R1<U1,F1>,R2<U2,F2>}具有无损连接的充分必要条件是: U1∩U2→U1-U2 €F...

2107
来自专栏desperate633

LintCode斐波纳契数列题目:分析小结

查找斐波纳契数列中第 N 个数。 所谓的斐波纳契数列是指: 前2个数是 0 和 1 。 第 i 个数是第 i-1 个数和第i-2 个数的和。

411
来自专栏SeanCheney的专栏

《Pandas Cookbook》第05章 布尔索引1. 计算布尔值统计信息2. 构建多个布尔条件3. 用布尔索引过滤4. 用标签索引代替布尔索引5. 用唯一和有序索引选取6. 观察股价7. 翻译SQ

第01章 Pandas基础 第02章 DataFrame运算 第03章 数据分析入门 第04章 选取数据子集 第05章 布尔索引 第06章 索引对齐 ...

662
来自专栏聊聊技术

原 初学算法-快速排序与线性时间选择(De

3086

扫码关注云+社区