AVL 树

ahao

发布于 2024-03-19 19:21:17

570

发布于 2024-03-19 19:21:17

文章被收录于专栏：学习学习

AVL树的概念

二叉搜索树虽可以缩短查找的效率，但如果数据有序或接近有序二叉搜索树将退化为单支树，查找元素相当于在顺序表中搜索元素，效率低下。因此，两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法：当向二叉搜索树中插入新结点后，如果保证每个结点的左右子树高度之差的绝对值不超过1(需要对树中的结点进行调整)，即可降低树的高度，从而减少平均搜索长度。

一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：

它的左右子树都是AVL树 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)

节点的平衡因子=右子树的高度-左子树的高度

例如：下图的二叉搜索树的每个节点的平衡因子的绝对值都小于2，并且每个节点的子树也都是AVL树

AVL树的定义

AVL树是一种特殊的二叉搜索树，它具有高度的平衡，所以为了在插入过程中的各个节点的平衡因子的更新，我们在定义AVL树的节点结构的同时要带上一个节点的双亲结点parent

template<class T>
struct AVLTreeNode
{
    AVLTreeNode(const T& data)
        : _left(nullptr), _right(nullptr), _parent(nullptr)
        , _data(data), _bf(0)
    {}
    AVLTreeNode<T>* _left;   // 该节点的左孩子
    AVLTreeNode<T>* _right;  // 该节点的右孩子
    AVLTreeNode<T>* _parent; // 该节点的双亲
    T _data;
    int _bf;                  // 该节点的平衡因子
};

AVL树的插入

AVL树的插入是一个难点，它分为好几种情况，其实AVL树的插入也就是在二叉搜索树中插入新节点，但是由于他引入了平衡因子，需要更新，所以这里的插入节点就比较麻烦，她一共分为两步：

1 插入节点 2 更新节点的平衡因子

为什么要更新节点的平衡因子呢？

简单地举个例子：如图所示，我将一个新节点插入0的左孩子节点的位置，那么以3为节点的这颗子树的高度差不就会超过1了吗，他的左子树的高度插入新节点后为3，而右子树为1，这就不符合AVL树的性质了，所以我们需要经过一些操作来更新平衡因子

这里大家需要注意一个规则： 新节点如果是插入后他的parent的左侧，那么他的平衡因子默认是+1 反之插入他的右侧就是默认-1

那么在插入节点后，各个插入节点的parent一共就有三种情况了：

平衡因子为0 如果parent的平衡因子为0，说明插入之前parent的平衡因子为正负1，插入后被调整成0，此时满足AVL树的性质，插入成功

平衡因子为正负1 如果parent的平衡因子为正负1，说明插入前pParent的平衡因子一定为0，插入后被更新成正负1，此时以parent为根的树的高度增加，需要继续向上更新，防止部分节点的左右子树高度差超过1 平衡因子为正负2 如果parent的平衡因子为正负2，则pParent的平衡因子违反平衡树的性质，需要对其进行旋转处理，旋转处理之后插入成功

至于旋转的情况我们待会分析，我们先将插入节点的代码的主要框架构造出来：这样一个简单的框架就构造出来了

template<class T>
struct AVLTreeNode
{
    
    AVLTreeNode<T>* _left;   // 该节点的左孩子
    AVLTreeNode<T>* _right;  // 该节点的右孩子
    AVLTreeNode<T>* _parent; // 该节点的双亲
    T _data;
    int _bf;                  // 该节点的平衡因子
    AVLTreeNode(const T& data)
        : _left(nullptr), _right(nullptr), _parent(nullptr)
        , _data(data), _bf(0)
    {}
};
template<class T>
class AVLTree
{

    typedef AVLTreeNode<T> Node;
public:
    
    bool insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_data < data)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
            cur = new Node(data);
            if (parent->_data > data)
            {
                parent->_left = cur;
            }
            else
            {
                parent->_right = cur;
            }
            while (parent)
            {
                //左边++
                if (cur == parent->_left)
                {
                    parent->_bf--;
                }
                //右边--
                else
                {
                    parent->_bf++;
                }
                //parent的平衡因子等于0，插入成功
                if (parent->_bf == 0)
                {
                    break;
                }
                //parent的平衡因子等于1或者-1，继续向上更新
                else if (parent->_bf == 1 || parent->_bf == -1)
                {
                    cur = parent;
                    parent = parent->_parent;
                }
                else if (parent->_bf == 2 || parent->_bf == -2)
                {
                    //需要进行旋转
                }
                else
                {
                    assert(false);
                }
            }
        }
    }


