dsap.searchtree.red_black_tree.RedBlackTreeMap

class documentation

class RedBlackTreeMap(TreeMap):

View In Hierarchy

Sorted map implementation using a red-black tree.

Class _Node Node class for red-black tree maintains bit that denotes color.
Method _fix_deficit Resolve black deficit at z, where y is the root of z's heavier subtree.
Method _get_red_child Return a red child of p (or None if no such child).
Method _is_red Undocumented
Method _is_red_leaf Undocumented
Method _rebalance_delete Call to indicate that a child of p has been removed.
Method _rebalance_insert Call to indicate that position p is newly added.
Method _resolve_red Undocumented
Method _set_black Undocumented
Method _set_color Undocumented
Method _set_red Undocumented

Inherited from TreeMap:

Class Position No class docstring; 2/2 methods documented
Method __delitem__ Remove item associated with key k (raise KeyError if not found).
Method __getitem__ Return value associated with key k (raise KeyError if not found).
Method __iter__ Generate an iteration of all keys in the map in order.
Method __reversed__ Generate an iteration of all keys in the map in reverse order.
Method __setitem__ Assign value v to key k, overwriting existing value if present.
Method after Return the Position just after p in the natural order.
Method before Return the Position just before p in the natural order.
Method delete Remove the item at given Position.
Method find_ge Return (key,value) pair with least key greater than or equal to k.
Method find_gt Return (key,value) pair with least key strictly greater than k.
Method find_le Return (key,value) pair with greatest key less than or equal to k.
Method find_lt Return (key,value) pair with greatest key strictly less than k.
Method find_max Return (key,value) pair with maximum key (or None if empty).
Method find_min Return (key,value) pair with minimum key (or None if empty).
Method find_position Return position with key k, or else neighbor (or None if empty).
Method find_range Iterate all (key,value) pairs such that start <= key < stop.
Method first Return the first Position in the tree (or None if empty).
Method last Return the last Position in the tree (or None if empty).
Method _rebalance_access Call to indicate that position p was recently accessed.
Method _relink Relink parent node with child node (we allow child to be None).
Method _restructure Perform a trinode restructure among Position x, its parent, and its grandparent.
Method _rotate Rotate Position p above its parent.
Method _subtree_first_position Return Position of first item in subtree rooted at p.
Method _subtree_last_position Return Position of last item in subtree rooted at p.
Method _subtree_search Return Position of p's subtree having key k, or last node searched.
Instance Variable _root Undocumented

Inherited from LinkedBinaryTree (via TreeMap):

Method __init__ Create an initially empty binary tree.
Method __len__ Return the total number of elements in the tree.
Method left Return the Position of p's left child (or None if no left child).
Method num_children Return the number of children of Position p.
Method parent Return the Position of p's parent (or None if p is root).
Method right Return the Position of p's right child (or None if no right child).
Method root Return the root Position of the tree (or None if tree is empty).
Method _add_left Create a new left child for Position p, storing element e.
Method _add_right Create a new right child for Position p, storing element e.
Method _add_root Place element e at the root of an empty tree and return new Position.
Method _attach Attach trees t1 and t2, respectively, as the left and right subtrees of the external Position p.
Method _delete Delete the node at Position p, and replace it with its child, if any.
Method _make_position Return Position instance for given node (or None if no node).
Method _replace Replace the element at position p with e, and return old element.
Method _validate Return associated node, if position is valid.
Instance Variable _size Undocumented

Inherited from BinaryTree (via TreeMap, LinkedBinaryTree):

Method children Generate an iteration of Positions representing p's children.
Method inorder Generate an inorder iteration of positions in the tree.
Method positions Generate an iteration of the tree's positions.
Method sibling Return a Position representing p's sibling (or None if no sibling).
Method _subtree_inorder Generate an inorder iteration of positions in subtree rooted at p.

Inherited from Tree (via TreeMap, LinkedBinaryTree, BinaryTree):

Method breadthfirst Generate a breadth-first iteration of the positions of the tree.
Method depth Return the number of levels separating Position p from the root.
Method height Return the height of the subtree rooted at Position p.
Method is_empty Return True if the tree is empty.
Method is_leaf Return True if Position p does not have any children.
Method is_root Return True if Position p represents the root of the tree.
Method postorder Generate a postorder iteration of positions in the tree.
Method preorder Generate a preorder iteration of positions in the tree.
Method _height_bad Return the height of the tree.
Method _height_good Return the height of the subtree rooted at Position p.
Method _subtree_postorder Generate a postorder iteration of positions in subtree rooted at p.
Method _subtree_preorder Generate a preorder iteration of positions in subtree rooted at p.

Inherited from MapBase (via TreeMap, LinkedBinaryTree, BinaryTree, Tree):

Class _Item Lightweight composite to store key-value pairs as map items.
def _fix_deficit(self, z, y):

Resolve black deficit at z, where y is the root of z's heavier subtree.

def _get_red_child(self, p):

Return a red child of p (or None if no such child).

def _is_red(self, p):

Undocumented

def _is_red_leaf(self, p):

Undocumented

def _rebalance_delete(self, p):
overrides dsap.searchtree.binary_search_tree.TreeMap._rebalance_delete

Call to indicate that a child of p has been removed.

def _rebalance_insert(self, p):
overrides dsap.searchtree.binary_search_tree.TreeMap._rebalance_insert

Call to indicate that position p is newly added.

def _resolve_red(self, p):

Undocumented

def _set_black(self, p):

Undocumented

def _set_color(self, p, make_red):

Undocumented

def _set_red(self, p):

Undocumented