MENU

AVL树

一:背景

AVL树是一棵平衡的二叉查找树,于1962年,G. M. Adelson-Velsky和E. M. Landis在他们的论文《An algorithm for the organization of information》中发表。

所谓的平衡之意,就是树中任意一个结点下左右两个子树的高度差不超过1。(本文对于树的高度约定为:空结点高度是0,叶子结点高度是1。)

那AVL树和普通的二叉查找树有何区别呢?如图,如果我们插入的是一组有序上升或下降的数据,则一棵普通的二叉查找树必然会退化成一个单链表,其查找效率就降为$O(n)$。而AVL树因其平衡的限制,可以始终保持$O(logn)$的时间复杂度。

二:具体实现与代码分析

在我们进行完插入或删除操作后,很可能会导致某个结点失去平衡,那么我们就需要把失衡结点旋转一下,使其重新恢复平衡。

经过分析,不管是插入还是删除,它们都会有四种失衡的情况:左左失衡,右右失衡,左右失衡,右左失衡。因此每次遇到失衡时,我们只需判断一下是哪个失衡,再对其进行相对应的恢复平衡操作即可。

好,下面以插入操作为例,来看下这四种失衡的庐山真面目。(以下统一约定:红色结点为新插入结点,y结点为失衡结点

1. 左左失衡

所谓的左左,即"失衡结点"的左子树比右子树高2,左孩子下的左子树比右子树高1。

我们只需对"以y为根的子树"进行"左左旋转(ll_rotate)"即可。一次旋转后,恢复平衡。

Node * AVL::ll_rotate(Node * y)
{
    Node * x = y->left;
    y->left = x->right;
    x->right = y;

    y->height = max(get_height(y->left), get_height(y->right)) + 1;
    x->height = max(get_height(x->left), get_height(x->right)) + 1;

    return x;
}

2. 右右失衡

所谓的右右,即"失衡结点"的右子树比左子树高2,右孩子下的右子树比左子树高1。

我们只需对"以y为根的子树"进行"右右旋转(rr_rotate)"即可。一次旋转后,恢复平衡。

Node * AVL::rr_rotate(Node * y)
{
    Node * x = y->right;
    y->right = x->left;
    x->left = y;

    y->height = max(get_height(y->left), get_height(y->right)) + 1;
    x->height = max(get_height(x->left), get_height(x->right)) + 1;

    return x;
}

3. 左右失衡

所谓的左右,即"失衡结点"的左子树比右子树高2,左孩子下的右子树比左子树高1。

观察发现,若先对"以x为根的子树"进行"右右旋转(rr_rotate)",此时"以y为根的子树"恰好符合"左左失衡",所以再进行一次"左左旋转(ll_rotate)"。两次旋转后,恢复平衡。

Node * AVL::lr_rotate(Node * y)
{
    Node * x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}

4. 右左失衡

所谓的右左,即"失衡结点"的右子树比左子树高2,右孩子下的左子树比右子树高1。

观察发现,若先对"以x为根的子树"进行"左左旋转(ll_rotate)",此时"以y为根的子树"恰好符合"右右失衡",所以再进行一次"右右旋转(rr_rotate)"。两次旋转后,恢复平衡。

Node * AVL::rl_rotate(Node * y)
{
    Node * x = y->right;
    y->right = ll_rotate(x);
    return rr_rotate(y);
}

2.1 插入操作

插入成功后,在递归回溯时依次对经过的结点判断是否失衡,若失衡就需要对其进行对应的旋转操作使其恢复平衡,在这期间,原先作为一棵子树的根结点就会因为旋转被替换,因此设置insert_real()返回的是新根结点,这样就可以实时更新根结点。

插入操作实现代码如下:

int AVL::get_height(Node * node)
{
    if (node == nullptr)
        return 0;
    return node->height;
}

int AVL::get_balance(Node * node)
{
    if (node == nullptr)
        return 0;
    return get_height(node->left) - get_height(node->right);
}

Node * AVL::insert_real(int key, Node * node)
{
    if (node == nullptr)
        return new Node(key);

    if (key < node->key)
        node->left = insert_real(key, node->left);
    else if (key > node->key)
        node->right = insert_real(key, node->right);
    else
        return node;

    node->height = max(get_height(node->left), get_height(node->right)) + 1;

    int balance = get_balance(node);

    // 左左失衡
    if (balance > 1 && get_balance(node->left) > 0)
        return ll_rotate(node);

    // 右右失衡
    if (balance < -1 && get_balance(node->right) < 0)
        return rr_rotate(node);

    // 左右失衡
    if (balance > 1 && get_balance(node->left) < 0)
        return lr_rotate(node);

    // 右左失衡
    if (balance < -1 && get_balance(node->right) > 0)
        return rl_rotate(node);

    return node;
}

void AVL::insert(int key)
{
    header->left = insert_real(key, header->left);
}

2.2 查找操作

Node * AVL::find_real(int key, Node * node)
{
    if (node == nullptr)
        return nullptr;

    if (key < node->key)
        return find_real(key, node->left);
    else if (key > node->key)
        return find_real(key, node->right);
    else
        return node;
}

Node * AVL::find(int key)
{
    return find_real(key, header->left);
}

2.3 删除操作

删除操作的四种失衡情况和插入操作一样,读者可以参考前文。下面是删除操作的实现代码:

Node * AVL::erase_real(int key, Node * node)
{
    if (node == nullptr)
        return node;

    if (key < node->key)
        node->left = erase_real(key, node->left);
    else if (key > node->key)
        node->right = erase_real(key, node->right);
    else
    {
        if (node->left && node->right)
        {
            // 找到后继结点
            Node * x = node->right;
            while (x->left)
                x = x->left;

            // 后继直接复制
            node->key = x->key;

            // 转化为删除后继
            node->right = erase_real(x->key, node->right);
        }
        else
        {
            Node * t = node;
            node = node->left ? node->left : node->right;
            delete t;
            if (node == nullptr)
                return nullptr;
        }
    }

    node->height = max(get_height(node->left), get_height(node->right)) + 1;

    int balance = get_balance(node);

    // 左左失衡
    if (balance > 1 && get_balance(node->left) >= 0) // 需要加等号
        return ll_rotate(node);

    // 右右失衡
    if (balance < -1 && get_balance(node->right) <= 0) // 需要加等号
        return rr_rotate(node);

    // 左右失衡
    if (balance > 1 && get_balance(node->left) < 0)
        return lr_rotate(node);

    // 右左失衡
    if (balance < -1 && get_balance(node->right) > 0)
        return rl_rotate(node);

    return node;
}

void AVL::erase(int key)
{
    header->left = erase_real(key, header->left);
}

三:完整代码

/**
 *
 * author : 刘毅(Limer)
 * date   : 2017-08-17
 * mode   : C++
 */

#include <iostream>
#include <algorithm>

using namespace std;

struct Node
{
    int key;
    int height;
    Node * left;
    Node * right;
    Node(int key = 0)
    {
        this->key = key;
        this->height = 1;
        this->left = this->right = nullptr;
    }
};

class AVL
{
private:
    Node * header;
private:
    Node * ll_rotate(Node * y);
    Node * rr_rotate(Node * y);
    Node * lr_rotate(Node * y);
    Node * rl_rotate(Node * y);
    void destroy(Node * node);
    int get_height(Node * node);
    int get_balance(Node * node);
    Node * insert_real(int key, Node * node);
    Node * find_real(int key, Node * node);
    Node * erase_real(int key, Node * node);
    void in_order(Node * node);
public:
    AVL();
    ~AVL();
    void insert(int key);
    Node * find(int key);
    void erase(int key);
    void print();
};

Node * AVL::ll_rotate(Node * y)
{
    Node * x = y->left;
    y->left = x->right;
    x->right = y;

    y->height = max(get_height(y->left), get_height(y->right)) + 1;
    x->height = max(get_height(x->left), get_height(x->right)) + 1;

    return x;
}

Node * AVL::rr_rotate(Node * y)
{
    Node * x = y->right;
    y->right = x->left;
    x->left = y;

    y->height = max(get_height(y->left), get_height(y->right)) + 1;
    x->height = max(get_height(x->left), get_height(x->right)) + 1;

    return x;
}

Node * AVL::lr_rotate(Node * y)
{
    Node * x = y->left;
    y->left = rr_rotate(x);
    return ll_rotate(y);
}

Node * AVL::rl_rotate(Node * y)
{
    Node * x = y->right;
    y->right = ll_rotate(x);
    return rr_rotate(y);
}

void AVL::destroy(Node * node)
{
    if (node == nullptr)
        return;
    destroy(node->left);
    destroy(node->right);
    delete node;
}

int AVL::get_height(Node * node)
{
    if (node == nullptr)
        return 0;
    return node->height;
}

int AVL::get_balance(Node * node)
{
    if (node == nullptr)
        return 0;
    return get_height(node->left) - get_height(node->right);
}

Node * AVL::insert_real(int key, Node * node)
{
    if (node == nullptr)
        return new Node(key);

    if (key < node->key)
        node->left = insert_real(key, node->left);
    else if (key > node->key)
        node->right = insert_real(key, node->right);
    else
        return node;

    node->height = max(get_height(node->left), get_height(node->right)) + 1;

    int balance = get_balance(node);

    // 左左失衡
    if (balance > 1 && get_balance(node->left) > 0)
        return ll_rotate(node);

    // 右右失衡
    if (balance < -1 && get_balance(node->right) < 0)
        return rr_rotate(node);

    // 左右失衡
    if (balance > 1 && get_balance(node->left) < 0)
        return lr_rotate(node);

    // 右左失衡
    if (balance < -1 && get_balance(node->right) > 0)
        return rl_rotate(node);

    return node;
}

Node * AVL::find_real(int key, Node * node)
{
    if (node == nullptr)
        return nullptr;

    if (key < node->key)
        return find_real(key, node->left);
    else if (key > node->key)
        return find_real(key, node->right);
    else
        return node;
}

Node * AVL::erase_real(int key, Node * node)
{
    if (node == nullptr)
        return node;

    if (key < node->key)
        node->left = erase_real(key, node->left);
    else if (key > node->key)
        node->right = erase_real(key, node->right);
    else
    {
        if (node->left && node->right)
        {
            // 找到后继结点
            Node * x = node->right;
            while (x->left)
                x = x->left;

            // 后继直接复制
            node->key = x->key;

            // 转化为删除后继
            node->right = erase_real(x->key, node->right);
        }
        else
        {
            Node * t = node;
            node = node->left ? node->left : node->right;
            delete t;
            if (node == nullptr)
                return nullptr;
        }
    }

    node->height = max(get_height(node->left), get_height(node->right)) + 1;

    int balance = get_balance(node);

    // 左左失衡
    if (balance > 1 && get_balance(node->left) >= 0) // 需要加等号
        return ll_rotate(node);

    // 右右失衡
    if (balance < -1 && get_balance(node->right) <= 0) // 需要加等号
        return rr_rotate(node);

    // 左右失衡
    if (balance > 1 && get_balance(node->left) < 0)
        return lr_rotate(node);

    // 右左失衡
    if (balance < -1 && get_balance(node->right) > 0)
        return rl_rotate(node);

    return node;
}

void AVL::in_order(Node * node)
{
    if (node == nullptr)
        return;

    in_order(node->left);
    cout << node->key << " ";
    in_order(node->right);
}

AVL::AVL()
{
    header = new Node(0);
}

AVL::~AVL()
{
    destroy(header->left);
    delete header;
    header = nullptr;
}

void AVL::insert(int key)
{
    header->left = insert_real(key, header->left);
}

Node * AVL::find(int key)
{
    return find_real(key, header->left);
}

void AVL::erase(int key)
{
    header->left = erase_real(key, header->left);
}

void AVL::print()
{
    in_order(header->left);
    cout << endl;
}

int main()
{
    AVL avl;

    // test "insert"
    avl.insert(7);
    avl.insert(2);
    avl.insert(1); avl.insert(1);
    avl.insert(5);
    avl.insert(3);
    avl.insert(6);
    avl.insert(4);
    avl.insert(9);
    avl.insert(8);
    avl.insert(11); avl.insert(11);
    avl.insert(10);
    avl.insert(12);
    avl.print(); // 1 2 3 4 5 6 7 8 9 10 11 12

    // test "find"
    Node * p = nullptr;
    cout << ((p = avl.find(2)) ? p->key : -1) << endl;   //  2
    cout << ((p = avl.find(100)) ? p->key : -1) << endl; // -1

    // test "erase"
    avl.erase(1);
    avl.print(); // 2 3 4 5 6 7 8 9 10 11 12
    avl.erase(9);
    avl.print(); // 2 3 4 5 6 7 8 10 11 12
    avl.erase(11);
    avl.print(); // 2 3 4 5 6 7 8 10 12

    return 0;
}

起初构造的AVL树为下图:

四:总结

和二叉查找树相比,AVL树的特点是时间复杂度更稳定,但缺点也是很明显的。

插入操作中,至多需要一次恢复平衡操作,递归回溯的量级为$O(logn)​$。有一点需要我们注意,在对第一个失衡结点进行恢复平衡后,递归回溯就应该立即停止(因为失衡结点的父亲及其祖先们肯定都是处于平衡状态的),但让"递归的回溯"中途停止,不好实现,所以我上面的编码程序都不可避免的会继续回溯,直到整棵树的根结点,而这些回溯都是没有必要的。(谢谢LLL的提醒,若在结点中增设父亲结点,就可以解决递归回溯的问题)

删除操作中,若存在失衡,则至少需要一次恢复平衡操作,递归回溯的量级亦为$O(logn)$。与插入操作不同,当对第一个失衡结点恢复平衡后,它的父亲或者是它的祖先们也可能是非平衡的(见下图,删除1),所以删除操作的回溯很有必要。

没有参照物对比的探讨是没有意义的,所以此文就止于此吧,有兴趣的朋友可以看下我后面《红黑树》及《AVL树与红黑树的对比》的文章。

五:参考文献

返回文章列表 文章二维码 打赏
本页链接的二维码
打赏二维码
添加新评论

8 条评论
  1. LLL LLL

    关于 AVL 插入 都不可避免的会继续回溯,直到整棵树的根结点,看看下面这个的实现

    https://github.com/hungry0/DataStructureOfDeng/blob/b8f195b0b86c5718054343c65b9deda118b7019d/src/avl/avl_insert.h

    1. @LLL是的哦,谢谢提醒。

  2. Kernel Kernel

    为什么删掉 1、3、4后 根节点还是5 ????

    1. @Kernel

      // 左左失衡
      if (balance > 1 && get_balance(node->left) >= 0)
          return ll_rotate(node);
      
      // 右右失衡
      if (balance < -1 && get_balance(node->right) <= 0)
          return rr_rotate(node);

      需要加个等号

  3. 松鼠先生 松鼠先生

    正在学习相关知识,感谢分享。

  4. Sooke Sooke

    已经收藏博客@(呵呵) ,希望楼主更新 字典树 的 第二篇 以及 AC自动机 的相关教程哦

  5. 感谢分享!!