我知道红黑树只是一个平衡的二进制搜索树。所以我计算了元素数量为2^n的数据集的平均搜索成本(基本上是比较次数)。数据的设计方式是,它将形成完美的二进制搜索树。然而,在计算了平均成本后,我意识到红黑树的计算平均搜索成本略高于完全平衡的二进制搜索树。下面是我的表格:
# of elements Binary S. Tree Red-Black Tree
1 | 1 | 1
3 | 1.66667 | 1.6667
7 | 2.42857 |
受这个问题的启发:Why isn't std::set just called std::binary_tree?,我想出了一个我自己的想法。红黑树是唯一可能满足std::set需求的数据结构吗?还有其他的吗?例如,另一种自平衡树- AVL tree -似乎是具有非常相似属性的很好的替代。理论上有没有可能取代std::set的底层数据结构,或者有没有一组要求使红黑树成为唯一可行的选择?
我试图找出在红黑树的旋转,而它的再平衡已经完成。我明白为什么轮换会发生,但我不明白是怎么做到的。此外,什么样的中间轮,如LL,RR,LR和RL,直到结果,我也会很感激,如果有人告诉我的经验规则,什么时候做任何这些轮换。这是轮调:
Rr(2) is the case when black node deficiency is in right child of "py" i.e.
"y" and grandchild of "v" are 2 red nodes i.e. "b" and "x"
考虑一个有n个内部节点的红黑树,其中n是偶数.最多有多少人可以是一个带一个红色孩子的黑色节点?
A. n/2 B. C. lg(n+1-1 D. lg(n+1 E. )
在达到上述问题解决方案的26个节点的红黑树中,树的最大高度是多少?一个节点的树被假定有高度1。
A. 5 B. 6 C. 7 D. 8 E. 9