高阶数据结构＜红黑树＞

04-10 1784阅读

本文已收录至《数据结构(C/C++语言)》专栏！

作者：ARMCSKGT

目录

前言
正文
- 红黑树简介
- 红黑树整体结构
- 红黑树节点的定义
- 红黑树主体类设计
- 红黑树的插入函数
- - 情况一：变色
  - 情况二：变色+旋转
  - - 单旋情况
    - 双旋情况
    - 完整插入代码
    - 关于红黑树
    - - 红黑树检验
      - 红黑树 vs AVL树
      - 最后
        前言
        
        红黑树是二叉搜索树的一种，但是红黑树是性能最均衡应用场景最广的一种二叉搜索树，相对于AVL树来说，红黑树在旋转条件上并不是很严格，但是依然可以有非常出色的查找性能，这得益于红黑树的性质，本节将为大家介绍红黑树的基本性质。
        
        正文
        
        本文相关知识点：二叉搜索树(搜索树性质)，AVL树(旋转相关)
        如果大家对二叉搜索树性质不熟悉或者对树的旋转调整不熟悉，可以先移步这两篇文章就行了解！
        
        红黑树简介
        
        红黑树是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树（symmetric binary B-trees）。后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的“红黑树”。
        
        红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。
        
        前面我们介绍了AVL树，AVL树有着极其严格的平衡标准，这使得AVL树在某些极端情况下可能会频繁旋转导致插入和删除性能下降，而红黑树只有在极度不平衡下才会调整，对于红黑树来说，极度不平衡就是最长路径大于最短路径的两倍！
        
        红黑树的性质：
        
        每个节点不是黑色就是红色
        根节点是黑色
        如果一个节点是红色的，则它的两个孩子结点是黑色的（不存在连续的红色节点，例如父子节点都是红色）
        每条路径上叶子节点都是黑色的（红黑树中空节点NIL可以理解为叶子节点，这个叶节点没有特殊意思，方便判断）
        每条路径上的黑色节点数量相同
        按照红黑树的性质，可以知道：
        上图中，如果是AVL树就需要进行左单旋降低高度，而红黑树则不需要调整。
        可以说，最短路径是全黑节点，最长路径是红黑相间。
        因为最长路径的节点数量不能超过最短路径节点数量的两倍，所以黑节点数量大于等于红节点数量。
        
        我们一般在使用容器时，增删查改是都会出现的，如果使用AVL树，查找性能非常好，但是插入性能就一般了，所以一般语言标准中的容器都会使用红黑树，性能比较均衡，而AVL树则时候那些只读的静态数据，专门用于查询！
        
        关于实际的性能差距，假设二叉树有n个节点，AVL树查询的时间复杂度为O( l o g 2 n log_2n log2n)；红黑树查询的最优效率为O( l o g 2 n log_2n log2n)，最差效率为O( 2 l o g 2 n 2log_2n 2log2n)。 l o g 2 n log_2n log2n和 2 l o g 2 n 2log_2n 2log2n这两个数值的差距，对于计算机来说可以忽略不计，假设有10亿，也仅仅是30和60次查找的差别！
        
        红黑树整体结构
        
        红黑树需要定义节点，比较函数和红黑树类主体，所以分为三部分，封装在红黑树命名空间中！
        对于比较函数，我们使用仿函数控制，使用模板参数传参，默认K类型参数为比较对象，使用者也可以自己按要求实现比较函数，按自己的比较规则控制红黑树。
        同时，我们在头文件中实现，为了防止重复包含，使用 #ifndef~#endif 来就行条件编译。
        
        #ifndef RB_TREE #define RB_TREE #include namespace RB_Tree { typedef bool Color; //重定义定义bool为颜色类型 const bool RED = true; //定义 true 为 RED 常量值对应红色节点 const bool BLACK = false; //定义 false 为 BLACK 常量值对应黑色节点 template struct RBTreeNode { //红黑树节点成员 }; //默认比较仿函数 template struct less { bool operator()(const T& left, const T& right) { return left right; } }; //红黑树类主体 template class RBTree { //红黑树类主体成员 }; } #endif // !RB_TREE
        
        红黑树节点的定义
        
        红黑树依然是三叉链结构，需要一个父节点指针，同时有一个颜色节点来区分红黑节点。
        这里红黑节点采用bool值区分，true为红，false为黑。
        我们采用key-value键值对模型来构造红黑树，形成映射关系(搜索树类容器属于关系型容器)。
        这里的键值对，我们采用C++标准库提供的pair对象来实现。
        
        代码：
        
        struct RBTreeNode { typedef std::pair val_type; RBTreeNode() : _parent(nullptr) , _left(nullptr) , _right(nullptr) , _col(RED) {} RBTreeNode(const val_type& data) : _parent(nullptr) , _left(nullptr) , _right(nullptr) , _data(data) , _col(RED) {} RBTreeNode* _parent; RBTreeNode* _left; RBTreeNode* _right; val_type _data; Color _col; //bool类型 true=red false=black };
        
        关于节点的默认颜色：
        新节点的插入，有可能会违反规则，分为下面两种情况：
        
        如果是插入黑节点，那么所有路径的黑色节点不相等，此时需要花费大量时间对黑色节点进行调整！
        如果是插入红色节点，则会造成连续红色节点的的出现，需要变色和旋转。
        对于上面的情况，我们必须选择违背其中一个，然后想办法恢复，怎么选择取决于那个的恢复成本比较小。
        如果是选择插入黑节点，那么一个节点的插入可能会影响所有路径的黑色节点（全局影响），如果是插入红色节点，最坏的情况仅需要旋转到根即可（局部影响），显而易见，插入红节点的恢复成本更小，如果需要调整所有路径的黑色节点，是非常复杂的！
        控制红色节点是必然，如果出现连续的红色节点，那么就不能保证红黑相间，最长路径必然大于最短路径的两倍，而每条路径上黑色节点数量相同，即使是出现连续的黑色节点，在同一层都是连续的，那么每条路径的黑色节点也相同，性质可以得以维持！
        
        所以我们默认插入红色节点，然后对其进行局部调整！
        
        红黑树主体类设计
        
        红黑树类主体对pair对象重定义为val_type，对RBTreeNode重定义为Node，方便使用。
        其成员变量只需要一个根节点指针_root，一个_size记录节点数量，一个_com比较函数即可。
        为了防止内存泄漏，我们事先实现了节点释放函数，使用后序遍历+递归逐一删除节点。
        
        //红黑树类主体设计 template class RBTree { typedef std::pair val_type; typedef RBTreeNode Node; public: RBTree() :_root(nullptr) , _size(0) {} ~RBTree() { DelTree(_root); _root = nullptr; } private: //删除树 void DelTree(Node* root) { if (root == nullptr) return; DelTree(root->_left); DelTree(root->_right); delete root; } private: Node* _root; //根节点 size_t _size; //节点数量 Compare _com; //比较函数 };
        
        我们自己实现的红黑树，与STL库中的有一定区别，我们主要介绍插入思想，插入思想上与库中基本相似，但是在结构设计上有一定区别，这里要提一下的是，STL中的红黑树有一个头节点，其左子树指针指向树中的最小值节点（最左节点），右子树指针指向最大值节点（最右节点），这样好处在于，设计迭代器时，遍历不需要找最左和最右节点，以及对遍历到结尾的条件判断要简单一点，但是我们这里主要介绍红黑树的插入原理，所以使用简单的结构就行。
        当然，我们本节介绍的并非上图的红黑树，而是不带header的！
        
        红黑树的插入函数
        
        红黑树的插入流程与二叉搜索树相似，只不过多了调整环节。
        
        插入流程：
        
        判断根节点是否为空，如果为空则直接插入根节点
        找最合适的插入位置（插入到哪个父节点下），与每个节点相比较，通过比较函数决定向左子树走还是向右子树走
        找到合适的父节点后，通过比较函数选择插入到父节点的左边还是右边
        判断父节点颜色，决定是否需要染色或调整
        
        为了方便理解，我们先介绍一下节点关系，一张图说明：
        
        代码：
        
        pair insert(const val_type& data) { //为空插入根节点 if (nullptr == _root) { Node* newnode = new Node(data); _root = newnode; } else //否则开始找插入位置 { Node* newnode = new Node(data); Node* parent = _root; Node* cur = _root; while (cur) { if (_com(data.first, cur->_data.first)) // _left; } else if (_com(cur->_data.first, data.first)) // > { parent = cur; cur = cur->_right; } else return { data,false }; // == } //新节点插入合适的父节点下 if (_com(data.first, parent->_data.first)) parent->_left = newnode; else parent->_right = newnode; newnode->_parent = parent; cur = newnode; //开始调整 while (parent && parent->_col == RED) { //祖父节点 Node* grandfather = parent->_parent; //叔叔节点 Node* uncle = nullptr; //调整 ... } } ++_size; _root->_col = BLACK; //无论怎么调整根节点总是黑色 return { data,true }; }
        
        说明：
        
        插入函数的返回值为pair对象key-value类型，表示数据data是否插入成功，插入成功时second为true，失败则为false。
        每次成功插入节点时，都将_size+1，用作计数（如果设计返回节点数量的接口，该变量可以大大优化效率，否则需要对整棵树进行遍历）。
        每次插入成功返回前都将根节点_root的颜色置为BLACK，以确保根节点一直为黑（染色调整可能会修改根节点颜色）。
        
        关于调整：
        调整的关键是看父节点和叔叔节点！
        
        如果父节点为黑节点，则直接插入，不需要进行任何调整
        如果父节点为红色，则需要去看叔叔节点，如果叔叔节点也为红色，则直接变色然后继续向上调整即可
        如果父节点为红色，叔叔节点为黑色或不存在，则需要进行旋转+变色调整。
        因为左区间和右区间的判断条件对称，所以我们左右一起介绍。
        下面介绍时因为祖父单词过长，简写为gf！
        
        情况一：变色
        
        父节点和叔叔节点都为红色此时需要变色
        如果新节点插入后，父节点（parent）和叔叔节点（uncle）的颜色都为黑色，则可以将父节点和叔叔节点变为黑色，祖父节点（grandfather）变为红色来解决！
        不过在变色后，如果祖父节点是其他树的子树，则需要继续向上调整，将祖父节点作为新插入节点继续检查，因为祖父节点变成红色后可能其曾祖父也是红色，此时还需要继续判断和调整，如果曾祖父是黑色或不存在，则停止调整即可！
        代码：
        
        if (grandfather->_left == parent) { //父节点是祖父的左叔叔就是祖父的右 uncle = grandfather->_right; if (uncle && uncle->_col == RED) { grandfather->_col = RED; parent->_col = uncle->_col = BLACK; uncle->_col = BLACK; //继续检查和调整 cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_col == BLACK) { //旋转+染色 } } else if (grandfather->_right == parent) { //父节点是祖父的右叔叔就是祖父的左 uncle = grandfather->_left; if (uncle && uncle->_col == RED) { grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //继续检查和调整 cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_col == BLACK) { //旋转+染色 } }
        
        这里主要是通过祖父指针分辨父节点和叔叔节点的位置，以做不同操作！
        
        情况二：变色+旋转
        
        叔叔不存在或叔叔为黑色此时需要旋转和变色
        有些情况下染色并不能保持性质，此时需要旋转降低高度！
        情况二可以由情况一产生，变色后祖父和曾祖父为连续的红色节点！
        
        在AVL树中，旋转分为单旋和双旋，如果插入在左子树的左和右子树的右，不平衡的情况直接分别进行右单旋和左单旋即可；如果插入在左子树的右和右子树的左，不平衡的情况直接分别进行左右双旋和右左双旋即可！
        
        涉及旋转都需要注意新增节点的插入位置，才能进行对应的旋转！
        
        旋转后就需要调整节点的颜色，以符合红黑树的性质！
        当旋转和染色结束后，直接跳出调整即可，不需要继续向上检测！
        
        单旋情况
        
        如果插入位置在左子树的左和右子树的右且叔叔节点不存在或存在且为黑节点，此时需要进行单旋和变色调整！
        
        图示：
        左单旋+染色
        
        
        右单旋+染色
        
        
        代码：
        
        if (grandfather->_left == parent) { uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //单纯染色 } else if (uncle == nullptr || uncle->_col == BLACK) { if (parent->_left == cur) { //右单旋 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else if (parent->_right == cur) { //左右双旋 } //旋转完后整树平衡直接跳出 break; } } else if (grandfather->_right == parent) { uncle = grandfather->_left; if (uncle && uncle->_col == RED) { //单纯染色 } else if (uncle == nullptr || uncle->_col == BLACK) { if (parent->_right == cur) { //左单旋 RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else if (parent->_left == cur) { //右左双旋 } //旋转完成后整树趋于平衡 break; } }
        
        双旋情况
        
        如果插入位置在左子树的右和右子树的左且叔叔节点不存在或存在且为黑节点，此时需要进行双旋和变色调整！
        
        图示：
        右左双旋+变色
        
        
        右左双旋+变色
        
        
        代码：
        
        if (grandfather->_left == parent) { uncle = grandfather->_right; if (uncle && uncle->_col == RED) { //染色+调整 } else if (uncle == nullptr || uncle->_col == BLACK) { if (parent->_left == cur) { //右单旋+染色 } else if (parent->_right == cur) { //左右双旋+染色 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } //旋转完后整树平衡直接跳出 break; } } else if (grandfather->_right == parent) { uncle = grandfather->_left; if (uncle && uncle->_col == RED) { //染色+调整 } else if (uncle == nullptr || uncle->_col == BLACK) { if (parent->_right == cur) { //左单旋+变色 } else if (parent->_left == cur) { //右左双旋+染色 RotateR(parent); RotateL(grandfather); grandfather->_col = RED; cur->_col = BLACK; } //旋转完成后整树趋于平衡 break; }
        
        完整插入代码
        
        pair insert(const val_type& data) { if (nullptr == _root) { Node* newnode = new Node(data); _root = newnode; } else { Node* newnode = new Node(data); Node* parent = _root; Node* cur = _root; while (cur) { if (_com(data.first, cur->_data.first)) // _left; } else if (_com(cur->_data.first, data.first)) // > { parent = cur; cur = cur->_right; } else return { data,false }; // == } if (_com(data.first, parent->_data.first)) parent->_left = newnode; else parent->_right = newnode; newnode->_parent = parent; cur = newnode; while (parent && parent->_col == RED) { //祖父节点 Node* grandfather = parent->_parent; //叔叔节点 Node* uncle = nullptr; //调整 if (grandfather->_left == parent) { uncle = grandfather->_right; if (uncle && uncle->_col == RED) { grandfather->_col = RED; parent->_col = uncle->_col = BLACK; uncle->_col = BLACK; //继续染色 cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_col == BLACK) { if (parent->_left == cur) { //右单旋 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else if (parent->_right == cur) { //左右双旋 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } //旋转完后整树平衡直接跳出 break; } } else if (grandfather->_right == parent) { uncle = grandfather->_left; if (uncle && uncle->_col == RED) { grandfather->_col = RED; parent->_col = BLACK; uncle->_col = BLACK; //继续染色 cur = grandfather; parent = grandfather->_parent; } else if (uncle == nullptr || uncle->_col == BLACK) { if (parent->_right == cur) { //左单旋 RotateL(grandfather); grandfather->_col = RED; parent->_col = BLACK; } else if (parent->_left == cur) { //右左双旋 RotateR(parent); RotateL(grandfather); grandfather->_col = RED; cur->_col = BLACK; } //旋转完成后整树趋于平衡 break; } } } } ++_size; _root->_col = BLACK; //无论怎么调整根节点总是黑色 return { data,true }; }
        
        关于红黑树
        
        红黑树检验
        
        我们实现红黑树后，还需要对其规则进行检验，防止bug导致红黑树结构异常！
        
        检验规则：
        
        根节点是否为黑色姐
        是否出现连续的红色节点
        – 说明：如果我们先判断当前节点再判断子节点，就需要对子节点进行分类判断，很麻烦。此时我们需要转换思想，先判断子树是否为红再判断父节点，因为根节点为黑所以不会访问根节点的父级指针，也就是不会访问空指针，而后的子树必有父节点，所以我们只需要判断当前节点是否为红，如果为红再去判断父节点，红节点一定有父节点。
        每条路径的黑色节点数量是否相等
        –说明：既然是每条路径都相等，我们随意找一条路径取基准值（例如取最左路径或最右路径的黑节点数量），然后去与每条路径进行对比，全相等就符合要求。
        
        //检验函数调用接口 bool isRBTree() { //三个条件 //没有连续红色节点 //每条路上的黑色节点数相等 if (_root == nullptr) return true; if (_root && _root->_col == RED) return false; int blackmark = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK) ++blackmark; cur = cur->_right; } return _isRBTree(_root, blackmark, 0); } //检验函数执行接口 bool _isRBTree(Node* root, const int blackmark, int blacknum) { if (root == nullptr) { if (blackmark != blacknum) { cout _parent && root->_parent->_col == RED) { cout _right, blackmark, blacknum); }
        
        有序插入1-10000的数，查看情况：
        可以发现，插入有序序列下，最大和最小层数正好相差二倍，但是仍然合格！
        
        红黑树 vs AVL树
        
        我们将两棵树进行性能对比，插入1-100w节点，查看耗时！
        检查代码：
        
        void randominsert(const int N) { srand(time(nullptr)); cout rand() % i + i,i }); clock_t end = clock(); cout rand() % i + i,i }); end = clock(); cout cout i,i }); clock_t end = clock(); cout i,i }); end = clock(); cout const int N = 1000000; randominsert(N); cout

VPS购买请点击我

文章版权声明：除非注明，否则均为主机测评原创文章，转载或复制请以超链接形式并注明出处。

相关阅读

目录[+]