「Icoding题解」平衡二叉树(AVL)的插入算法

AVL添加

题目链接

平衡二叉树,是一种二叉排序树,其中每个结点的左子树和右子树的高度差至多等于1。它是一种高度平衡的二叉排序树。现二叉平衡树结点定义如下:

typedef struct node
{
    int val;
    struct node *left;
    struct node *right;
    struct node *parent;
    int height;
} node_t;

请实现平衡二叉树的插入算法:

//向根为 root 的平衡二叉树插入新元素 val,成功后返回新平衡二叉树根结点
node_t *avl_insert(node_t *root, int val);

前置知识

AVL定义

平衡二叉搜索树:简称平衡二叉树。由前苏联的数学家Adelse-Velskil和Landis在1962年提出的高度平衡的二叉树,根据科学家的英文名也称为AVL树。它具有如下几个性质:

  1. 可以是空树。
  2. 假如不是空树,任何一个结点的左子树与右子树都是平衡二叉树,并且高度之差的绝对值不超过1。

平衡之意,如天平,即两边的分量大约相同。如定义,假如一棵树的左右子树的高度之差超过1,如左子树的树高为2,右子树的树高为0,子树树高差的绝对值为2就打破了这个平衡。如依次插入1,2,3三个结点(如下图)后,根结点的右子树树高减去左子树树高为2,树就失去了平衡。

那么在建立树的过程中,我们如何知道左右子树的高度差呢?在这里我们采用了平衡因子进行记录。

平衡因子:左子树的高度减去右子树的高度。由平衡二叉树的定义可知,平衡因子的取值只可能为0,1,-1.分别对应着左右子树等高,左子树比较高,右子树比较高。

AVL树的插入时的失衡与调整

不平衡的4种情况

  1. 6节点的左子树3节点高度比右子树7节点大2,左子树3节点的左子树1节点高度大于右子树4节点,这种情况成为左左。
  2. 6节点的左子树2节点高度比右子树7节点大2,左子树2节点的左子树1节点高度小于右子树4节点,这种情况成为左右。
  3. 2节点的左子树1节点高度比右子树5节点小2,右子树5节点的左子树3节点高度大于右子树6节点,这种情况成为右左。
  4. 2节点的左子树1节点高度比右子树4节点小2,右子树4节点的左子树3节点高度小于右子树6节点,这种情况成为右右。

LL型

在LL型的不平衡树中,我们首先找到最小不平衡子树,再以其根结点向右旋转。为何是向右旋转呢?应该不难理解,向右旋转后,相当于右边的子树树高增加了1,而左边的子树树高降低了1,而原本的树高之差为2,那么就能够将根的平衡因子就化为0.引用一下之前的图如下。旋转之后为“原来根结点的左孩子作为新的根结点”。

我们对树以根结点为中心,向右旋转。旋转步骤如下:

  1. 将2作为根结点。
  2. 将3作为2的右孩子。
  3. 将2的右孩子作为3的左孩子(维护树的有序性,只是此处为NULL而已)。

旋转后,3与2的平衡因子为0,1的平衡因子保持不变。

RR型

还是引用一下之前的例子。旋转之后为“原来根结点的右孩子作为新的根结点”。旋转的步骤如下:

  1. 将2作为根结点。
  2. 将1作为2的左孩子。
  3. 将2的左孩子作为1的右孩子(维护树的有序性,只是此处为NULL而已)。

最后1,2,3的平衡因子都为0。

LR型

对于LR,要分为两步进行旋。旋转之后为“原来根结点的左孩子的右孩子作为新的根结点”。

第一以较高子树的根,即1,为中心向左旋转。具体步骤如下:

  1. 将2的左子树作为1的右子树(维护树的有序性,只是此处为NULL而已)。
  2. 将1作为2的左子树。
  3. 将2作为3的左子树。

第二以原树的根,即3为中心,向右旋转。最后结果如下:

旋转后,1,2,3的平衡因子变为0。

RL型

还是引用一下之前的例子。与LR型类似,我们需要进行两次旋转。旋转之后为“原来根结点的右孩子的左孩子作为新的根结点”。

第一,以根结点的右孩子即3为中心向右旋转,结果如下。具体步骤如下:

  1. 将2作为1的右孩子。
  2. 将3作为2的右孩子。
  3. 将2的右孩子作为3的左孩子(维护树的有序性,只是此处为NULL而已)。

第二,以原根结点即1,作为中心,向左旋转。结果如下。具体步骤如下:

  1. 将2作为根结点。

  2. 将1作为2的左孩子。

  3. 将2的左孩子作为1的右孩子(维护树的有序性,只是此处为NULL而已)。

最后1,2,3的平衡因子都是0。

答案代码及注释

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

int getHeight(node_t* root)
{
    int height = 0;
    if (root)
        height = root->height;
    return height;
}
int getMax(int a, int b)
{
    return a > b ? a : b;
}
//LL型
node_t* LL(node_t* root)
{
    node_t* child = root->left;
    root->left = child->right;
    child->right = root;
    root->height = getMax(getHeight(root->left), getHeight(root->right)) + 1;
    child->height = getMax(getHeight(child->left), root->height) + 1;
    return child;
}
//RR型
node_t* RR(node_t* root)
{
    node_t* child = root->right;
    root->right = child->left;
    child->left = root;
    root->height = getMax(getHeight(root->left), getHeight(root->right)) + 1;
    child->height = getMax(root->height, getHeight(child->right)) + 1;
    return child;
}
//RL型
node_t* RL(node_t* root)
{
    //右左调整分两步,先LL再RR
    root->right = LL(root->right);
    return RR(root);
}
//LR型
node_t* LR(node_t* root)
{
    //左右调整分两步,先RR再LL
    root->left = RR(root->left);
    return LL(root);
}
node_t* NewNode(int val)
{
    node_t* newnode = (node_t*)malloc(sizeof(node_t));
    newnode->val = val;
    newnode->left = NULL;
    newnode->right = NULL;
    newnode->parent = NULL;
    newnode->height = 0;
    return newnode;
}
node_t* avl_insert(node_t* root, int val)
{
    if (!root)//如果avl不存在则先创建一个avl
        root = NewNode(val);
    else if (val < root->val) {
        //如果val小于根结点val,则插入左子树
        root->left = avl_insert(root->left, val);
        if (getHeight(root->left) - getHeight(root->right) == 2) {
            //插入后判断平衡因子,如果等于2则需要旋转
            if (val < root->left->val)//LL型
                root = LL(root);
            else//LR型
                root = LR(root);
        }
    } else if (val > root->val) {
        //如果val大于根结点val,则插入右子树
        root->right = avl_insert(root->right, val);
        if (getHeight(root->right) - getHeight(root->left) == 2) {
            //插入后判断平衡因子,如果等于2则需要旋转
            if (val > root->right->val)//RR型
                root = RR(root);
            else//RL型
                root = RL(root);
        }
    }
    root->height = getMax(getHeight(root->left), getHeight(root->right)) + 1;
    return root;
}

发表评论

nv-author-image