目录一、红黑树简介二、为什么需要红黑树？三、红黑树的特性四、红黑树的效率4.1红黑树效率4.2红黑树和AVL树的比较五、红黑树的等价变换六、红黑树的操作 6.1旋转操作6.2插入操作6.2.1插入操作的所有情况6.2.2LL和RR插入情况6.2.3LR和RL插入情况6.2.4上溢的LL插入情况6.2.5上溢的RR插入情况6.2.6上溢的LR插入情况6.2.7上溢的RL插入情况6.2.8插入情况总结6.3删除操作6.3.1删除操作的所有情况6.3.2删除拥有1个红色子节点的黑色节点6.3.3删除黑色叶子节点——删除节点为根节点6.3.4删除黑色叶子节点——删除节点的兄弟节点为黑色6.3.5删除黑
目录一、为什么要有红黑树？二、什么是“平衡二叉查找树”？三、红黑树的定义四、为什么说红黑树是“近似平衡”的？五、红黑树为什么综合性能好？六、实现红黑树1、插入操作的平衡调整2、删除操作的平衡调整 1.针对删除节点初步调整2.针对关注节点进行二次调整3、小结 六、红黑树的应用场景红黑树已经落地的场景 一、为什么要有红黑树？二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是O(logn)。但是，在已经有了性能不错的二叉搜索树，为什么还需要引入红黑树呢？那是因为，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于lo
目录一、为什么要有红黑树？二、什么是“平衡二叉查找树”？三、红黑树的定义四、为什么说红黑树是“近似平衡”的？五、红黑树为什么综合性能好？六、实现红黑树1、插入操作的平衡调整2、删除操作的平衡调整 1.针对删除节点初步调整2.针对关注节点进行二次调整3、小结 六、红黑树的应用场景红黑树已经落地的场景 一、为什么要有红黑树？二叉查找树是最常用的一种二叉树，它支持快速插入、删除、查找操作，各个操作的时间复杂度跟树的高度成正比，理想情况下，时间复杂度是O(logn)。但是，在已经有了性能不错的二叉搜索树，为什么还需要引入红黑树呢？那是因为，二叉查找树在频繁的动态更新过程中，可能会出现树的高度远大于lo
红黑树——一种自平衡的二叉树一、红黑树简介普通二叉树在数据不够均匀的情况下，可能导致左右子树高度会相差比较大，最坏情况下树的结构相当于一个链表，时间复杂度为n。为了使二叉树在最坏情况下也能有log(n)的性能，需要对二叉树进行平衡操作，相应的算法有很多，红黑树就是其中一种算法。红黑树是一种自平衡的二叉搜索树，它每一个节点有一个存储位表示颜色。通过对路径上的颜色约束，红黑树保证没有一条路径比其他路径长2倍，因而是接近平衡的。相对于普通的二叉搜索树，红黑树在最坏的情况下保证插入和删除操作的时间复杂度是log(n)一颗红黑树需要满足下列5条规则：每一个节点是红色和黑色的一种根节点是黑色的null节点
红黑树——一种自平衡的二叉树一、红黑树简介普通二叉树在数据不够均匀的情况下，可能导致左右子树高度会相差比较大，最坏情况下树的结构相当于一个链表，时间复杂度为n。为了使二叉树在最坏情况下也能有log(n)的性能，需要对二叉树进行平衡操作，相应的算法有很多，红黑树就是其中一种算法。红黑树是一种自平衡的二叉搜索树，它每一个节点有一个存储位表示颜色。通过对路径上的颜色约束，红黑树保证没有一条路径比其他路径长2倍，因而是接近平衡的。相对于普通的二叉搜索树，红黑树在最坏的情况下保证插入和删除操作的时间复杂度是log(n)一颗红黑树需要满足下列5条规则：每一个节点是红色和黑色的一种根节点是黑色的null节点
前言 在之前学习的STL中的Vector,List,Deque等都是属于序列式容器，序列容器就是以线性排列来存储某一指定类型的数据，并且该类容器并不会自动对存储的元素按照值的大小进行排序。今日所学习的Set，Map本质是一个平衡搜索二叉树，其中包含元素的值都是唯一的，按一定顺序，Set是直接通过key值进行读取和修改元素与map关联容器不同，它只是单纯键的集合，Map是通过键值对进行查找。他们都是关联式容器，关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高 相信大家有一个疑问，为什么Set没有键值对为什么它还是关联式容
前言 在之前学习的STL中的Vector,List,Deque等都是属于序列式容器，序列容器就是以线性排列来存储某一指定类型的数据，并且该类容器并不会自动对存储的元素按照值的大小进行排序。今日所学习的Set，Map本质是一个平衡搜索二叉树，其中包含元素的值都是唯一的，按一定顺序，Set是直接通过key值进行读取和修改元素与map关联容器不同，它只是单纯键的集合，Map是通过键值对进行查找。他们都是关联式容器，关联式容器也是用来存储数据的，与序列式容器不同的是，其里面存储的是结构的键值对，在数据检索时比序列式容器效率更高 相信大家有一个疑问，为什么Set没有键值对为什么它还是关联式容
时间过的好快，我也修炼到红黑树了人世这一遭，何其短暂而漫长啊……文章目录一、AVL树1.AVL树的介绍2.AVL树插入的思路3.AVL树插入的代码（死亡三部曲）4.AVL树的验证二、红黑树1.红黑树的介绍2.红黑树插入的思路3.红黑树插入的代码（关键是uncle）4.红黑树的验证一、AVL树1.AVL树的介绍1.虽然二叉搜索树的搜索效率很高，当搜索树接近满二叉树时，搜索效率可以达到logN，但是如果数据是有序的，则二叉搜索树会退化为单支树，搜索效率和普通的序列式容器相同了就，所以在搜索树的基础上，两位俄罗斯数学家研究出了平衡搜索树。2.平衡搜索树要求任一结点的左右子树的高度差不超过|1|，这个
时间过的好快，我也修炼到红黑树了人世这一遭，何其短暂而漫长啊……文章目录一、AVL树1.AVL树的介绍2.AVL树插入的思路3.AVL树插入的代码（死亡三部曲）4.AVL树的验证二、红黑树1.红黑树的介绍2.红黑树插入的思路3.红黑树插入的代码（关键是uncle）4.红黑树的验证一、AVL树1.AVL树的介绍1.虽然二叉搜索树的搜索效率很高，当搜索树接近满二叉树时，搜索效率可以达到logN，但是如果数据是有序的，则二叉搜索树会退化为单支树，搜索效率和普通的序列式容器相同了就，所以在搜索树的基础上，两位俄罗斯数学家研究出了平衡搜索树。2.平衡搜索树要求任一结点的左右子树的高度差不超过|1|，这个
目录一、红黑树简介1、红黑树的简介2、红黑树的性质二、红黑树的插入（看叔叔的颜色就行）1、为什么新插入的节点必须给红色？2、插入红色节点后，判定红黑树性质是否被破坏2.1情况一：uncle存在且为红2.2情况二：uncle不存在/存在且为黑（直线）2.3情况三：uncle不存在/存在且为黑（折线）2.4总结3、红黑树插入代码三、红黑树的平衡检测四、红黑树整体代码一、红黑树简介1、红黑树的简介红黑树和AVL树一样，因其逻辑复杂，面试时现场要求手撕就是纯纯刁难面试者。但某大厂面试官曾要求某些求职者现场手撕红黑树（我赌5毛，让面试官撕，他也撕不出来，而且你家员工上班手搓红黑树啊？），随后求职遭遇被发
