X-Git-Url: http://nitlanguage.org diff --git a/lib/trees/rbtree.nit b/lib/trees/rbtree.nit index ce17feb..7310ac7 100644 --- a/lib/trees/rbtree.nit +++ b/lib/trees/rbtree.nit @@ -32,17 +32,17 @@ import bintree # Red-Black Tree Map # Properties of a Red-Black tree map: -# * every node is either red or black -# * root is black -# * every leaf (null) is black -# * if a node is red, then both its children are black -# * for each node, all simple path from the node to descendant -# leaves contain the same number of black nodes +# * every node is either red or black +# * root is black +# * every leaf (null) is black +# * if a node is red, then both its children are black +# * for each node, all simple path from the node to descendant +# leaves contain the same number of black nodes # # Operations: -# * search average O(lg n) worst O(lg n) -# * insert average O(lg n) worst O(lg n) -# * delete average O(lg n) worst O(lg n) +# * search average O(lg n) worst O(lg n) +# * insert average O(lg n) worst O(lg n) +# * delete average O(lg n) worst O(lg n) class RBTreeMap[K: Comparable, E] super BinTreeMap[K, E] @@ -130,7 +130,7 @@ end class RBTreeNode[K: Comparable, E] super BinTreeNode[K, E] - redef type SELF: RBTreeNode[K, E] + redef type N: RBTreeNode[K, E] # Is the node red? private var is_red = true @@ -144,4 +144,3 @@ class RBTreeNode[K: Comparable, E] end end -