AVL平衡树

2024-02-22 08:22:04

AVL平衡树

对于一般的二叉搜索树来说，插入元素很容易导致树的高度向一个方向偏斜，在最坏情况下二叉搜索树退化成链表，其时间复杂度为 O ( n ) O(n) O(n)。此时，我们就需要做一个高度自平衡的二叉搜索树——AVL平衡树。

节点信息

和普通的树节点相比，AVL平衡树的节点信息多了一个高度信息，记录了这颗子树的高度，并规定空树的高度为 0 0 0，单一节点的高度为 1 1 1，以此类推。

struct Node
{
    int val;
    Node *left;
    Node *right;
    int height;

    Node(int v) : val(v), left(nullptr), right(nullptr), height(1){};
};

辅助函数

获取一颗子树的高度

如果节点不为空，那么返回节点本身的高度信息，否则返回 0 0 0。

int getHeight(Node *n)
{
    return n == nullptr ? 0 : n->height;
}

更新节点高度信息

如果一颗子树经过了修改，那么就应该更新他的高度信息。一颗子树的高度信息为左子树的高度和右子树的高度取最大值并加一即可。

void updateHeight(Node *n)
{
    n->height = max(getHeight(n->left), getHeight(n->right)) + 1;
}

计算平衡因子

一颗子树的平衡因子等于左子树的高度减去右子树的高度。可以发现，如果一颗子树的平衡因子的绝对值大于了 1 1 1，那么说明这颗子树向左或向右偏斜，需要校正。AVL平衡树规定，一颗子树的平衡因子的绝对值不能大于 1 1 1。

int getBalanceFactor(Node *n)
{
    return getHeight(n->left) - getHeight(n->right);
}

旋转

当我们发现某一棵树的平衡因子的绝对值大于了 1 1 1，我们应该如何调整这颗子树呢？我们通过四种旋转操作调整这个子树。

LL旋转

第一种情况 L L LL LL（向左偏两次），我们对节点 N 2 N_{2} N2​进行右旋转，旋转完成之后 N 2 N_{2} N2​节点称为子树新的根节点，节点的子树对应转移即可。

AVL平衡树

Node *LL(Node *n)
{
    Node *nr = n->left;
    n->left = nr->right;
    nr->right = n;
    updateHeight(n);
    updateHeight(nr);
    return nr;
}

RR旋转

第一种情况 R R RR RR（向右偏两次），我们对节点 N 2 N_{2} N2​进行左旋转，旋转完成之后 N 2 N_{2} N2​节点称为子树新的根节点，节点的子树对应转移即可。正好和 L L LL LL旋转是镜像关系。

AVL平衡树

Node *RR(Node *n)
{
    Node *nr = n->right;
    n->right = nr->left;
    nr->left = n;
    updateHeight(n);
    updateHeight(nr);
    return nr;
}

LR旋转

这种情况和下面的 R L RL RL旋转较复杂，需要两次旋转。

对于这种情况，我们先将 N 2 N_{2} N2​子树进行 R R RR RR旋转，再对 N 1 N_{1} N1​进行 L L LL LL旋转即可。

AVL平衡树

Node *LR(Node *n)
{
    n->left = RR(n->left);

    return LL(n);
}

RL旋转

对于这种情况，我们先将 N 2 N_{2} N2​子树进行 L L LL LL旋转，再对 N 1 N_{1} N1​进行 R R RR RR旋转即可。

AVL平衡树

Node *RL(Node *n)
{
    n->right = LL(n->right);

    return RR(n);
}

添加节点

合理使用旋转和判断平衡因子，我们能写出添加节点的操作。

Node *addNode(Node *r, int key)
{
    // 添加节点
    if (r == nullptr)
    {
        return new Node(key);
    }

    if (key < r->val)
        r->left = addNode(r->left, key);
    else if (key > r->val)
        r->right = addNode(r->right, key);

    updateHeight(r);

    int rb = getBalanceFactor(r);

    if (rb > 1)
    {
        // L
        int lb = getBalanceFactor(r->left);
        if (lb > 0)
        {
            // LL
            r = LL(r);
        }
        else if (lb < 0)
        {
            // LR
            r = LR(r);
        }
    }
    else if (rb < -1)
    {
        // R
        int rb = getBalanceFactor(r->right);
        if (rb < 0)
        {
            // RR
            r = RR(r);
        }
        else if (rb > 0)
        {
            // RL
            r = RL(r);
        }
    }
    return r;
}

判断值是否存在

和普通二叉搜索树相同。

bool containsKey(Node *r, int key)
{
    if (r == nullptr)
        return false;
    else if (r->val == key)
        return true;

    if (key < r->val)
        return containsKey(r->left, key);
    else
        return containsKey(r->right, key);
}

代码

struct Node
{
    int val;
    Node *left;
    Node *right;
    int height;

    Node(int v) : val(v), left(nullptr), right(nullptr), height(1){};
};

class AVL
{
private:
    Node *root;

    int getHeight(Node *n)
    {
        return n == nullptr ? 0 : n->height;
    }

    void updateHeight(Node *n)
    {
        n->height = max(getHeight(n->left), getHeight(n->right)) + 1;
    }

    int getBalanceFactor(Node *n)
    {
        return getHeight(n->left) - getHeight(n->right);
    }

    Node *LL(Node *n)
    {
        Node *nr = n->left;
        n->left = nr->right;
        nr->right = n;
        updateHeight(n);
        updateHeight(nr);
        return nr;
    }

    Node *RR(Node *n)
    {
        Node *nr = n->right;
        n->right = nr->left;
        nr->left = n;
        updateHeight(n);
        updateHeight(nr);
        return nr;
    }

