平衡二叉树 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 条评论
登录 后参与评论

相关文章

来自专栏吴伟祥

【数据结构】务实篇 原

                                                             还有非线性结构(树、图等)。

753
来自专栏向治洪

算法之红黑树

红黑树(一) 原理和算法详细介 1 R-B Tree简介     R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树...

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

cf633F. The Chocolate Spree(树形dp)

\(g[i]\)表示以\(i\)为根的子树中从\(i\)到叶子节点 加上一条与之不相交的链的最大值

902
来自专栏菩提树下的杨过

“AS3.0高级动画编程”学习:第二章转向行为(上)

因为这一章的内容基本上都是涉及向量的,先来一个2D向量类:Vector2D.as (再次强烈建议不熟悉向量运算的童鞋,先回去恶补一下高等数学-07章空间解释几何...

2006
来自专栏ml

cf------(round)#1 C. Ancient Berland Circus(几何)

C. Ancient Berland Circus time limit per test 2 seconds memory limit per test ...

2403
来自专栏文武兼修ing——机器学习与IC设计

AVL二叉树AVL二叉查找树

AVL二叉查找树 AVL二叉查找树是一种特殊的二叉查找树,其规定 每个节点的左子树和右子树的高度差最多是1 AVL调整算法 AVL树插入一个新的节点到某个...

2334
来自专栏小樱的经验随笔

从零基础学三分查找

今晚是我们学长第二次讲课,讲了一个三分!认真听了一下,感觉不是很难,可能会比二分还简单些!我就把上课讲的内容归纳为一篇文章概述吧!以后也会重点讲解的! 简单点说...

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

HDU 3078 Network

Problem Description The ALPC company is now working on his own network system,...

3427
来自专栏智能算法

十张GIFs让你弄懂递归等概念

链接:http://codingpy.com/article/10-gifs-to-understand-some-programming-concepts/(...

3719
来自专栏趣学算法

数据结构 第17讲 沟通无限校园网——最小生成树(kruskal算法)

构造最小生成树还有一种算法,Kruskal算法:设G=(V,E)是无向连通带权图,V={1,2,…,n};设最小生成树T=(V,TE),该树的初始状态为只有n...

872

扫码关注云+社区