关于c++:AVL树

AVL 树性质

• 它的左右子树都是 AVL 树
• 左右子树高度之差的绝对值不超过 1（右子树高度 – 左子树高度）（也称为均衡因子）
• 每个节点都有一个均衡因子
• 个别 AVL 树都是三叉链（左右节点指针和父亲节点指针）
• AVL 树高度为 O(logN)
• AVL 树的工夫复杂度为 O(logN)。

• 均衡因子的更新准则：

  • 如果新增节点在父节点的右边，则父节点的均衡因子减 1；顺次向上更新
  • 如果新增节点在父节点的左边，则父节点的均衡因子加 1；顺次向上更新
  • 直到以后节点的均衡因子为 0 才不向上持续更新了
  • 如果均衡因子为 - 2 或 2，则须要旋转。而后在判断是否须要持续更新。

AVL 树节点的定义形式

template<class K,class V>
struct AVLTreeNode      // 建设节点
{
    AVLTreeNode<K, V>* _left;
    AVLTreeNode<K, V>* _right;
    AVLTreeNode<K, V>* _parent;
    int _bf;  // 均衡因子
    pair<K, V> _kv; // 键值对，存储数据
    AVLTreeNode(const pair<K, V>& kv)   // 构造函数
        :_left(nullptr)
        ,_right(nullptr)
        ,_parent(nullptr)
        ,_bf(0)
        ,_kv(kv)
    {}};

AVL 树的四种旋转形式

为什么要旋转

• 当插入一个节点时，直接插入可能会导致均衡被毁坏（插入节点的所有先人节点的均衡因子可能会扭转）
• 这时就须要将数据进行旋转
• 例如：当插入 30 节点时，这个树就不是 AVL 树了，所以将其进行旋转，失去左边的 AVL 树。

右单旋

右单旋代码实现

    // 右单旋
    void RotateR(Node* parent)  
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        Node* parent_parent = parent->_parent;
        parent->_left = subLR;
        if (subLR) subLR->_parent = parent;
        subL->_right = parent;
        parent->_parent = subL;
        if (parent == _root)
        {
            _root = subL;
            _root->_parent = nullptr;
        }
        else
        {if (parent_parent->_left == parent) parent_parent->_left = subL;
            else parent_parent->_right = subL;
            subL->_parent = parent_parent;
        }
        subL->_bf = 0;
        parent->_bf = 0;
    }

左单旋

左单旋代码实现

    // 左单旋
    void RotateL(Node* parent)  
    {
        Node* subR = parent->_right;  
        Node* subRL = subR->_left;    
        Node* parent_parent = parent->_parent;  
        parent->_right = subRL;
        if (subRL) subRL->_parent = parent;
        subR->_left = parent;
        parent->_parent = subR;
        if (parent == _root)
        {
            _root = subR;
            subR->_parent = nullptr;
        }
        else
        {if (parent_parent->_left == parent)parent_parent->_left = subR;
            else parent_parent->_right = subR;
            subR->_parent = parent_parent;
        }
        subR->_bf = 0;
        parent->_bf = 0;
    }

左右双旋

左右双旋代码实现

    // 左右双旋
    void LRrotate(Node* parent)
    {
        Node* subL = parent->_left;
        Node* subLR = subL->_right;
        int bf = subLR->_bf;
        RotateL(parent->_left);
        RotateR(parent);
        if (bf == -1)
        {
            subL->_bf = 0;
            parent->_bf = 1;
            subLR->_bf = 0;
        }
        else if (bf == 1)
        {
            subL->_bf = -1;
            parent->_bf = 0;
            subLR->_bf = 0;
        }
        else if (bf == 0)
        {
            subL->_bf = 0;
            parent->_bf = 0;
            subLR->_bf = 0;
        }
        else
        {assert(false);
        }
    }

右左双旋

原理同上。

    // 右左双旋
    void RLrotate(Node* parent)
    {
        Node* subR = parent->_right;
        Node* subRL = subR->_left;
        int bf = subRL->_bf;
        RotateR(parent->_right);
        RotateL(parent);
        if (bf == 1)
        {
            subR->_bf = 0;
            parent->_bf = -1;
            subRL->_bf = 0;
        }
        else if (bf == -1)
        {
            parent->_bf = 0;
            subR->_bf = 1;
            subRL->_bf = 0;
        }
        else if (bf == 0)
        {
            parent->_bf = 0;
            subR->_bf = 0;
            subRL->_bf = 0;
        }
        else
        {assert(false);
        }
        
    }

源码地址

gitee 地址：https://gitee.com/BJFyfwl/Lin…