private:
    Node* _root;
};

下面我们就具体分析几种旋转的情况

AVL树的旋转

如果在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，AVL树的旋转分为四种：

1. 新节点插入较高左子树的左侧—左左：右单旋 下图中的h可以时0 1 2三种，分别代表了这三个子树的高度，无论他是等于0 1 还是2时他们都可以满足AVL树的要求

可以看到，这种情况就是parent的平衡因子等于-2，cur的平衡因子等于-1 左旋函数如下：

void RotateR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    parent->_left = subLR;
    //防止sublr为空
    if(subLR)
        subLR->_parent = parent;
    //记录祖父位置
    Node* pparent = parent->_parent;
    
    subL->_right = parent;
    parent->_parent = subL;
    //如果父亲是根节点
    if (parent == _root)
    {
        _root = subL;
        subL->_parent = nullptr;
    }
    //parent不是根节点，那么祖父就会成为subl的parent
    else
    {
        if (pparent->_left == parent)
        {
            pparent->_left = subL;
            subL->_parent = pparent;
        }
        else
        {
            pparent->_right = subL;
            subL->_parent = pparent;
        }
    }
    //旋转后parent和subl的 平衡因子都会更新为0
    parent->_bf = subL->_bf = 0;
}

2. 新节点插入较高右子树的右侧—右右：左单旋 实现及情况考虑可参考右单旋。

void RotateL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;

    parent->_right = subRL;
    subR->_left = parent;

    Node* pparent = parent->_parent;
    
    if (subRL)
        subRL->_parent = parent;

    if (_root == parent)
    {
        _root = subR;
        subR->_parent == nullptr;
    }
    else
    {
        if (pparent->_left == parent)
        {
            pparent->_left = subR;
            subR->_parent = pparent;
        }
        else
        {
            pparent->_right = subR;
            subR->_parent = pparent;
        }
    }
    parent->_bf = subR->_bf = 0;
}

3. 新节点插入较高左子树的右侧—左右：先左单旋再右单旋

将双旋变成单旋后再旋转，即：先对30进行左单旋，然后再对90进行右单旋，旋转完成后再考虑平衡因子的更新。直接复用即可：由于博主能力有限，所以放入代码大家仔细理解

