trees :: BinTreeNode
trees :: BinTreeNode :: defaultinit
trees :: BinTreeNode :: grandparent
parent
of the parent
of this node (null if root)
trees :: BinTreeNode :: left
left
tree node child (null if node has no left child)
trees :: BinTreeNode :: left=
setleft
child for this node (or null if left no child)
trees :: BinTreeNode :: right
right
tree node child (null if node has no right child)
trees :: BinTreeNode :: right=
setright
child for this node (or null if right no child)
trees $ BinTreeNode :: SELF
Type of this instance, automatically specialized in every classcore :: Object :: class_factory
Implementation used byget_class
to create the specific class.
core :: Object :: defaultinit
trees :: BinTreeNode :: defaultinit
core :: Comparable :: defaultinit
trees :: TreeNode :: defaultinit
trees :: BinTreeNode :: grandparent
parent
of the parent
of this node (null if root)
core :: Object :: is_same_instance
Return true ifself
and other
are the same instance (i.e. same identity).
core :: Object :: is_same_serialized
Isself
the same as other
in a serialization context?
core :: Object :: is_same_type
Return true ifself
and other
have the same dynamic type.
trees :: BinTreeNode :: left
left
tree node child (null if node has no left child)
trees :: BinTreeNode :: left=
setleft
child for this node (or null if left no child)
core :: Object :: output_class_name
Display class name on stdout (debug only).trees :: BinTreeNode :: right
right
tree node child (null if node has no right child)
trees :: BinTreeNode :: right=
setright
child for this node (or null if right no child)
Tree
implementation
trees :: RBTreeNode
RedBlackTree node (can be red or black)
# TreeNode used by BinTree
class BinTreeNode[K: Comparable, E]
super TreeNode[K, E]
private var prev: nullable BinTreeNode[K, E] = null
private var next: nullable BinTreeNode[K, E] = null
redef type N: BinTreeNode[K, E]
private var left_node: nullable N = null
# `left` tree node child (null if node has no left child)
fun left: nullable N do return left_node
# set `left` child for this node (or null if left no child)
# ENSURE: node.key < key (only if node != null)
fun left=(node: nullable N) do
#assert node != null implies node.key < key
left_node = node
end
private var right_node: nullable N = null
# `right` tree node child (null if node has no right child)
fun right: nullable N do return right_node
# set `right` child for this node (or null if right no child)
# ENSURE: node.key < key (only if node != null)
fun right=(node: nullable N) do
#assert node != null implies node.key > key
right_node = node
end
# `parent` of the `parent` of this node (null if root)
fun grandparent: nullable N do
if parent == null then
return null
else
return parent.parent
end
end
# Other child of the `grandparent`
# `left` or `right` depends on the position of the current node against its parent
fun uncle: nullable N do
var g = grandparent
if g == null then
return null
else
if parent == g.left then
return g.right
else
return g.left
end
end
end
# Other child of the parent
# `left` or `right` depends on the position of the current node against its parent
fun sibling: nullable N do
if parent == null then
return null
else if self == parent.left then
return parent.right
else if self == parent.right then
return parent.left
else
return null
end
end
redef fun to_s do return "\{{key}: {value or else ""}\}"
end
lib/trees/bintree.nit:379,1--451,3