我想在哈斯克尔写一棵红黑树。在红黑树的属性中,所有不包含数据的叶子都是黑色的。
我想写这样的东西:
data EmptyNode = EmptyNode{
data = ???,
color = ???, <-- it should black (assume that it is False)
left = ???,
right = ???
}
data NodeBR a = NodeBR {
data :: a,
color :: Bool,
left :: NodeBR,
right :: NodeBR
}
data TreeBR a = EmptyNode
我正在研究TreeMap in JAVA的源代码。根据JAVA文档:
一个基于红黑树的NavigableMap实现。映射根据其键的自然顺序进行排序,或者由在地图创建时提供的比较器进行排序,这取决于所使用的构造函数。
该实现为containsKey、get、put和remove操作提供了保证的日志(N)时间开销。算法是那些在Cormen,Leiserson,和Rivest对算法的介绍的适应。
在源代码中,我发现内部类条目被用作节点。
static final class Entry<K,V> implements Map.Entry<K,V> {