东平网站建设,storyset自定义插画网站,做网站好多钱,二级域名ip查询本文已收录至《数据结构(C/C语言)》专栏#xff01; 作者#xff1a;ARMCSKGT 目录 前言正文红黑树简介红黑树整体结构红黑树节点的定义红黑树主体类设计红黑树的插入函数情况一#xff1a;变色情况二#xff1a;变色旋转单旋情况双旋情况 完整插入代码 关于红黑树红黑树检… 本文已收录至《数据结构(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 iostreamnamespace RB_Tree
{typedef bool Color; //重定义定义bool为颜色类型const bool RED true; //定义 true 为 RED 常量值 对应红色节点const bool BLACK false; //定义 false 为 BLACK 常量值 对应黑色节点templateclass K, class Vstruct RBTreeNode{//红黑树节点成员};//默认比较仿函数templateclass Tstruct less { bool operator()(const T left, const T right) { return left right; } };templateclass Tstruct greater { bool operator()(const T left, const T right) { return left right; } };//红黑树类主体templateclass K, class V, class Compare lessKclass RBTree{//红黑树类主体成员};
}#endif // !RB_TREE红黑树节点的定义 红黑树依然是三叉链结构需要一个父节点指针同时有一个颜色节点来区分红黑节点。 这里红黑节点采用bool值区分true为红false为黑。 我们采用key-value键值对模型来构造红黑树形成映射关系(搜索树类容器属于关系型容器)。 这里的键值对我们采用C标准库提供的pair对象来实现。 代码 struct RBTreeNode
{typedef std::pair K, V 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){}RBTreeNodeK, V* _parent;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;val_type _data;Color _col; //bool类型 truered falseblack
};关于节点的默认颜色 新节点的插入有可能会违反规则分为下面两种情况 如果是插入黑节点那么所有路径的黑色节点不相等此时需要花费大量时间对黑色节点进行调整如果是插入红色节点则会造成连续红色节点的的出现需要变色和旋转。 对于上面的情况我们必须选择违背其中一个然后想办法恢复怎么选择取决于那个的恢复成本比较小。 如果是选择插入黑节点那么一个节点的插入可能会影响所有路径的黑色节点全局影响如果是插入红色节点最坏的情况仅需要旋转到根即可局部影响显而易见插入红节点的恢复成本更小如果需要调整所有路径的黑色节点是非常复杂的 控制红色节点是必然如果出现连续的红色节点那么就不能保证红黑相间最长路径必然大于最短路径的两倍而每条路径上黑色节点数量相同即使是出现连续的黑色节点在同一层都是连续的那么每条路径的黑色节点也相同性质可以得以维持 所以我们默认插入红色节点然后对其进行局部调整 红黑树主体类设计 红黑树类主体对pairK,V对象重定义为val_type对RBTreeNodeK, V重定义为Node方便使用。 其成员变量只需要一个根节点指针_root一个_size记录节点数量一个_com比较函数即可。 为了防止内存泄漏我们事先实现了节点释放函数使用 后序遍历递归 逐一删除节点。 //红黑树类主体设计
templateclass K, class V, class Compare lessK
class RBTree
{typedef std::pair K, V val_type;typedef RBTreeNodeK, V 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的 红黑树的插入函数 红黑树的插入流程与二叉搜索树相似只不过多了调整环节。 插入流程 判断根节点是否为空如果为空则直接插入根节点找最合适的插入位置插入到哪个父节点下与每个节点相比较通过比较函数决定向左子树走还是向右子树走找到合适的父节点后通过比较函数选择插入到父节点的左边还是右边判断父节点颜色决定是否需要染色或调整 为了方便理解我们先介绍一下节点关系一张图说明 代码 pairval_type, bool 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)) // {parent cur;cur cur-_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。每次成功插入节点时都将_size1用作计数如果设计返回节点数量的接口该变量可以大大优化效率否则需要对整棵树进行遍历。每次插入成功返回前都将根节点_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;}完整插入代码 pairval_type, bool 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)) // {parent cur;cur cur-_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 黑节点数不相等 endl;return false;}return true;}if (root-_col BLACK) blacknum;else if (root-_parent root-_parent-_col RED){cout 出现连续的红色节点 endl;return false;}return _isRBTree(root-_left, blackmark, blacknum) _isRBTree(root-_right, blackmark, blacknum);
}有序插入1-10000的数查看情况 可以发现插入有序序列下最大和最小层数正好相差二倍但是仍然合格 红黑树 vs AVL树 我们将两棵树进行性能对比插入1-100w节点查看耗时 检查代码 void randominsert(const int N)
{srand(time(nullptr));cout 随机数据插入 endl;RB_Tree::RBTreeint, int rbt;AVLTree::AVLTreeint, int avl;clock_t start clock();for (int i 1; i N; i) avl.insert({ rand() % i i,i });clock_t end clock();cout AVLTree end - start ms endl;avl.~AVLTree();start clock();for (int i 1; i N; i) rbt.insert({ rand() % i i,i });end clock();cout RBTree end - start ms endl;}void orderlyinsert(const int N)
{cout 有序数据插入 endl;RB_Tree::RBTreeint, int rbt;AVLTree::AVLTreeint, int avl;clock_t start clock();for (int i 1; i N; i) avl.insert({ i,i });clock_t end clock();cout AVLTree end - start ms endl;avl.~AVLTree();start clock();for (int i 1; i N; i) rbt.insert({ i,i });end clock();cout RBTree end - start ms endl;}int main()
{const int N 1000000;randominsert(N);cout endl;orderlyinsert(N);return 0;
}在测试中我们插入随机节点发现红黑树与AVL相差不大而插入有序节点AVL树反而比红黑树性能要好所以不同情况两树性能有区别。 这里我们只实现了插入还有增删改查等一系列的操作都进行的话红黑树平均性能会超过AVL树 注意实际对比下因为数据量问题可能出现AVL树性能比红黑树好的情况这种属于正常现象单比插入不能真实体现全部性能 最后
本节红黑树的介绍到这里就告一段落了当我们完全了解红黑树后发现其实红黑树比较抽象但是比AVL树好控制而我们的STL容器中map和set使用的底层数据结构就是红黑树后面我们将为大家介绍库中红黑树的使用以及map和set的基本封装
本次 红黑树 就先介绍到这里啦希望能够尽可能帮助到大家。
如果文章中有瑕疵还请各位大佬细心点评和留言我将立即修补错误谢谢
本节涉及代码红黑树博客代码 其他文章阅读推荐 高级数据结构AVL树 高级数据结构二叉搜索树 数据结构初级二叉树 C 继承 C 多态 欢迎读者多多浏览多多支持!
