树-二叉平衡树AVL

基本概念

AVL树:树中任何节点的两个子树的高度最大差别为1。

AVL树的查找、插入和删除在平均和最坏情况下都是O(logn)。

AVL实现

AVL树的节点包括的几个组成对象:
(01) key -- 是关键字,是用来对AVL树的节点进行排序的。
(02) left -- 是左孩子。
(03) right -- 是右孩子。
(04) height -- 是高度。即空的二叉树的高度是0,非空树的高度等于它的最大层次(根的层次为1,根的子节点为第2层,依次类推)。

AVL旋转算法

AVL失衡四种形态:

LL(根的左子树的左子树高):根节点的左子树的左子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2。

LR(根的左子树的右子树高):根节点的左子树的右子树还有非空子节点,导致"根的左子树的高度"比"根的右子树的高度"大2。

RL(根的右子树的左子树高):根节点的右子树的左子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2。

RR(根的右子树的右子树高):根节点的右子树的右子树还有非空子节点,导致"根的右子树的高度"比"根的左子树的高度"大2。

旋转算法实现

1 LL(一步到位)

LL失去平衡的情况,可以通过一次旋转让AVL树恢复平衡。如下图:

树-二叉平衡树AVL_第1张图片

图中左边是旋转之前的树,右边是旋转之后的树。从中可以发现,旋转之后的树又变成了AVL树,而且该旋转只需要一次即可完成。
对于LL旋转,你可以这样理解为:LL旋转是围绕"失去平衡的AVL根节点"进行的,也就是节点k2;而且由于是LL情况,即左左情况,就用手抓着"左孩子,即k1"使劲摇。将k1变成根节点,k2变成k1的右子树,"k1的右子树"变成"k2的左子树"。

/*
* LL:左左对应的情况(左单旋转)。
*
* 返回值:旋转后的根节点
*/
static Node* left_left_rotation(AVLTree k2)
{
    AVLTree k1;

    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;
}

2 RR(一步到位)

理解了LL之后,RR就相当容易理解了。RR是与LL对称的情况!RR恢复平衡的旋转方法如下:

树-二叉平衡树AVL_第2张图片

图中左边是旋转之前的树,右边是旋转之后的树。RR旋转也只需要一次即可完成。

/*
* RR:右右对应的情况(右单旋转)。
*
* 返回值:旋转后的根节点
*/
static Node* right_right_rotation(AVLTree k1)
{
    AVLTree k2;

    k2 = k1->right;
    k1->right = k2->left;
    k2->left = k1;

    k1->height = MAX( HEIGHT(k1->left), HEIGHT(k1->right)) + 1;
    k2->height = MAX( HEIGHT(k2->right), k1->height) + 1;

    return k2;
}

3 LR(两步旋转RR->LL)

LR失去平衡的情况,需要经过两次旋转才能让AVL树恢复平衡。如下图:

树-二叉平衡树AVL_第3张图片
第一次旋转是围绕"k1"进行的"RR旋转",第二次是围绕"k3"进行的"LL旋转"。

/*
* LR:左右对应的情况(左双旋转)。
*
* 返回值:旋转后的根节点
*/
static Node* left_right_rotation(AVLTree k3)
{
    k3->left = right_right_rotation(k3->left);

    return left_left_rotation(k3);
}

4 RL(两步旋转LL->RR)

RL是与LR的对称情况!RL恢复平衡的旋转方法如下:

树-二叉平衡树AVL_第4张图片

第一次旋转是围绕"k3"进行的"LL旋转",第二次是围绕"k1"进行的"RR旋转"。

/*
* RL:右左对应的情况(右双旋转)。
*
* 返回值:旋转后的根节点
*/
static Node* right_left_rotation(AVLTree k1)
{
    k1->right = left_left_rotation(k1->right);

    return right_right_rotation(k1);
}

 

AVL操作

插入

步骤1:递归插入到左子树或右子树(left<root<right);

步骤2:比较左右子树高度来确定AVL失衡处理类型:

插入到左子树,就有LL和LR:通过left<root<right确定;

插入到右子树,就有RL和RR:通过left<root<right确定;

步骤3:修正树高。

删除

你可能感兴趣的