2

我在这里有一个非常简单的问题：红黑树是否必须按排序顺序排列？我问这个是因为维基百科页面右侧的小方框 (http://en.wikipedia.org/wiki/Red–black_tree) 说搜索时间是 O(log(n)); 但是，这不仅是对树进行排序的情况。但另一方面，属性 s

4

4 回答 4

6

红黑树是排序树（所有RB树都是排序二叉树，但并非所有排序二叉树都是红黑树）。普通二叉树和红黑树的区别在于，RB 树保证搜索时间为log 2 (n)，因为它们是平衡的。从本质上讲，它保证了n 个节点的层数永远不会超过log 2 (n)，从而检查二进制搜索。

没有平衡的普通二叉树不会总是产生log 2 (n)的时间复杂度。例如，如果我有一棵这样的树：

  4
 / \
3   6
     \
      7
       \
       10
         \
         12

对于这种不平衡的树，实际搜索时间几乎是线性的12（最坏情况下的时间复杂度，5 次比较）。对于最多具有log 2 (n)层的平衡树，上面的树可以是：

     7
   /   \
  4    10
 / \     \
3   6    12

因此，找到任何最低层节点最多需要 3 次比较（适合log 2 (n)，因为它实际上是四舍五入的，ceil[log 2 (6)] = 3）

这里的关键是要记住，层数在功能上等于从根开始时必须进行的比较次数。红黑树通过平衡将层数限制在最低限度，而普通的不平衡二叉树则没有。

于 2012-09-24T22:40:52.793 回答
2

红黑树是二叉搜索树。根据二叉搜索树的定义，左孩子（和所有后代）必须小于父节点，右孩子（和所有后代）必须大于父节点。因此有一个排序。

于 2012-09-24T22:37:38.810 回答
1

The whole point of a red-black tree is to keep the tree balanced to some degree. If you relax the sorting constraint, then keeping a tree balanced is trivial since you can put nodes wherever you want.

于 2012-09-24T22:56:59.013 回答
1

红黑树的搜索时间为 O(log n)，因为它以自然顺序设置节点的方式。

当您进行节点比较时，理论上您在选择分支时会丢弃一半的选项。

由于您只能log n times在获得一个元素之前“减半”，因此您的搜索复杂性是O(log n)

于 2012-09-24T22:37:37.127 回答