void RotateLR(Node* parent)
{
    Node* subL = parent->_left;
    Node* subLR = subL->_right;

    RotateL(parent->_left);
    RotateR(parent);
    
    int bf = subLR->_bf;
    //sublr就是新增节点
    if (bf == 0)
    {
        parent->_bf = 0;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    //sublr左子树新增节点
    else if (bf == -1)
    {
        parent->_bf = 1;
        subL->_bf = 0;
        subLR->_bf = 0;
    }
    //sublr右子树新增节点
    else if (bf == 1)
    {
        parent->_bf = 0;
        subL->_bf = -1;
        subLR->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

4. 新节点插入较高右子树的左侧—右左：先右单旋再左单旋

void RotateRL(Node* parent)
{
    Node* subR = parent->_right;
    Node* subRL = subR->_left;
    int bf = subRL->_bf;
    RotateR(parent->_right);
    RotateL(parent);
    //subrl这个点为新增点
    if (bf == 0)
    {
        parent->_bf = subR->_bf = subRL->_bf = 0;
    }
    //subrl的左子树新增
    else if (bf == -1)
    {
        parent->_bf = 0;
        subRL->_bf = 0;
        subR->_bf = 1;
    }
    //subrl的右子树新增
    else if (bf == 1)
    {
        parent->_bf = -1;
        subRL->_bf = 0;
        subR->_bf = 0;
    }
    else
    {
        assert(false);
    }
}

根据各种情况我们做了总结：

假如以parent为根的子树不平衡，即parent的平衡因子为2或者-2，分以下情况考虑

parent的平衡因子为2，说明parent的右子树高，设parent的右子树的根为subR，当subR的平衡因子为1时，执行左单旋当subR的平衡因子为-1时，执行右左双旋
parent的平衡因子为-2，说明parent的左子树高，设parent的左子树的根为subL，当subL的平衡因子为-1是，执行右单旋，当subL的平衡因子为1时，执行左右双旋旋转完成后，原parent为根的子树个高度降低，已经平衡，不需要再向上更新。

所以我们可以补全上面的插入节点的代码了：

bool insert(const T& data)
{
    if (_root == nullptr)
    {
        _root = new Node(data);
        return true;
    }
    Node* parent = nullptr;
    Node* cur = _root;
    while (cur)
    {
        if (cur->_data < data)
        {
            parent = cur;
            cur = cur->_right;
        }
        else if (cur->_data > data)
        {
            parent = cur;
            cur = cur->_left;
        }
        else
        {
            return false;
        }
        
    }
    cur = new Node(data);
    if (parent->_data > data)
    {
        parent->_left = cur;
    }
    else
    {
        parent->_right = cur;
    }
    while (parent)
    {
        //左边++
        if (cur == parent->_left)
        {
            parent->_bf--;
        }
        //右边--
        else
        {
            parent->_bf++;
        }
        //parent的平衡因子等于0，插入成功
        if (parent->_bf == 0)
        {
            break;
        }
        //parent的平衡因子等于1或者-1，继续向上更新
        else if (parent->_bf == 1 || parent->_bf == -1)
        {
            cur = parent;
            parent = parent->_parent;
        }
        else if (parent->_bf == 2 || parent->_bf == -2)
        {
            //需要进行旋转
            if (parent->_bf == 2 && cur->_bf == 1)
            {
                RotateL(parent);
            }
            else if (parent->_bf == 2 && cur->_bf == -1)
            {
                RotateRL(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == -1)
            {
                RotateR(parent);
            }
            else if (parent->_bf == -2 && cur->_bf == 1)
            {
                RotateLR(parent);
            }
            break;
        }
        else
        {
            assert(false);
        }
    }
    return true;
}

AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分两步：

1. 验证其为二叉搜索树 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树 2. 验证其为平衡树每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)节点的平衡因子是否计算正确

我们可以用一个函数来判断即可：首先要有一个计算树的高度的函数然后判断他们的子树的高度差的绝对值是否在2以内，并且他们的子树也要是AVL树

int Height(Node* root)
{
    if (root == nullptr)
    {
        return 0;
    }
    int leftheight = Height(root->_left);
    int rightheight = Height(root->_right);
    return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
}

bool isbalance()
{
    return _isbalance(_root);
}

bool _isbalance(Node* root)
{
    if (root == nullptr)
        return true;
    int leftheight = Height(root->_left);
    int rightheight = Height(root->_right);
    if (rightheight - leftheight != root->_bf)
    {
        cout << root->_data << "平衡因子异常" << endl;
        return false;
    }
    return abs(rightheight - leftheight) < 2
        && _isbalance(root->_left)
        && _isbalance(root->_right);
}

我们还可以用中序遍历打印：

void inorder()
{
    _inorder(_root);
    cout << endl;
}

void _inorder(Node* root)
{
    if (root == nullptr)
    {
        return;
    }
    _inorder(root->_left);
    cout << root->_data << " ";
    _inorder(root->_right);
}

完整代码如下：

#include<iostream>
#include<assert.h>
using namespace std;
template<class T>
struct AVLTreeNode
{
    
    AVLTreeNode<T>* _left;   // 该节点的左孩子
    AVLTreeNode<T>* _right;  // 该节点的右孩子
    AVLTreeNode<T>* _parent; // 该节点的双亲
    T _data;
    int _bf;                  // 该节点的平衡因子
    AVLTreeNode(const T& data)
        : _left(nullptr), _right(nullptr), _parent(nullptr)
        , _data(data), _bf(0)
    {}
};
template<class T>
class AVLTree
{

    typedef AVLTreeNode<T> Node;
public:
    
    bool insert(const T& data)
    {
        if (_root == nullptr)
        {
            _root = new Node(data);
            return true;
        }
        Node* parent = nullptr;
        Node* cur = _root;
        while (cur)
        {
            if (cur->_data < data)
            {
                parent = cur;
                cur = cur->_right;
            }
            else if (cur->_data > data)
            {
                parent = cur;
                cur = cur->_left;
            }
            else
            {
                return false;
            }
            
        }
        cur = new Node(data);
        if (parent->_data > data)
        {
            parent->_left = cur;
        }
        else
        {
            parent->_right = cur;
        }
        while (parent)
        {
            //左边++
            if (cur == parent->_left)
            {
                parent->_bf--;
            }
            //右边--
            else
            {
                parent->_bf++;
            }
            //parent的平衡因子等于0，插入成功
            if (parent->_bf == 0)
            {
                break;
            }
            //parent的平衡因子等于1或者-1，继续向上更新
            else if (parent->_bf == 1 || parent->_bf == -1)
            {
                cur = parent;
                parent = parent->_parent;
            }
            else if (parent->_bf == 2 || parent->_bf == -2)
            {
                //需要进行旋转
                if (parent->_bf == 2 && cur->_bf == 1)
                {
                    RotateL(parent);
                }
                else if (parent->_bf == 2 && cur->_bf == -1)
                {
                    RotateRL(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == -1)
                {
                    RotateR(parent);
                }
                else if (parent->_bf == -2 && cur->_bf == 1)
                {
                    RotateLR(parent);
                }
                break;
            }
            else
            {
                assert(false);
            }
        }
        return true;
    }

    void RotateR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        parent->_left = subLR;
        //防止sublr为空
        if(subLR)
            subLR->_parent = parent;
        //记录祖父位置
        Node* pparent = parent->_parent;
        
        subL->_right = parent;
        parent->_parent = subL;
        //如果父亲是根节点
        if (parent == _root)
        {
            _root = subL;
            subL->_parent = nullptr;
        }
        //parent不是根节点，那么祖父就会成为subl的parent
        else
        {
            if (pparent->_left == parent)
            {
                pparent->_left = subL;
                subL->_parent = pparent;
            }
            else
            {
                pparent->_right = subL;
                subL->_parent = pparent;
            }
        }
        //旋转后parent和subl的 平衡因子都会更新为0
        parent->_bf = subL->_bf = 0;
    }

    void RotateL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;

        parent->_right = subRL;
        subR->_left = parent;

        Node* pparent = parent->_parent;
        
        if (subRL)
            subRL->_parent = parent;

        if (_root == parent)
        {
            _root = subR;
            subR->_parent == nullptr;
        }
        else
        {
            if (pparent->_left == parent)
            {
                pparent->_left = subR;
                subR->_parent = pparent;
            }
            else
            {
                pparent->_right = subR;
                subR->_parent = pparent;
            }
        }
        parent->_bf = subR->_bf = 0;
    }

    void RotateLR(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;

        RotateL(parent->_left);
        RotateR(parent);
        
        int bf = subLR->_bf;
        //sublr就是新增节点
        if (bf == 0)
        {
            parent->_bf = 0;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        //sublr左子树新增节点
        else if (bf == -1)
        {
            parent->_bf = 1;
            subL->_bf = 0;
            subLR->_bf = 0;
        }
        //sublr右子树新增节点
        else if (bf == 1)
        {
            parent->_bf = 0;
            subL->_bf = -1;
            subLR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    void RotateRL(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        //subrl这个点为新增点
        if (bf == 0)
        {
            parent->_bf = subR->_bf = subRL->_bf = 0;
        }
        //subrl的左子树新增
        else if (bf == -1)
        {
            parent->_bf = 0;
            subRL->_bf = 0;
            subR->_bf = 1;
        }
        //subrl的右子树新增
        else if (bf == 1)
        {
            parent->_bf = -1;
            subRL->_bf = 0;
            subR->_bf = 0;
        }
        else
        {
            assert(false);
        }
    }

    int Height(Node* root)
    {
        if (root == nullptr)
        {
            return 0;
        }
        int leftheight = Height(root->_left);
        int rightheight = Height(root->_right);
        return leftheight > rightheight ? leftheight + 1 : rightheight + 1;
    }

    bool isbalance()
    {
        return _isbalance(_root);
    }

    bool _isbalance(Node* root)
    {
        if (root == nullptr)
            return true;
        int leftheight = Height(root->_left);
        int rightheight = Height(root->_right);
        if (rightheight - leftheight != root->_bf)
        {
            cout << root->_data << "平衡因子异常" << endl;
            return false;
        }
        return abs(rightheight - leftheight) < 2
            && _isbalance(root->_left)
            && _isbalance(root->_right);
    }

    void inorder()
    {
        _inorder(_root);
        cout << endl;
    }

    void _inorder(Node* root)
    {
        if (root == nullptr)
        {
            return;
        }
        _inorder(root->_left);
        cout << root->_data << " ";
        _inorder(root->_right);
    }

private:
    Node* _root=nullptr;
};

好了，今天的分享到这里就结束了，感谢大家的支持！

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2024-03-19，如有侵权请联系 cloudcommunity@tencent.com 删除

parent