关于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...