数据结构(AVL树)

BST的退化

仔细观察BST你会发现，虽然他有良好的“搜索”特性，也就是：你可以利用其节点之间的大小关系，很容易地从根节点开始往下走找到你要的节点，但他却无法保证这种搜索所需要的时间的长短，因为建立BST时节点的随机性可能会导致他极其“不平衡”，什么叫不平衡呢？来看一个例子便马上知晓。

假设你创建了一棵空的BST，然后你接连依次插入节点1、2、3、4、5，这会出现什么情况呢？利用draw()函数来帮我们一看究竟，你会发现这棵BST将变成成这样

平衡树的定义

这棵“畸形”的二叉树虽然依旧是一棵标准的BST，但却已经明显左轻右重了，事实上这棵二叉树已经退化成了一条链表，在这棵BST中搜索某一节点的时间复杂度跟链表是一样的。
这种“左轻右重”或者“左重右轻”的长短腿的情形，就是所谓的不平衡，一棵树如果不平衡，那么他的搜索性能将会受到影响，具体来讲：当树保持平衡时，其搜索时间复杂度是O(log2n)O(log2​n)，当树退化成链表时，其搜索时间复杂度变成O(n)O(n)，其他情况下树的平均搜索时间复杂度就介于这两者之间。现在的目标，就是要升级我们的BST，使之带有自平衡的特性，当他发现自己的左腿长或者右腿长的时候，会及时调整，保持平衡。

要达到此目的，首先需要量化所谓的“平衡”，平衡的严格数学定义是：在一棵树中，如果其任意一个节点的左、右子树的高度差绝对值小于等于1，那么它就是平衡的。比如下面几棵树都是平衡树：

上图中每一个节点右上方的数字代表以其为根的树的高度，如果一个节点的子树为空，那么规定空树的高度为0。再来看两棵非平衡树：

图中红色的节点就是失去平衡的节点，左边二叉树的根节点的右腿太长，右边的是左腿太长，不管是哪种情况，左右两边的子树高度差绝对值都已经超过了1。

AVL树

所谓AVL树，就是要求树中的任何一棵子树的高度差都严格小于或等于1。构造AVL树的关键，是引入一种被称为“旋转”的特殊操作。

不平衡产生的原因

下图中填充了斜线的节点代表新插入的节点，是他们的插入导致了红色节点出现了不平衡。例如第一种情况：原先红节点的左子树已经较其右子树高，现在其左子树又新增了一个左子节点，于是这种不平衡被称为“左-左不平衡”。类似地，如果其左子树新增的是一个右子节点也会导致不平衡，这就是第二种情况“左-右不平衡”。而第三和第四种情况，则完全是对称的。

跟插入算法一样，删除节点的时候也会导致原来平衡的树变得不再平衡，而不平衡的类型跟插入时导致的四种类型是完全一样的，请看下图：

旋转操作

以第一种“左-左不平衡”为例，应该怎么处理呢？注意这里的“处理”指的是：既要维持原有的二叉搜索树的特性，即“小-中-大”的搜索特性，又要使得它恢复平衡。以前在讨论各种线性表的时候，都会设计一套其常规操作，例如初始化、插入、删除、查询节点、遍历等等，二叉树也不例外，但是二叉树实际上还有一类标准常规操作，他们叫旋转。处理“左-左不平衡”就要用到旋转操作。

按照上图所示，所谓“右旋转”是一种对树的节点的常规操作，形象上讲，就是将不平衡子树的的根（节点3）按下去，将其原先的左孩子（节点2）提上来，从图上看就好像整棵树被向右（顺时针）旋转了一下，所以叫右旋转。注意：旋转了之后确实重新恢复了平衡，而且各个节点之间也保持了二叉搜索树的“小–中–大”的特性。

AVL树代码设计

树节点

综上可知，对 AVL 树的操作的其中一个核心要素是各个子树的高度，因此，在设计AVL 树节点的时候，通常加入表征以该节点为根的子树的高度是一个比较常见的做法，例如：

typedef struct node
{
    datatype data; // 节点数据

    int height;    // 以该节点为根的子树的高度

    struct node *lchild; // 左子树根指针
    struct node *rchild; // 右子树根指针
}treenode, *linktree;

旋转操作

以上述逻辑为基调，将旋转操作分成4组函数，其核心参考代码如何：

// 左旋转：
// 将root的左子树压下去，右子树抬起来作为新的根
linktree avlRotateLeft(linktree root)
{
    linktree tmp = root->rchild;
    root->rchild = tmp->lchild;
    tmp->lchild = root;
    
    root->height = MAX(height(root->lchild), height(root->rchild)) + 1;
    tmp->height = MAX(root->height, height(tmp->rchild)) + 1;

    return tmp;
}

