我知道红黑树只是一个平衡的二进制搜索树。所以我计算了元素数量为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的底层数据结构,或者有没有一组要求使红黑树成为唯一可行的选择?