红黑树的颜色有什么用,红黑树的用途
Jk8为什么要用红黑树呢？
红黑树的用途
红黑树用在关联数组、字典的实现上。
需要的空间比散列表小。
任何键值对应,需要随机存储和键有序的情况都可以用。
一. 基本概念
1.红黑树(Red Black Tree)一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
2.它是在1972年由Rudolf Bayer发明的，当时被称为平衡二叉B树(symmetric binary B-trees)。
后来，在1978年被 Leo J. Guibas 和 Robert Sedgewick 修改为如今的"红黑树"。
3.红黑树和AVL树类似，都是在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
4.它虽然是复杂的，但它的最坏情况运行时间也是非常良好的，并且在实践中是高效的: 它可以在O(log n)时间内做查找，插入和删除，这里的n树中元素的数目。
二. 数据结构
它的统计性能要好于平衡二叉树(有些书籍根红黑树据作者姓名，Adelson-Velskii和Landis，将其称为AVL-树)，因此，红黑树在很多地方都有应用。
在C++ STL中，很多部分(包括set, multiset, map, multimap)应用了红黑树的变体(SGI STL中的红黑树有一些变化，这些修改提供了更好的性能，以及对set操作的支持)。
其他平衡树还有:AVL，SBT，伸展树，TREAP 等等。
三. 性质
性质1. 节点是红色或黑色。
性质2. 根节点是黑色。
性质3.每个叶节点(NIL节点，空节点)是黑色的。
性质4.每个红色节点的两个子节点都是黑色。
(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
linux红黑树详解linux红黑树
红黑树的各种操作的时间复杂度是多少？
红黑树的操作时间跟二叉查找树的时间复杂度是一样的，执行查找、插入、删除等操作的时间复杂度为O（logn）。
红黑树是特殊的AVL树，遵循红定理和黑定理红定理：不能有两个相连的红节点黑定理：根节点必须是黑节点，而且所有节点通向NULL的路径上，所经过的黑节点的个数必须相等
红黑树的算法原理及讲解？
红黑树原理和算法详细介绍
红黑树定义：
(1)每个节点或者是黑色，或者是红色。
(2)根节点是黑色。
(3)每个叶子节点是黑色。
(4)如果一个节点是红色的，则它的子节点必须是黑色的。
(5)从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。
证明
首先定义一个节点x的黑高为bh(x)bh(x)bh(x),表示从x到任意一个叶子节点路径上黑色节点的个数（不包括x）。
1.第一步，先证明以某一节点x为根的子树中至少包含2bh(x)?12^{bh(x)}?12
bh(x)?1个内节点(不是叶子的都是内节点)。
用数学归纳法证明。
如果x的高度为0，那么x是叶节点，包含0个内节点，满足该式子。
对于高度为正值的x，其两个孩子至少包含2bh(x)?1?12^{bh(x)?1}?12bh(x)?1?1个内节点，
所以以x为根的子树至少包含(2bh(x)?1?1)+(2bh(x)?1?1)+1=2bh(x)?1(2^{bh(x)?1}?1)+(2^{bh(x)?1}?1)+1=2^{bh(x)}?1(2bh(x)?1?1)+(2
bh(x)?1?1)+1=2bh(x)?1个内节点。
2.第二步，对于一棵高度为h的树，任意一条从根到叶节点（不包括根）的路径上至少有一半黑色节点，从而bh(x)≥h/2bh(x)≥h/2bh(x)≥h/2，所以n≥2bh(x)?1≥2h/2?1n≥2^{bh(x)}?1≥2^{h/2}?1n≥2bh(x)?1≥2h/2?1，即h≤2log(n+1)h≤2log(n+1)h≤2log(n+1)
红黑树和链表的区别？
红黑树是一种自平衡二叉查找树，是在计算机科学中用到的一种数据结构，典型的用途是实现关联数组。
能在进行插入和删除操作时通过特定操作保持二叉查找树的平衡，从而获得较高的查找性能。
关于红黑树描述正确的？
红黑树是每个节点都带有颜色属性的二叉查找树，颜色或红色或黑色。
在二叉查找树强制一般要求以外，对于任何有效的红黑树我们增加了如下的额外要求:
性质1.节点是红色或黑色。
性质2.根是黑色。
性质3每个叶节点是黑色的。
性质4每个红色节点的两个子节点都是黑色。
(从每个叶子到根的所有路径上不能有两个连续的红色节点)
性质5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
二叉树是用来干什么的?在软件工程方面有什么用途，请帮小弟举几个实例？
用的最多的应该是平衡二叉树，有种特殊的平衡二叉树红黑树，查找、插入、删除的时间复杂度最坏为O(logn)Java集合中的TreeSet和TreeMap，C++STL中的set、map，以及Linux虚拟内存的管理，都是通过红黑树去实现的。
还有哈夫曼树编码方面的应用。
B-Tree，B+-Tree在文件系统中的应用。
如有错误或遗漏还请各位指正补充。
