Module

load container.redblacktree

This module provides the Container.RedBlackTree class which is a low level class to store and search ordered elements.

Packages

• Container

Enums

Container.RedBlackTree.Color

The color of a node used to ensure that the tree remains approximately balanced during insertions and deletions.

Constant	Value	Description
Black	1	The node is black.
Red	0	The node is red.

Classes

Container.RedBlackTree

This class create a self-balancing binary search tree. Each node stores a Container.RedBlackTree.Color, used to ensure that the tree remains approximately balanced during insertions and deletions.

Each node of the tree store a key value. A comparator function must be provided to the class instances to be used to sort keys. The values used as key in the instances must provide the operator used by the function.

Public members

Modifiers	Member	Description
enum	Color	The color of a node used to ensure that the tree remains approximately balanc...
const	delete	Cleans up the tree instance.
const	each	Apply the func function to each elements of the tree.
const	find	Returns the value key in the tree. If key is not contained in the tree, ...
const	getComparator	Returns the comparator function used by the tree.
const	insert	Inserts key in the tree. If key is already contained in the tree, this me...
const	isEmpty	Returns true if the tree is empty; otherwise returns false.
const	new	Creates a new instance of Container.RedBlackTree. The comparator function c...
const	remove	Removes the element associated to the specified key in the tree. If key i...

Private members

Modifiers	Member	Description
class	Node	This class describe a node of the tree. A node store a color and a key value.
final	comparator	Internal comparator function.
final	root	Internal root node.

Container.RedBlackTree.Node

This class describe a node of the tree. A node store a color and a key value.

Public members

Modifiers	Member	Description
const	deleteOneChild	Deletes the last child of this node.
const	each	Applies recursively the func function to the key value of each node.
const	find	Searchs recursively for a node with a key value that match key using the ``...
const	getGrandParent	Returns the parent of this node's parent or null if this node or his parent...
const	getKey	Returns the key value of the node.
const	getParent	Returns the parent node of the node or null if the node is the root node.
const	getSibling	Returns the sibling node of this node or null if this node has no sibling. ...
const	getUncle	Returns the uncle node of this node or null if this node has no uncle. The ...
const	insert	Inserts the node new node under this node. The comparator function is use...
const	new	Creates a new node with the color color and the value key.
const	replaceChild	Replaces this node by child.
const	rotateLeft	Rotates the node to the left.
const	rotateRight	Rotates the node to the right.

Private members

Modifiers	Member	Description
final	color	Internal color.
final const	deleteCase1	Repaires after deletion case 1: if the current node is the new root then we a...
final const	deleteCase2	Repaires after deletion case 2: the current node's sibling is red. The co...
final const	deleteCase3	Repaires after deletion case 3: if the parent node, sibling node and sibling ...
final const	deleteCase4	Repaires after deletion case 4: if the sibling node and sibling children are ...
final const	deleteCase5	Repaires after deletion case 5: if the sibling node is black, the sibling...
final const	deleteCase6	Repaires after deletion case 6: the sibling node is black, the sibling no...
final const	insertCase1	Repaires after insertion case 1: the current node is the root of the tree. Th...
final const	insertCase2	Repaires after insertion case 2: the current node parent is balck, then t...
final const	insertCase3	Repaires after insertion case 3: the current node's parent is red. The co...
final const	insertCase4	Repaires after insertion case 4: if the uncle is black, a rotation must b...
final const	insertCase5	Repaires after insertion case 5: the parent must be swapped with the grand-pa...
final const	insertRecurse	Tries recursively to insert the node new node in the tree using the compa...
final const	insertRepairTree	Repaires the tree after an insertion.
final	key	Internal key value.
final	left	Internal left child node.
final	parent	Internal parent node.
final	right	Internal right child node.

Descriptions

Container.RedBlackTree.Color.Black

1

The node is black.

Container.RedBlackTree.Color.Red

0

The node is red.

Container.RedBlackTree.Node.color

none

Internal color.

Container.RedBlackTree.Node.deleteCase1

def (self)

Repaires after deletion case 1: if the current node is the new root then we are done; otherwise deleteCase2 must be executed.

Container.RedBlackTree.Node.deleteCase2

def (self)

Repaires after deletion case 2: the current node's sibling is red. The color of the parent node and the sibling node must be reversed and the parent must be rotated left turning the sibling into node's grand-parent. The resulting subtree has a path short one black node so deleteCase3 must be executed.

Container.RedBlackTree.Node.deleteCase3

def (self)

Repaires after deletion case 3: if the parent node, sibling node and sibling children are both black, the sibling color is changed into red and deleteCase3 is applied to parent node; otherwise deleteCase4 must be executed.

Container.RedBlackTree.Node.deleteCase4

def (self)

Repaires after deletion case 4: if the sibling node and sibling children are both black but the parent node is red, the sibling node's and parent node's color must be swapped; otherwise deleteCase5 must be executed.

Container.RedBlackTree.Node.deleteCase5

def (self)

Repaires after deletion case 5: if the sibling node is black, the sibling node's left child is red, the sibling node's right child is black and the current node is the left child of its parent, the sibling node must be rotated right, so that the sibling node's left child becomes the sibling node's parent and the current node's new sibling. The color of the sibling node and its new parent must then be exchanged. In any case, deleteCase6 must be executed.

