OrderedNodeMixin

ordered node implementation

Members

Functions

remove
Node remove(Node end)

Remove this node from the tree. The 'end' node is used as the marker which is root's parent. Note that this cannot be null!

rotateL
Node rotateL()

Rotate left. This performs the following operations: - The right child becomes the parent of this node. - This node becomes the new parent's left child. - The old left child of the new parent becomes the right child of this node.

rotateR
Node rotateR()

Rotate right. This performs the following operations: - The left child becomes the parent of this node. - This node becomes the new parent's right child. - The old right child of the new parent becomes the left child of this node.

setColor
void setColor(Node end)

Set the color of the node after it is inserted. This performs an update to the whole tree, possibly rotating nodes to keep the Red-Black properties correct. This is an O(lg(n)) operation, where n is the number of nodes in the tree.

Properties

isLeftNode
bool isLeftNode [@property getter]

Returns true if this node is a left child.

left
inout(typeof(this))* left [@property getter]

Get the left child

left
Node left [@property setter]

Set the left child. Also updates the new child's parent node. This does not update the previous child.

leftmost
leftmost [@property getter]

Return the leftmost descendant of this node.

next
inout(typeof(this))* next [@property getter]

Returns the next valued node in the tree.

parent
Node parent [@property getter]

Get the parent

prev
inout(typeof(this))* prev [@property getter]

Returns the previous valued node in the tree.

right
inout(typeof(this))* right [@property getter]

Get the right child

right
Node right [@property setter]

Set the right child. Also updates the new child's parent node. This does not update the previous child.

rightmost
rightmost [@property getter]

Return the rightmost descendant of this node

Variables

color
Color color;

The color of the node.

Meta