    Node *LR(Node *n)
    {
        n->left = RR(n->left);

        return LL(n);
    }

    Node *RL(Node *n)
    {
        n->right = LL(n->right);

        return RR(n);
    }

    Node *addNode(Node *r, int key)
    {
        // 添加节点
        if (r == nullptr)
        {
            return new Node(key);
        }

        if (key < r->val)
            r->left = addNode(r->left, key);
        else if (key > r->val)
            r->right = addNode(r->right, key);

        updateHeight(r);

        int rb = getBalanceFactor(r);

        if (rb > 1)
        {
            // L
            int lb = getBalanceFactor(r->left);
            if (lb > 0)
            {
                // LL
                r = LL(r);
            }
            else if (lb < 0)
            {
                // LR
                r = LR(r);
            }
        }
        else if (rb < -1)
        {
            // R
            int rb = getBalanceFactor(r->right);
            if (rb < 0)
            {
                // RR
                r = RR(r);
            }
            else if (rb > 0)
            {
                // RL
                r = RL(r);
            }
        }
        return r;
    }

    bool containsKey(Node *r, int key)
    {
        if (r == nullptr)
            return false;
        else if (r->val == key)
            return true;

        if (key < r->val)
            return containsKey(r->left, key);
        else
            return containsKey(r->right, key);
    }

public:
    AVL() : root(nullptr)
    {
    }

    void add(int key)
    {
        root = addNode(root, key);
    }

    bool contains(int key)
    {
        return containsKey(root, key);
    }
};

应用——哈希集合

LeetCode 705


struct Node
{
    int val;
    Node *left;
    Node *right;
    int height;

    Node(int v) : val(v), left(nullptr), right(nullptr), height(1){};
};

class AVL
{
private:
    Node *root;

    int getHeight(Node *n)
    {
        return n == nullptr ? 0 : n->height;
    }

    void updateHeight(Node *n)
    {
        n->height = max(getHeight(n->left), getHeight(n->right)) + 1;
    }

    int getBalanceFactor(Node *n)
    {
        return getHeight(n->left) - getHeight(n->right);
    }

    Node *LL(Node *n)
    {
        Node *nr = n->left;
        n->left = nr->right;
        nr->right = n;
        updateHeight(n);
        updateHeight(nr);
        return nr;
    }

    Node *RR(Node *n)
    {
        Node *nr = n->right;
        n->right = nr->left;
        nr->left = n;
        updateHeight(n);
        updateHeight(nr);
        return nr;
    }

    Node *LR(Node *n)
    {
        n->left = RR(n->left);

        return LL(n);
    }

    Node *RL(Node *n)
    {
        n->right = LL(n->right);

        return RR(n);
    }

    Node *rotate(Node *n)
    {
        int rb = getBalanceFactor(n);

        if (rb > 1)
        {
            // L
            int lb = getBalanceFactor(n->left);
            if (lb > 0)
            {
                // LL
                n = LL(n);
            }
            else if (lb < 0)
            {
                // LR
                n = LR(n);
            }
        }
        else if (rb < -1)
        {
            // R
            int rb = getBalanceFactor(n->right);
            if (rb < 0)
            {
                // RR
                n = RR(n);
            }
            else if (rb > 0)
            {
                // RL
                n = RL(n);
            }
        }

        return n;
    }

    Node *addNode(Node *r, int key)
    {
        // 添加节点
        if (r == nullptr)
        {
            return new Node(key);
        }

        if (key < r->val)
            r->left = addNode(r->left, key);
        else if (key > r->val)
            r->right = addNode(r->right, key);
        else
            return r;

        updateHeight(r);
        r = rotate(r);

        return r;
    }

    bool containsKey(Node *r, int key)
    {
        if (r == nullptr)
            return false;
        else if (r->val == key)
            return true;

        if (key < r->val)
            return containsKey(r->left, key);
        else
            return containsKey(r->right, key);
    }

    Node *minimum(Node *r)
    {
        Node *curr = r->right;
        while (curr->left != nullptr)
        {
            curr = curr->left;
        }

        return curr;
    }

    Node *deleteKey(Node *r, int key)
    {
        if (r == nullptr)
            return nullptr;

        if (key < r->val)
            r->left = deleteKey(r->left, key);
        else if (key > r->val)
            r->right = deleteKey(r->right, key);
        else
        {
            if (r->right == nullptr)
            {
                return r->left;
            }
            else if (r->left == nullptr)
            {
                return r->right;
            }
            else
            {
                Node *minn = minimum(r);
                                minn->right = deleteKey(r->right, minn->val);
                minn->left = r->left;

                r = minn;
            }
        }

        updateHeight(r);

        r = rotate(r);

        return r;
    }

public:
    AVL() : root(nullptr)
    {
    }

    void add(int key)
    {
        root = addNode(root, key);
    }

    bool contains(int key)
    {
        return containsKey(root, key);
    }

    void deletes(int key)
    {
        root = deleteKey(root, key);
    }
};

class MyHashSet
{
public:
    AVL avl;
    /** Initialize your data structure here. */
    MyHashSet()
    {
    }

    void add(int key)
    {
        cout << key << endl;
        avl.add(key);
    }

    void remove(int key)
    {
        cout << key << endl;
        avl.deletes(key);
    }

    /** Returns true if this set contains the specified element */
    bool contains(int key)
    {
        cout << key << endl;
        return avl.contains(key);
    }
};
上一篇：平衡二叉树(AVL树)


下一篇：数据结构 - 红黑树原理及其在Java中的应用