RBNode

Undocumented in source.

struct RBNode (

V

) {

inout(RBNode)* left [@property getter];

inout(RBNode)* right [@property getter];

inout(RBNode)* parent [@property getter];

Node left [@property setter];

Node right [@property setter];

Node rotateR();

Node rotateL();

bool isLeftNode [@property getter];

void setColor(Node end);

Node remove(Node end);

inout(RBNode)* leftmost [@property getter];

inout(RBNode)* rightmost [@property getter];

inout(RBNode)* next [@property getter];

inout(RBNode)* prev [@property getter];

}

Members

Enums

Color enum Color: Enumeration determining what color the node is. Null nodes are assumed to be black.

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(RBNode)* 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 inout(RBNode)* leftmost [@property getter]: Return the leftmost descendant of this node.
next inout(RBNode)* next [@property getter]: Returns the next valued node in the tree.
parent inout(RBNode)* parent [@property getter]: Get the parent
prev inout(RBNode)* prev [@property getter]: Returns the previous valued node in the tree.
right inout(RBNode)* 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 inout(RBNode)* rightmost [@property getter]: Return the rightmost descendant of this node

Variables

color Color color;: The color of the node.
value V value;: The value held by this node

Meta

Source

See Implementation

std container rbtree classes

RedBlackTree

functions

redBlackTree

structs

RBNode