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

相关文章

来自专栏fangyangcoder

leetcode(二)

给定一个二叉数(root),二叉树中一个node(target)以及整数K,求二叉树中所有与target距离K的节点值。问题描述与example如下。

572
来自专栏HansBug's Lab

3223: Tyvj 1729 文艺平衡树

3223: Tyvj 1729 文艺平衡树 Time Limit: 10 Sec  Memory Limit: 128 MB Submit: 1347  Sol...

3425
来自专栏zaking's

用js来实现那些数据结构14(树02-AVL树)

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

卡特兰数入门

简介 卡特兰数是组合数学中的一种常见数列 它的前几项为: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58...

3044
来自专栏Java 源码分析

平衡搜索树

2-3树 ​ 其实仔细来看2-3树好像是 B 树的一个特例,它规定了一个节点要么有一个 key 要么有两个 key。 如果有一个 key 那么他就有两个子...

2859
来自专栏青玉伏案

算法与数据结构(七) AOV网的拓扑排序(Swift版)

今天博客的内容依然与图有关,今天博客的主题是关于拓扑排序的。拓扑排序是基于AOV网的,关于AOV网的概念,我想引用下方这句话来介绍: AOV网:在现代化管理中...

1747
来自专栏ml

mxnet框架样本,使用C++接口

哇塞,好久么有跟进mxnet啦,python改版了好多好多啊,突然发现C++用起来才是最爽的. 贴一个mxnet中的C++Example中的mlp网络和实现,感...

4485
来自专栏王亚昌的专栏

A*算法C实现

参考 http://www.cppblog.com/christanxw/archive/2006/04/07/5126.html 实现了A*算法,模拟了一下,...

722
来自专栏老秦求学

短语 ,直接短语,句柄

编译原理概念: 书上的概念如下: 令G是一文法,S是文法的开始符号,αβδ是文法G的一个句型。如果有:   S  αAδ且A  β则称β是句型αβδ相对于非终结...

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

从零开始学建树(树的分治,树的重心)

分治算法在树的路径问题中的应用 一、树的分治算法 树的分治算法是分治思想在树型结构上的体现。 任一个具有n个节点的连通路,它的任何一棵树的树枝数为n-1 分治:...

2394

扫码关注云+社区