// 右旋转：
// 将root的右子树压下去，左子树抬起来作为新的根
linktree avlRotateRight(linktree root)
{
    linktree tmp = root->lchild;
    root->lchild = tmp->rchild;
    tmp->rchild = root;
    
    root->height = MAX(height(root->lchild), height(root->rchild)) + 1;
    tmp->height = MAX(height(tmp->lchild), root->height) + 1;

    return tmp;
}

// 左右旋转：
// 先对左子树执行左旋转，再对根执行右旋转
linktree avlRotateLeftright(linktree root)
{
    root->lchild = avlRotateLeft(root->lchild);
    return avlRotateRight(root);
}

// 右左旋转：
// 先对右子树执行右旋转，再对根执行左旋转
linktree avlRotateRightleft(linktree root)
{
    root->rchild = avlRotateRight(root->rchild);
    return avlRotateLeft(root);
}

插入节点操作

有了节点和旋转函数，就可以在一棵空树的基础上，不断地按照 AVL 的逻辑插入新的节点，注意到：AVL 树本质上也是一棵 BST，因此对它的插入操作必然要先满足 BST 的逻辑，也就是说前面半部分是BST 的插入代码，只不过插入完节点之后，还需考虑平衡性方可退出插入函数。以下是 AVL 树的插入操作的参考代码：

// AVL 树的插入操作
linktree avlInsert(linktree root, linktree new)
{
    // 若为空树，则直接将 new 作为新的根
    if(root == NULL)
        return new;

    // 按 BST 的逻辑，插入新的节点
    if(new->data < root->data)
        root->lchild = avlInsert(root->lchild, new);
    else if(new->data > root->data)
        root->rchild = avlInsert(root->rchild, new);
    else
    {
        printf("%d is already exist.\n", new->data);
    }

    // 插入完节点之后，判断是否发生4中不平衡中的一种
    // 如果是，则执行对应的旋转操作
    if(height(root->lchild) - height(root->rchild) == 2)
    {
        // 发生了“左左不平衡”: 执行右旋转操作
        if(new->data < root->lchild->data)
            root = avlRotateRight(root);

        // 发生了“左右不平衡”: 执行左右旋转操作
        else if(new->data > root->lchild->data)
            root = avlRotateLeftRight(root);
    }

    else if(height(root->rchild) - height(root->lchild) == 2)
    {
        // 发生了“右右不平衡”: 执行左旋转操作
        if(new->data > root->rchild->data)
            root = avlRotateLeft(root);

        // 发生了“右左不平衡”: 执行右左旋转操作
        else if(new->data < root->rchild->data)
            root = avlRotateRightLeft(root);
    }

    // 更新根节点高度
    root->height = MAX(height(root->lchild), height(root->rchild)) + 1;

    return root;
}

删除节点操作

同理，在 AVL 树的节点删除中，首先考虑到 AVL 是一棵 BST，因此完全可以按照 BST 的逻辑先进性一波处理，处理完了再考虑平衡性的问题，参考代码如下：

// AVL 树的删除操作
linktree avlRemove(linktree root, datatype data)
{
    if(root == NULL)
        return NULL;

    // 按 BST 逻辑删除指定节点
    if(data < root->data)
        root->lchild = avlRemove(root->lchild, data);
    else if(data > root->data)
        root->rchild = avlRemove(root->rchild, data);
    else
    {
        linktree p;

        if(root->lchild != NULL)
        {
            for(p=root->lchild; p->rchild!=NULL; p=p->rchild){;}
            root->data = p->data;
            root->lchild = avlRemove(root->lchild, p->data);
        }
        else if(root->rchild != NULL)
        {
            for(p=root->rchild; p->lchild!=NULL; p=p->lchild){;}
            root->data = p->data;
            root->rchild = avlRemove(root->rchild, p->data);
        }
        else
        {
            free(root);
            return NULL;
        }
    }

    // 删除完节点之后，判断是否发生4中不平衡中的一种
    // 如果是，则执行对应的旋转操作
    if(height(root->lchild) - height(root->rchild) == 2)
    {
        // 发生了“左左不平衡”: 执行右旋转操作
        if(height(root->lchild->lchild)-height(root->lchild->rchild) == 1)
            root = avlRotateRight(root);

        // 发生了“左右不平衡”: 执行左右旋转操作
        else
            root = avlRotateLeftRight(root);
    }
    else if(height(root->rchild) - height(root->lchild) == 2)
    {
        // 发生了“右右不平衡”: 执行左旋转操作
        if(height(root->rchild->rchild)-height(root->rchild->lchild) == 1)
            root = avlRotateLeft(root);

        // 发生了“右左不平衡”: 执行右左旋转操作
        else
            root = avlRotateRightLeft(root);
    }

    root->height = MAX(height(root->lchild), height(root->rchild)) + 1;
    return root;
}