目录一、红黑树简介1、红黑树的简介2、红黑树的性质二、红黑树的插入（看叔叔的颜色就行）1、为什么新插入的节点必须给红色？2、插入红色节点后，判定红黑树性质是否被破坏2.1情况一：uncle存在且为红2.2情况二：uncle不存在/存在且为黑（直线）2.3情况三：uncle不存在/存在且为黑（折线）2.4总结3、红黑树插入代码三、红黑树的平衡检测四、红黑树整体代码一、红黑树简介1、红黑树的简介红黑树和AVL树一样，因其逻辑复杂，面试时现场要求手撕就是纯纯刁难面试者。但某大厂面试官曾要求某些求职者现场手撕红黑树（我赌5毛，让面试官撕，他也撕不出来，而且你家员工上班手搓红黑树啊？），随后求职遭遇被发

红黑树红黑树的概念红黑树的性质红黑树节点的定义红黑树结构红黑树的插入操作红黑树的验证红黑树与AVL树的比较红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。红黑树的性质每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)思考：为什么满足上面的性质，红黑树就能保证

红黑树红黑树的概念红黑树的性质红黑树节点的定义红黑树结构红黑树的插入操作红黑树的验证红黑树与AVL树的比较红黑树的概念红黑树，是一种二叉搜索树，但在每个结点上增加一个存储位表示结点的颜色，可以是Red或Black。通过任何一条从根到叶子的路径上各个结点着色方式的限制，红黑树确保没有一条路径会比其他路径长出俩倍，因而是接近平衡的。红黑树的性质每个结点不是红色就是黑色根节点是黑色的如果一个节点是红色的，则它的两个孩子结点是黑色的对于每个结点，从该结点到其所有后代叶结点的简单路径上，均包含相同数目的黑色结点每个叶子结点都是黑色的(此处的叶子结点指的是空结点)思考：为什么满足上面的性质，红黑树就能保证

目录一、set/map的底层结构1、set/map的源码2、利用模板区分set/map3、利用仿函数控制比较大小二、set/map的迭代器（红黑树的迭代器）1、红黑树的begin、end迭代器2、红黑树迭代器的operator++3、红黑树迭代器的operator--三、set的const迭代器四、map的const迭代器五、迭代器类的拷贝构造六、整体代码1、RBTree.h2、Set.h3、map.h本文相关往期内容，可按需查阅：1、【C++】set/multiset、map/multimap的使用2、【数据结构】二叉搜索树的实现3、【数据结构】平衡二叉树4、【数据结构】手撕红黑树本文难点：

目录一、set/map的底层结构1、set/map的源码2、利用模板区分set/map3、利用仿函数控制比较大小二、set/map的迭代器（红黑树的迭代器）1、红黑树的begin、end迭代器2、红黑树迭代器的operator++3、红黑树迭代器的operator--三、set的const迭代器四、map的const迭代器五、迭代器类的拷贝构造六、整体代码1、RBTree.h2、Set.h3、map.h本文相关往期内容，可按需查阅：1、【C++】set/multiset、map/multimap的使用2、【数据结构】二叉搜索树的实现3、【数据结构】平衡二叉树4、【数据结构】手撕红黑树本文难点：

zset底层的数据结构为什么使用调表而不是红黑树前言Redis中使用到的数据结构以及各个数据对象的底层数据结构在上一篇文章已经写得非常详细，这里不再赘述。https://www.cnblogs.com/ruigedada/p/16248689.htmlzset的底层数据结构是压缩列表和跳表，当满足以下条件时，Redis将使用压缩列表存储有序集合保存的元素个数要小于128个；有序集合保存的所有元素成员的长度都必须小于64字节。我们都知道，调表的查找时间复杂度为O(logn)，但是红黑树和AVL树的查找效率也是O(logn)呀，为什么zset的底层是调表而不是红黑树或者AVL树呢？一、跳表、红黑树

zset底层的数据结构为什么使用调表而不是红黑树前言Redis中使用到的数据结构以及各个数据对象的底层数据结构在上一篇文章已经写得非常详细，这里不再赘述。https://www.cnblogs.com/ruigedada/p/16248689.htmlzset的底层数据结构是压缩列表和跳表，当满足以下条件时，Redis将使用压缩列表存储有序集合保存的元素个数要小于128个；有序集合保存的所有元素成员的长度都必须小于64字节。我们都知道，调表的查找时间复杂度为O(logn)，但是红黑树和AVL树的查找效率也是O(logn)呀，为什么zset的底层是调表而不是红黑树或者AVL树呢？一、跳表、红黑树

本质还是一颗二叉搜索树，只是在其基础上增加了AddFix和RemoveFix来做平衡性修正，确保不会出现极端不平衡的情况。 【规则】a)根节点为黑b)红色节点的子节点只能是2个黑c)黑色节点的子节点只能是：1个红，2个红，2个黑或没有子节点，不可能出现1个黑（如下图所示）d) 任一结点到各个叶子结点的路径都包含数量相同的黑色结点e)新添加的节点一开始总是为红色，后面根据需要调整颜色 #根据上面的规则，下面的这些情况也不可能出现a)  b) c)  #红黑树看似很复杂，其实只是过程比较繁琐而已。他对什么情况做什么操作都已经规定死了，只要照着这些规定的步骤走就行了。【添加】#当遇到新添加节点后，出

本质还是一颗二叉搜索树，只是在其基础上增加了AddFix和RemoveFix来做平衡性修正，确保不会出现极端不平衡的情况。 【规则】a)根节点为黑b)红色节点的子节点只能是2个黑c)黑色节点的子节点只能是：1个红，2个红，2个黑或没有子节点，不可能出现1个黑（如下图所示）d) 任一结点到各个叶子结点的路径都包含数量相同的黑色结点e)新添加的节点一开始总是为红色，后面根据需要调整颜色 #根据上面的规则，下面的这些情况也不可能出现a)  b) c)  #红黑树看似很复杂，其实只是过程比较繁琐而已。他对什么情况做什么操作都已经规定死了，只要照着这些规定的步骤走就行了。【添加】#当遇到新添加节点后，出

title:红黑树date:2022-03-3110:41:30sidebar:autocategories:-数据结构-二叉树tags:-红黑树一、树1.1树的定义树是由n（n>=0）个有限结点组成一个具有层次关系的集合。把它叫做“树”是因为它看起来像一棵倒挂的树，也就是说它是根朝上，而叶朝下的。树结构是一种非线性存储结构，存储的是具有“一对多”关系的数据元素的集合。1.2树的特点每个结点有零个或多个子结点；没有父结点的结点称为根结点；每一个非根结点有且只有一个父结点；除了根结点外，每个子结点可以分为多个不相交的子树；树是一种特殊的图1.3树与图的区别树是没有环的图（在图里面，环的路线是开始