rb_tree深度探索rb_tree vs AVL树AVL是一个高度平衡的二叉树而红黑树不是红黑树每次插入一个元素最多只需要两次旋转而AVL可能需要更多次平衡操作搜索速度AVL树更加快因为其严格遵守高度平衡搜索查找的平均时间复杂度为log2(n)插入速度红黑树更加快因为最多只需要两次旋转再加一些重新着色。AVL树是rb_tree的子集红黑树的结构红黑树是平衡二分搜索树中常常使用的一种平衡二分搜索树的特性排列规则有利search和insert并保持适度平衡。红黑树提供遍历的功能及iterators。按正常规则ite遍历便能获得排序状态。红黑树的结构样例为红黑树的中序遍历begin()在左下end()是在右下红黑树的规则(首先需要是一颗二分查找树{BST})1.每个节点不是红色就是黑色2.根节点为黑色3.如果节点为红其子节点必须是黑如果节点为黑其子节点既可以是红也可以是黑4.任一节点至NULL(树尾端)的任何路径所含黑色节点数必须相同根据规则4新增节点必须为红根据规则3新增节点之父节点必须为黑当新节点根据二叉搜索树的规则到达其插入点 但未能符合上述要求就必须调整颜色并旋转树形我们不应该用红黑树的iterators改变元素值因为元素有其严谨的排序规则。但是编程层面并未阻止此事rb_tree将会为set和map服务而map允许元素的data被改变 只有元素的key才是不能被改变的。rb_tree提供两种insertion操作红黑树本身对重复与否没有限制而取决于insert的方式insert_unique()和insert_equal()。前者表示节点的key一定在整个树中独一无二 否则安插失败后者表示节点的key可以重复。部分源码在这里将key和data合起来的节点合成value//这里的Value是key和data的组合如果value只传一个值说明没有valueset template class Key, class Value, class KeyOfValue, class Compare, class Alloc alloc class rb_tree { protected: typedef __rb_tree_nodeValue rb_tree_node;//红黑树的结构 ··· public: // 注意没有定义iterator喔不定义在后面 typedef rb_tree_node* link_type;//指向红黑树节点的指针 ··· protected: //rb_tree只以三个资料表现它自己 size_type node_count;//rb_tree的大小节点数量 link_type header; Compare key_compare;//key的大小比较准则应会是个function object ··· }红黑树插入节点红黑树插入的节点默认为红色首先根据二叉树寻找插入的位置再根据相对位置来调整红色和黑色以及旋转的问题。关于红黑树的插入问题可以在这个网站 来手动插入试验一下Red/Black Tree Visualization关于红色和黑色节点的问题插入节点初始一定为红色新增节点的父节点必须为黑色再根据rb_tree的四条规则进行调整。关于旋转先看一个实例红黑树旋转的具体规则如下(假设插入的节点为X)将新插入的节点标记为红色如果 X 是根结点(root)则标记为黑色2⃣️如果 X 的 parent 不是黑色同时 X 也不是 root3⃣️:如果 X 的 uncle (叔叔) 是红色将 parent 和 uncle 标记为黑色将 grand parent (祖父) 标记为红色让 X 节点的颜色与 X 祖父的颜色相同然后重复步骤2⃣️3⃣️。。。STL_sourcecode/10.第十讲 at master · caixiongjiang/STL_sourcecodeSetmultiset剖析set和multiset特性set/multiset以红黑树为底层结构因此有自动排序的特性排序的依据是key而set和multiset的value和key 是合二为一的value就是keykey和data合成valueset和multiset提供遍历的操作以及iterator按照正常的规则遍历就能获得排序状态。无法使用iterator来改变元素值底层为将iterator设为const因为key有其严谨的排序规则。set的key必须独一无二因此其insert()用的是rb_tree的insert_unique()multiset元素的key可以重复因此其insert()用的是rb_tree的insert_equal()multiset容器除了multiset之外和set基本没有区别map和multimap特性rb_tree为底层结构因此有元素自动排序功能,排序的依据依然为key提供iterator正常遍历便能获得排序状态的结果无法使用iterators来改变元素的key但可以用来改变元素的data。底层为将key值设为const类型map的key必须独一无二因此其insert()用的是rb_tree的insert_unique()multimap元素的key可以重复因此其insert()用的是rb_tree的insert_equal()map独特的operator[]operator[]的作用为返回对应key的data值如果这个key不存在标准库将会自动创建该key值放入map中源码层使用lower_bound来寻找元素的key值如果找到则返回迭代器进行操作如果没有找到则呼叫insert()lower_bound是二分查找的一种版本试图在已经排序的范围[first, last)中寻找一个元素值如果找得到就返回 一个iterator指向其中的第一个符合条件的元素值如果没有找到则返回last的iterator最适合安插这个值的位置operator[]创建新的key比直接使用insert插入效率低因为前面还多了一步lower_bound的过程heappriority_queue深入探索STL_sourcecode/13.第十三讲 at master · caixiongjiang/STL_sourcecode