Container.RedBlackTree.Node.deleteCase6

def (self)

Repaires after deletion case 6: the sibling node is black, the sibling node's right child is red.

If the current node is the left child of its parent, the parent node must be rotated left, so that the sibling node becomes the parent of the parent node and the sibling node's right child. The color of the parent node and the sibling node must then be exchanged and the sibling node's right child must be turned black.

If the current node is the right child of its parent, the parent node must be rotated right. The color of the parent node and the sibling node must then be exchanged and the sibling node's left child must be turned black.

Container.RedBlackTree.Node.deleteOneChild

def (self)

Deletes the last child of this node.

Container.RedBlackTree.Node.each

def (const self, func)

Applies recursively the func function to the key value of each node.

Container.RedBlackTree.Node.find

def (const self, key, comparator)

Searchs recursively for a node with a key value that match key using the comparator function. The comparator function must return true if the first parameter value is less tahn the second parameter value.

Returns the first node that have a match or none if no node was found.

Container.RedBlackTree.Node.getGrandParent

def (const self)

Returns the parent of this node's parent or null if this node or his parent is the root node.

Container.RedBlackTree.Node.getKey

def (const self)

Returns the key value of the node.

Container.RedBlackTree.Node.getParent

def (const self)

Returns the parent node of the node or null if the node is the root node.

Container.RedBlackTree.Node.getSibling

def (const self)

Returns the sibling node of this node or null if this node has no sibling. The sibling node is the other child node of this node parent.

Container.RedBlackTree.Node.getUncle

def (const self)

Returns the uncle node of this node or null if this node has no uncle. The uncle node is the other child node of the parent node of this node's parent.

Container.RedBlackTree.Node.insert

def (self, node, comparator)

Inserts the node new node under this node. The comparator function is used to sort the newly inserted node.

Returns the new root node of the tree.

Container.RedBlackTree.Node.insertCase1

def (self)

Repaires after insertion case 1: the current node is the root of the tree. The only correction to apply is to set the node's color to black.

Container.RedBlackTree.Node.insertCase2

def (self)

Repaires after insertion case 2: the current node parent is balck, then the tree is valid.

Container.RedBlackTree.Node.insertCase3

def (self)

Repaires after insertion case 3: the current node's parent is red. The correction to apply denpend on the uncle node's color: if it is red, then the parent node and the uncle node should be black and the grand-parent (that was necessarily black) should be red. This change could however have created a new violation in the tree. The grand-parent must now be repaired.

Container.RedBlackTree.Node.insertCase4

def (self)

Repaires after insertion case 4: if the uncle is black, a rotation must be applied depending on the inserted node parent and grand-parent and insertCase5 must be executed.

Container.RedBlackTree.Node.insertCase5

def (self)

Repaires after insertion case 5: the parent must be swapped with the grand-parent and the grand-parent with the uncle. The parent become red and the tree is repaired.

Container.RedBlackTree.Node.insertRecurse

def (self, node, comparator)

Tries recursively to insert the node new node in the tree using the comparator function. The comparator function must return true if the first parameter value is less tahn the second parameter value.

Returns true if the node can be inserted in the tree; otherwise returns false and the node is not inserted.

Container.RedBlackTree.Node.insertRepairTree

def (self)

Repaires the tree after an insertion.

Container.RedBlackTree.Node.key

none

Internal key value.

Container.RedBlackTree.Node.left

null

Internal left child node.

Container.RedBlackTree.Node.new

def (self, color, key)

Creates a new node with the color color and the value key.

Container.RedBlackTree.Node.parent

null

Internal parent node.

Container.RedBlackTree.Node.replaceChild

def (self, child)

Replaces this node by child.

Container.RedBlackTree.Node.right

null

Internal right child node.

Container.RedBlackTree.Node.rotateLeft

def (self)

Rotates the node to the left.

Container.RedBlackTree.Node.rotateRight

def (self)

Rotates the node to the right.

Container.RedBlackTree.comparator

none

Internal comparator function.

Container.RedBlackTree.delete

def (self)

Cleans up the tree instance.

Container.RedBlackTree.each

def (const self, func)

Apply the func function to each elements of the tree.

Container.RedBlackTree.find

def (const self, key)

Returns the value key in the tree.

If key is not contained in the tree, none is returned instead.

Container.RedBlackTree.getComparator

def (const self)

Returns the comparator function used by the tree.

Container.RedBlackTree.insert

def (self, key)

Inserts key in the tree. If key is already contained in the tree, this method has no effect.

Container.RedBlackTree.isEmpty

def (const self)

Returns true if the tree is empty; otherwise returns false.

Container.RedBlackTree.new

def (self, comparator = hashKeyCompareOperator)

Creates a new instance of Container.RedBlackTree. The comparator function can be overloaded to change the key sorting behaviour of the tree. By default, the same behaviour than the hash keys is used.

Container.RedBlackTree.remove

def (self, key)

Removes the element associated to the specified key in the tree.

If key is not contained in the tree, false is returned; otherwise true is returned.

Container.RedBlackTree.root

null

Internal root node.