红黑树(一)之 原理和算法详细介绍
作者&投稿：典宽 （若有异议请与网页底部的电邮联系）
掌握红黑树的奥秘，让我们一同探索这个高效数据结构的精髓——红黑树(Red-Black Tree)。它是一种特殊的二叉查找树，每个节点都被着上红色(Red)或黑色(Black)的标签，以确保其独特的平衡性和搜索效率。这些规则包括：所有节点为红或黑，根节点永远是黑色；空叶节点为黑色；红色节点的子节点为黑色；从任何节点到其所有后代叶节点的简单路径上，黑色节点数量相同。它在众多场景中发挥着重要作用，比如Java的TreeSet和C++的STL库，其时间复杂度令人惊艳，为O(log n)。而这个神奇的特性，通过数学归纳法进行严格的证明。
当进行插入或删除操作后，红黑树可能会失去平衡，这时就需要通过旋转和颜色调整来修复，保证树的平衡。插入节点的过程分为几个关键步骤：
- 插入: 保持二叉查找树的有序性，新插入的节点标记为红色，可能需要后续调整。
- 着色: 保证插入节点为红色，以符合红黑树的特性。
- 调整: 针对可能的不平衡，通过旋转和颜色变换，确保每个路径的黑色节点数相同。
- 代码实践: 诸如RB-INSERT插入节点，随后通过RB-INSERT-FIXUP进行修正，维护红黑树结构。
红黑树插入操作的精妙之处在于，根据父节点颜色的不同，分为三种情况：
- 当父节点和叔叔节点皆为红色时，通过颜色调整和祖父节点变黑来恢复平衡。
- 叔叔节点为黑色时，根据节点位置进行左旋或右旋，保持红黑特性。
删除节点的操作同样复杂而微妙，涉及节点后继的替换、颜色调整和旋转。删除后，通过一系列颜色和旋转操作，确保红黑树的特性始终如一。
无论是插入还是删除，红黑树的修正过程都围绕着核心原则：保持每个节点到其所有后代叶节点的简单路径上，黑色节点数量相同。通过深入理解这些规则，你可以领略红黑树的魔力，无论是Java的TreeSet还是其他应用场景，它都能提供卓越的性能和高效的存储管理。
势卓律定： 红黑树是平衡二叉树的一种,它有很好的性质,树中的结点都是有序的,而且因为它本身就是平衡的,所以查找也不会出现非常恶劣的情况,基于二叉树的操作的时间复杂度是O(log(N)).Linux内核在管理vm_area_struct时就是采用了红黑树来维...
古塔区18226523345： 红黑树的用途 - ？
势卓律定： 红黑树用在关联数组、字典的实现上.需要的空间比散列表小. 任何键值对应,需要随机存储和键有序的情况都可以用.一. 基本概念 1.红黑树(Red Black Tree) 是一种自平衡二叉查找树,是在计算机科学中用到的一种数据结构,典型的用...
古塔区18226523345： 请问java中HashMap是怎么实现的,还有treeMap的实现原理是红黑树,请解释一下红黑树 - ？
势卓律定： 参考资料的网页上有比较的代码,你可以仔细看下~~~ java中HashMap,LinkedHashMap,TreeMap,HashTable的区别 java为数据结构中的映射定义了一个接口java.util.Map;它有四个实现类,分别是HashMap Hashtable LinkedHashMap 和TreeMap...
古塔区18226523345： 只有左树节点是红树的红黑树与算法里介绍的红黑树有何区别 - ？
势卓律定： 只有左树节点是红树的红黑树与算法里介绍的红黑树有何区别 因为插入之前所有根至外部节点的路径上黑色节点数目都相同,所以如果插入的节点是黑色肯定错误(黑色节点数目不相同),而相对的插入红节点可能会也可能不会违反“没有连续两个节点是红色”这一条件,所以插入的节点为红色,如果违反条件再调整 红黑树的操作时间跟二叉查找树的时间复杂度是一样的,执行查找、插入、删除等操作的时间复杂度为O(logn).红黑树是特殊的AVL树,遵循红定理和黑定理 红定理:不能有两个相连的红节点 黑定理:根节点必须是黑节点,而且所有节点通向NULL的路径上,所经过的黑节点的个数必须相等
古塔区18226523345： 关于算法导论红黑树旋转的问题.？
势卓律定： 这句的意思是把 y节点 的 左节点 的 父节点 设为 x节点. 建议看着下面那副图13-3理解,第一步是把y设为x的右儿子,第二步是把x的右儿子设为y的左儿子,这样完成了x节点的旋转,然后接下来处理y.首先判断y的左儿子是否存在,如果存在,由于y的左儿子的父节点已经改变了(第二步改变的),所以要改变y的左儿子的父指针,设为x.
古塔区18226523345： 用Huffman算法求带权为1,4,9,25,36,49的最优二叉树 - ？
势卓律定： 先将所有的权值选出最小的两个值,为1,4,然后这两个的和为5,那么再从5,9,25,36,49中选出两个最小的,为5和9,然后再从14,25,36,49中选出两个最小的,为14,25,依次进行下去.那么就可以得到最优二叉树为:()/ \() 49/ \() 36/ \() 25/ \() 9/ \1 4
古塔区18226523345： 数据结构的红黑树性质的一个问题 - ？
势卓律定： 好乱.红黑树只有三个性质.1:根节点和所有外部节点是黑色.2:根至外部节点中没有两个连续的颜色是黑色3:所有根节点至外部节点的路径上都有相同数目的黑色节点.注1:外部节点就是叶节点指向的NULL节点,只不过这里不再指向NULL,而是一个实质性的空节点.注2:红黑树还有另一种规则(路径指针),但是和上面的是一样的意思,所以不列举了.
古塔区18226523345： 怎样判断一个数列是有穷数列还是无穷数列请说明具体方法和原理 - ？
势卓律定：[答案] 你好 有省略号的 未知字母不加约束条件的 与实际无关的 未说明有效数字位数的 ....大多是无穷数列 反之则为有穷数列. 判断一个数列是有穷数列还是无穷数列需要抓定义,多思考,多做题,认清题意,细心. 回答完毕.
古塔区18226523345： map底层由数组和链表 怎么理解 链表分为双向和单向 又怎么理解 - ？
势卓律定： 题主,准确来说map是一种高层映射,其底层实现是通过红黑树这种数据结构实现的,而再往下溯源会发现红黑树的数据结构是由链表构成的.因此题目所说底层由数组和链表构成其实跳过了中间红黑树的部分.在C/C++中的链表是通过指针连接的.有些链表结构中只有指向下一个节点的指针,这个就叫单向链表,这种链表只能从前往后顺序访问而不能反向回溯.但一种特殊的链表,每个节点存储了两个指针,一个指向下一个节点,另一个指向上一个节点,这样就可以在访问过程中随意控制访问的顺序:可以顺序向后访问,也可以逆序向前访问.形象理解:单向链表:A->B->C 双向链表:A<=>B<=>C
