我知道红黑树只是一个平衡的二进制搜索树。所以我计算了元素数量为2^n的数据集的平均搜索成本(基本上是比较次数)。数据的设计方式是,它将形成完美的二进制搜索树。然而,在计算了平均成本后,我意识到红黑树的计算平均搜索成本略高于完全平衡的二进制搜索树。下面是我的表格:
# of elements Binary S. Tree Red-Black Tree
1 | 1 | 1
3 | 1.66667 | 1.6667
7 | 2.42857 |
我正在研究TreeMap in JAVA的源代码。根据JAVA文档:
一个基于红黑树的NavigableMap实现。映射根据其键的自然顺序进行排序,或者由在地图创建时提供的比较器进行排序,这取决于所使用的构造函数。
该实现为containsKey、get、put和remove操作提供了保证的日志(N)时间开销。算法是那些在Cormen,Leiserson,和Rivest对算法的介绍的适应。
在源代码中,我发现内部类条目被用作节点。
static final class Entry<K,V> implements Map.Entry<K,V> {
受这个问题的启发:Why isn't std::set just called std::binary_tree?,我想出了一个我自己的想法。红黑树是唯一可能满足std::set需求的数据结构吗?还有其他的吗?例如,另一种自平衡树- AVL tree -似乎是具有非常相似属性的很好的替代。理论上有没有可能取代std::set的底层数据结构,或者有没有一组要求使红黑树成为唯一可行的选择?