郝斌数据结构,堆数据结构

平衡二叉树、二叉树的二叉树、红黑树是将二叉树集中在一起排列二叉树，相信大家都有接触过，二叉树的搜索树的特征是左子树的节点值比父亲节点小，而右子树的节点值比父亲节点大，如图所示

基于该二叉搜索树的特点，在搜索某个节点时，采用二分查找等思想可以快速找到某个节点。 在正常情况下，n个节点的二叉树的搜索时间复杂度为o (逻辑)。

之所以说正常情况下，是因为两股搜寻树有可能会变得极端。 例如

此时也满足二叉查找树的条件，但此时的二叉树已经基本退化为链表，这样的二叉树的搜索时间的复杂性会突然变成o(n )，所以不能发生这样的情况

平衡二叉树是为了解决二叉树搜索树退化为链表而诞生的，平衡树具有以下特点

1、具有二叉搜索树的所有特性。

2、每个节点左右子树的高度差至多等于1。

例如，图1是平衡树，而图2不是。 (节点右侧的目标是此节点的高度。

因为在图2中，节点9左边的孩子的高度为2，右边的孩子的高度为0。 他们之间的差距超过了1。

因此，通过平衡树，解决了脚踏两只船找树的缺点。 在具有n个节点的平衡树的情况下，最坏搜索时间的复杂度也为o(logn )。

为什么即使有平衡的树也需要红黑树？ 平衡树可以解决二叉树退化为接近链表的形状的缺点，可以将搜索时间控制在o(logn )，但不是最优的。 因为平衡树要求平衡二叉树) /，所以这个要求非常严格，每次插入/删除节点，平衡树的第二规则几乎都被破坏。 此外，还必须在每个节点的左子树和右子树的高度差至多等于1和左旋上进行调整，以再次获得符合要求的平衡树。

显然，对于频繁插入、删除的场景，需要频繁调整平衡树，这将大大降低平衡树的性能。 为了解决这个问题，请参阅右旋

1、具有二叉搜索树的特点。

2、根节点为黑色

3、每个叶节点是黑色的空节点(NIL )，也就是说叶节点不保存数据。

4、任何相邻节点都不能同时为红色。 也就是说，红色节点由黑色节点分隔。

5、每个节点，所有路径中，从节点到可用叶节点包括相同数量的黑色节点。

例如，下面的照片(请注意，照片中的黑色、天空的叶子节点没有画出来) )。

根据这种红黑树的特征，即使在最坏的情况下，也能找到o(logn )的时间复杂度的节点。

但是，与平衡树不同，红黑树进行了插入、删除等操作。 是红黑树。 因此，大多数情况下都使用红黑树。

但是，如果说只有寻找才是高效的话，平衡树比红黑树快。

因此，也可以说是不会像平衡树那样，频繁着破坏红黑树的规则，所以不需要频繁着调整折中方案。

因此，最后的答案是，平衡树是为了解决二叉树退化为链表的情况，而红黑树是为了解决平衡树在插入、删除等操作中需要频繁调整的情况。

红黑树是一种不大严格的平衡树

二叉树均衡时，n个节点的二叉树的高度为log(2n1 )，其搜索效率为o ) log ) 2n )，接近对半搜索。 如果二叉树完全不均衡，则其深度达到n，搜索效率为o(n )，退化为逐次搜索。 一般来说，二叉树的搜索性能为时间复杂度：，制作二叉树的时间复杂度为O(Log 2n)到O(n)

quad-log2n-o(n ) o ) log2n ) o ) log2n )操作并插入o ) log2n ) o ) o ) log2n ) o ) log2n ) log2n )删除* *

B-树：文件系统。 b树：数据库索引。 红黑树：内存中，频繁插入、删除。 例如，TreeMap，TreeSet (以下称为TreeMap )。O(nlog2n)。

红海每一操作的时间复杂度均为O(LOGN )O(LOGN )-logn )。

还有构建一棵节点个数为 n 的红黑树，时间复杂度是多少？

权衡三个因素: 查找速度, 数据量, 内存使用，可扩展性，有序性。

hash查找速度会比RB树快，而且查找速度基本和数据量大小无关，属于常数级别;而RB树的查找速度是log(n)级别。并不一定常数就比log(n) 小，因为hash还有hash函数的耗时。当元素达到一定数量级时，考虑hash。但若你对内存使用特别严格， 希望程序尽可能少消耗内存，那么hash可能会让你陷入尴尬，特别是舒服的饼干的hash对象特别多时，你就更无法控制了，而且 hash的构造速度较慢。