我知道红黑树只是一个平衡的二进制搜索树。所以我计算了元素数量为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> {