【C++】AVL树和红黑树模拟实现

AVL树和红黑树

• 1. 背景
• 2. AVL树的概念
• 3. AVL树节点的定义
• 4. AVL树的插入
• 5. AVL树的旋转
• • 5.1. 左单旋
  • 5.2. 右单旋
  • 5.3. 左右单旋
  • 5.4. 右左单旋
  • 5.5. 旋转总结
  • 6. AVL树的验证
  • 7. AVL树的性能
  • 8. 红黑树的概念
  • 9. 红黑树的节点的定义
  • 10. 红黑树的插入
  • • 10.1. 情况一
    • 10.2.情况二
    • 11. 红黑树的验证
    • 12. 红黑树与AVL树的比较

      1. 背景

      1. set、map、multiset、multimap，这几个关联式容器的共同点是：底层都是用二叉搜索树来实现的，但二叉搜索树自身有缺陷，若插入的元素有序或者接近有序，二叉搜索树就会退化为单支树，查询时相当于在顺序表中进行查询，效率低下，时间复杂度退化为O(n)，因此map、set等关联式容器的底层结构对二叉搜索树进行了平衡处理，即采用平衡树来实现。

      2. 通过保证每个节点的左、右子树高度差不超过1，对树中的节点进行调整，即可降低树的高度，从而减少树的搜索长度，时间复杂度为O(longn)。

      2. AVL树的概念

      1. AVL树具有的性质：a. 每个节点的左右子树都是AVL树， b. 每个节点的左右子树高度差(平衡因子)的绝对值不超过1(0、-1、1)。

      2. 平衡因子：右子树高度-左子树高度，不是必须存在的，只是一种控制方式，帮助我们更便捷的++控制树，检查是否为AVL树。

      • 如果一颗二叉搜索树高度是平衡的，那么它就是AVL树，如果它有n个节点，它的高度就是longn，则搜索的时间复杂度为O(longn)。

      • 无法做到平衡因子的值恒为0，因为二叉树插入节点是一个一个插入进去的，对于2个或者4个节点的树是无法做到左右子树高度差等于0，最优的高度差就是1。

        3. AVL树节点的定义

        template   //AVL树的节点(KV模型)struct AVLTreeNode{  typedef AVLTreeNode Node;  Node* _left;      //该节点的左孩子Node* _right;    //该节点的右孩子Node* _parent;  //该节点的父亲，便于向上更新int _bf;       //该节点的平衡因子pair _kv;  AVLTreeNode(const pair& kv)  //构造函数:_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)  { }};

        4. AVL树的插入

        方法：先按二叉搜索树的方式插入新节点，在更新平衡因子。

        void RotateL(Node* parent)  //右右—左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pphead = parent->_parent;    parent->_right = subRL;   //b变成父节点的右孩子if (subRL)   //当前节点的左孩子可能存在，也可能不存在  h=0,b=0subRL->_parent = parent;   //更新当前节点右孩子的父亲subR->_left = parent;   //父节点变为当前节点的左孩纸parent->_parent = subR;   //更新父节点的父亲    //更新当前节点的父亲，父节点可能为根节点，也可能为根节点if (parent == _root)  //根节点 {_root = subR;subR->_parent = nullptr; //更新当前节点的父亲}else{if (pphead->_left == parent)   //子树pphead->_left = subR;elsepphead->_right = subR;subR->_parent = pphead; //更新当前节点的父亲}subR->_bf = 0;  //更新平衡因子parent->_bf = 0;}void RotateR(Node* parent)  //左左—右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pphead = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pphead->_left == parent)pphead->_left = subL;elsepphead->_right = subL;subL->_parent = pphead;}subL->_bf = 0;  //更新平衡因子parent->_bf = 0;}void RotateRL(Node* parent)  //右左—先右旋再左旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* bf = subRL->_bf;   //因为旋转后会改变bf，需要提前记录RotateR(subR); RotateL(parent);subRL->_bf = 0;   //更新平衡因子if (bf == 0) //情况一：当h = 0,subRL为新增节点{subR->_bf = 0;parent->_bf = 0;}else if (bf == -1) //情况二：当h > 0，b插入，b的高度变为h，引发旋转{subR->_bf = 1;parent->_bf = 0;}else if(bf == 1) //情况三：当h > 0，c插入，c的高度变为h，引发旋转{subR->_bf = 0;parent->_bf = -1;}else  //平衡因子异常{assert(false);}}void RotateLR(Node* parent)  //左右—先左旋再右旋{Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(subL);RotateR(parent);    subLR->_bf = 0; //更新平衡因子if (bf == 0){subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else if(bf == -1){subL->bf = 0;parent->_bf = 1;}else{    assert(false);}}bool insert(const pair& kv)  //插入{Node* parent = nullptr;Node* cur = _root;while (cur)  //先按照二叉搜索树的方式插入{if (cur->_kv.first _right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false; //不能出现相同值，否则不构成搜索树了}}cur = new Node(kv);if (parent == nullptr) //空树{_root = cur;return true;}if (parent->_kv.first _right = cur;}else{parent->_left = cur;}cur->_parent = parent;  //记录当前节点的父亲while (parent)  //更新结束： 情况1，更新到根节点{if (parent->_left == cur) //再更新平衡因子parent->_bf--;elseparent->_bf++;if (parent->_bf == 0) //更新结束： 情况2，p的高度不变，不会影响上层的bfbreak;else if (parent->_bf == 1 || parent->_bf == -1) //更新继续：p的高度改变，会影响上层的bf，但未违反平衡树性质{cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) //违反了平衡树的规则，做处理-》旋转 ->更新结束{   //注意：以下4种旋转，只要完成了某一种，都会更新结束，需要breakif (parent->_bf == 2 && cur->_bf == 1) //插入到较高右子树的右边{RotateL(parent); //右右—左单旋break;  }else if (parent->_bf == -2 && cur->_bf == -1) //插入到较高左子树的左边{RotateR(parent);  //左左—右单旋break;}else if (parent->_bf == 2 && cur->_bf == -1)  //插入到较高右子树的左边{ RotateRL(parent);  //右左—先右旋再左旋break;}else if (parent->_bf == -2 && cur->_bf == 1)  //插入到较高左子树的右边{ RotateLR(parent);  //左右—先左旋再右旋break;}else   //在插入前就不是AVL树    必须保证再插入前是一颗AVL树 {assert(false);break;}}}}

        5. AVL树的旋转

        5.1. 左单旋

        void RotateL(Node* parent)  //右右—左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* pphead = parent->_parent;     parent->_right = subRL;   //b变成父节点的右孩子if (subRL)   //当前节点的左孩子可能存在，也可能不存在  h=0,b=0subRL->_parent = parent;   //更新当前节点右孩子的父亲subR->_left = parent;   //父节点变为当前节点的左孩纸parent->_parent = subR;   //更新父节点的父亲//更新当前节点的父亲，父节点可能为根节点，也可能为根节点if (parent == _root)  //根节点 {_root = subR;subR->_parent = nullptr; //更新当前节点的父亲}else{if (pphead->_left == parent)   //子树pphead->_left = subR;elsepphead->_right = subR;subR->_parent = pphead; //更新当前节点的父亲}    subL->_bf = 0;  //更新平衡因子parent->_bf = 0;}

        5.2. 右单旋

        void RotateR(Node* parent)  //左左—右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pphead = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;    if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pphead->_left == parent)pphead->_left = subL;elsepphead->_right = subL;subL->_parent = pphead;}subL->_bf = 0;  //更新平衡因子parent->_bf = 0;}

        5.3. 左右单旋

        void RotateLR(Node* parent)  //左右—先左旋再右旋{Node* subL = parent->_left;Node* subLR = subL->_right;    int bf = subLR->_bf;RotateL(subL);RotateR(parent);subLR->_bf = 0; //更新平衡因子if (bf == 0){subLR->_bf = 0;parent->_bf = 0;}else if (bf == 1){subL->_bf = -1;parent->_bf = 0;}else if(bf == -1){subL->bf = 0;parent->_bf = 1;}else{assert(false);}}

        5.4. 右左单旋

        void RotateRL(Node* parent)  //右左—先右旋再左旋{Node* subR = parent->_right;Node* subRL = subR->_left;Node* bf = subRL->_bf;   //因为旋转后会改变bf，需要提前记录RotateR(subR); RotateL(parent);subRL->_bf = 0;  //更新平衡因子if (bf == 0) //情况一：当h = 0,subRL为新增节点{subR->_bf = 0;parent->_bf = 0;}else if (bf == -1) //情况二：当h > 0，b插入，b的高度变为h，引发旋转{subR->_bf = 1;parent->_bf = 0;}else if(bf == 1) //情况三：当h > 0，c插入，c的高度变为h，引发旋转{subR->_bf = 0;parent->_bf = -1;}else  //平衡因子异常{assert(false);}}

        5.5. 旋转总结

        6. AVL树的验证

        方法：先验证其为二叉搜索树(中序遍历得到有序序列），再验证其为平衡树(左右子树高度差的绝对值不超过1、平衡因子正常)。

        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(Node* root) //前序遍历  验证其为平衡树{if (root == nullptr)return true;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);if (abs(rightHeight - leftHeight) >= 2){cout cout if (root == nullptr)return;_Inorder(root-_left);cout _kv.first if (root == nullptr) //空树也是AVL树{height = 0;return true;}int leftHeight = 0, rightHeight = 0;if(!_Isbalance(root-_left, leftHeight) || !_Isbalance(root-_right, rightHeight)) return false;  //只要左右子树有一颗不是平衡树，该树就不是平衡树height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}

        int main(){int a[] = { 8, 5, 2, 6, 3, 7, 4, 1 };AVLTree t;for (auto& e : a){t.insert(make_pair(e, e));}t.Inorder();cout   //枚举，一一列举出事物具有的所有可能Red,  //枚举常量，给枚举变量进行赋值Black,};templatetypedef RBTreeNode }};Node* subR = parent-_right;Node* subRL = subR-_left;        Node* pphead = 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 (pphead->_left == parent) pphead->_left = subR;elsepphead->_right = subR;    subR->_parent = pphead;}}void RotateR(Node* parent)  //左左—右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;Node* pphead = parent->_parent;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (pphead->_left == parent)pphead->_left = subL;elsepphead->_right = subL;subL->_parent = pphead;}}void RotateRL(Node* parent)  //右左—先右旋再左旋{Node* subR = parent->_right;Node* subRL = subR->_left;    RotateR(subR);RotateL(parent);}void RotateLR(Node* parent)  //左右—先左旋再右旋{Node* subL = parent->_left;Node* subLR = subL->_right;RotateL(subL);RotateR(parent);}bool insert(const pair& kv)  //插入{Node* parent = nullptr;Node* cur = _root;while (cur)  //先按照二叉搜索树的方式插入{if (cur->_kv.first _right;}else if (cur->_kv.first > kv.first){parent = cur;cur = cur->_left;}else{return false; //不能出现相同值，否则不构成搜索树了}}cur = new Node(kv);if (parent == nullptr) //空树{_root = cur;        _root->_col = Black;  //跟节点为黑return true;}if (parent->_kv.first _right = cur;}else{parent->_left = cur;}cur->_parent = parent;  //记录当前节点的父亲//更新颜色//插入结束：1.插入节点的父亲是黑色，因为插入前该树就为红黑树 2.情况一处理完后，cur为根节点，且为黑色while (parent && parent->_col == Red) { //爷爷一定存在，因为c为红，p为红，所以p一定不是根节点，且一定有父节点Node* grandfather = parent->_parent; if (parent == grandfather->_left)  //旋转需要确定方向{Node* uncle = grandfather->_right;  if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边){  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红parent->_col = uncle->_col = Black; //p、u变为黑，g变为红grandfather->_col = Red;//g可能为根节点(更新结束)，也可能为子树(继续向上更新)cur = grandfather;   parent = cur->_parent; }else  //情况二：叔叔不存在 或者 叔叔存在且为黑{  //叔叔不存在，cur为新增节点 或 cur原来为黑，经子树调整由黑变红if (parent->_left == cur)  //左左——右单旋{RotateR(grandfather);    parent->_col = Black; //p变为黑，g变为红grandfather->_col = Red;}else    //左右——左右单旋 {RotateL(parent); RotateR(grandfather);cur->_col = Black;  //c变黑，g变红grandfather->_col = Red;}break;  //更新结束：3.旋转+颜色处理后就是红黑树了}}else{Node* uncle = grandfather->_left;if (uncle && uncle->_col == Red){parent->_col = uncle->_col = Black;grandfather->_col = Red;cur = grandfather;parent = cur->_parent;}else{if (parent->_right == cur)  //右右——左单旋{RotateL(grandfather);parent->_col = Black;grandfather->_col = Red;}else   //右左——右左单旋{RotateR(parent);RotateL(grandfather);cur->_col = Black;grandfather->_col = Red;}break;  }}}_root->_col = Black;  //g为根，颜色变为黑，更新结束    return true;  //情况一，插入节点的父亲为黑，插入结束}

        10.1. 情况一

        1. 叔叔存在且为红色——将p、u变为黑色，g变为红色，在把g给c。若c为根节点，将c变为黑色，插入结束(break)。若c不为根节点，继续向上更新颜色，直到c为根 或则 c的父亲为黑色。

        2. 无方向——p、u是g的左右都可以，c是p的左右都可以，处理方式都是一样的。

        if (uncle && uncle->_col == Red) //情况一：叔叔存在且为红->无方向(p、u为g的任意边，c为p的任一边){  //cur可能为新增节点，也可能一开始为黑色，cur的子树(下一层为红，下一层为新插入节点)在调整过程中将cur由黑变为红parent->_col = uncle->_col = Black; //p、u变为黑，g变为红grandfather->_col = Red;//g可能为根节点(更新结束)，也可能为子树(继续向上更新)cur = grandfather;   parent = cur->_parent; }

        10.2.情况二

        1. 叔叔不存在 或者 叔叔存在且为黑色——旋转(有方向，4种) + 颜色处理。

        2. a. p为g的左孩子，c为p的左孩子，左左，右单旋。b. p为g的右孩子，c为p的右孩子，右右，左单旋，将p变为黑色，将g变为红色—》将p变为黑色，将g变为红色。c. p为g的左孩子，c为p的右孩子，左右旋。d. p为g的右孩子，c为p的左孩子，右左旋——》将c变为黑色，g变为红色。

        3. 若叔叔不存在，c只可以是新增节点，因为若c不是新增节点，该树最短路径长度为1，最长路径长度为4，在插入前就已经违反了红黑树性质3。若叔叔存在且为红，c只能是原来为黑色，经子树调整由黑色变为红色。

        4. 情况二在插入前最短路径长度：最短路径长度=1：2，插入后，违反了红黑树性质4，所以需要做旋转处理。

        if (parent->_left == cur)  //左左——右单旋{RotateR(grandfather);parent->_col = Black; //p变为黑，g变为红grandfather->_col = Red;}else    //左右——左右单旋 {RotateL(parent); RotateR(grandfather);cur->_col = Black;  //c变黑，g变红grandfather->_col = Red;}break;  //更新结束：3.旋转+颜色处理后就是红黑树了

        11. 红黑树的验证

        方法：先验证其为二叉搜索树(中序遍历得到有序序列），再验证其是否满足红黑树的性质。

        void Inorder() //验证其为二叉搜索树，中序遍历{_Inorder(_root);}bool Balance() //验证其是否满足红黑树的性质{if (_root && _root->_col == Red) //红黑树性质2，跟节点为黑色return false;int refvalue = 0;  //红黑树性质4，每条路径具有相同数量的黑节点Node* cur = _root; while (cur){if (cur->_col == Black)refvalue++;   //找参考值cur = cur->_left;}_Balance(_root, 0, refvalue);}//前序遍历，将每条路径黑色节点的数量于参考值比较，验证性质4bool _Balance(Node* root, int blackcount, int& refvalue){if (root == nullptr){if (blackcount != refvalue)return false;return true;    }if (root->_col == Red && root->_parent->_col == Red)return false;   //验证红黑性质3，没有连续的红节点，孩子找爹if (root->_col == Black) //blackcount没有用引用，因为下层不能影响上次，blackcount表示的是当前节点到根节点路径上黑色节点的数量    blackcount++;    return _Balance(root->_left, blackcount, refvalue) && _Balance(root->_right, blackcount, refvalue); //放在后面，从前往后}void _Inorder(Node* root) //中序遍历{if (root == nullptr)return;_Inorder(root->_left);cout _kv.first _right);}

        #define _CRT_SECURE_NO_WARNINGS 1#include"RBTree.h"void test1(){int a[] = { 5, 4, 8, 6, 2, 9, 1, 3, 7 }; RBTree rb;for (auto& e : a){rb.insert(make_pair(e, e));}rb.Inorder();cout test1();return 0;}