dsap.searchtree.binary_search_tree.TreeMap

class documentation

class TreeMap(LinkedBinaryTree, MapBase):

Known subclasses: dsap.searchtree.avl_tree.AVLTreeMap, dsap.searchtree.red_black_tree.RedBlackTreeMap, dsap.searchtree.splay_tree.SplayTreeMap

View In Hierarchy

Sorted map implementation using a binary search tree.

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 _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 _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:

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).
Class _Node Lightweight, nonpublic class for storing a node.
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 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 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 LinkedBinaryTree, BinaryTree, Tree):

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

Remove item associated with key k (raise KeyError if not found).

def __getitem__(self, k):

Return value associated with key k (raise KeyError if not found).

def __iter__(self):
overrides dsap.trees.tree.Tree.__iter__

Generate an iteration of all keys in the map in order.

def __reversed__(self):

Generate an iteration of all keys in the map in reverse order.

def __setitem__(self, k, v):

Assign value v to key k, overwriting existing value if present.

def after(self, p):

Return the Position just after p in the natural order.

Return None if p is the last position.

def before(self, p):

Return the Position just before p in the natural order.

Return None if p is the first position.

def delete(self, p):

Remove the item at given Position.

def find_ge(self, k):

Return (key,value) pair with least key greater than or equal to k.

Return None if there does not exist such a key.

def find_gt(self, k):

Return (key,value) pair with least key strictly greater than k.

Return None if there does not exist such a key.

def find_le(self, k):

Return (key,value) pair with greatest key less than or equal to k.

Return None if there does not exist such a key.

def find_lt(self, k):

Return (key,value) pair with greatest key strictly less than k.

Return None if there does not exist such a key.

def find_max(self):

Return (key,value) pair with maximum key (or None if empty).

def find_min(self):

Return (key,value) pair with minimum key (or None if empty).

def find_position(self, k):

Return position with key k, or else neighbor (or None if empty).

def find_range(self, start, stop):

Iterate all (key,value) pairs such that start <= key < stop.

If start is None, iteration begins with minimum key of map. If stop is None, iteration continues through the maximum key of map.

def first(self):

Return the first Position in the tree (or None if empty).

def last(self):

Return the last Position in the tree (or None if empty).

def _rebalance_access(self, p):
overridden in dsap.searchtree.splay_tree.SplayTreeMap

Call to indicate that position p was recently accessed.

def _rebalance_delete(self, p):
overridden in dsap.searchtree.avl_tree.AVLTreeMap, dsap.searchtree.red_black_tree.RedBlackTreeMap, dsap.searchtree.splay_tree.SplayTreeMap

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

def _rebalance_insert(self, p):
overridden in dsap.searchtree.avl_tree.AVLTreeMap, dsap.searchtree.red_black_tree.RedBlackTreeMap, dsap.searchtree.splay_tree.SplayTreeMap

Call to indicate that position p is newly added.

def _relink(self, parent, child, make_left_child):

Relink parent node with child node (we allow child to be None).

def _restructure(self, x):

Perform a trinode restructure among Position x, its parent, and its grandparent.

Return the Position that becomes root of the restructured subtree.

Assumes the nodes are in one of the following configurations:

       z=a                 z=c           z=a               z=c
      /  \                /  \          /  \              /              t0  y=b             y=b  t3       t0   y=c          y=a  t3
       /  \            /  \               /  \         /                t1  x=c         x=a  t2            x=b  t3      t0   x=b
         /  \        /  \               /  \              /                  t2  t3      t0  t1             t1  t2            t1  t2

The subtree will be restructured so that the node with key b becomes its root:

                b
              /                       a       c
           / \     /                  t0  t1  t2  t3

Caller should ensure that x has a grandparent.

def _rotate(self, p):

Rotate Position p above its parent.

Switches between these configurations, depending on whether p==a or p==b:

          b                   a
         / \                 /                 a  t2              t0   b
       / \                     /              t0  t1                  t1  t2

Caller should ensure that p is not the root.

def _subtree_first_position(self, p):

Return Position of first item in subtree rooted at p.

def _subtree_last_position(self, p):

Return Position of last item in subtree rooted at p.

def _subtree_search(self, p, k):

Return Position of p's subtree having key k, or last node searched.

_root =
overrides dsap.trees.linked_binary_tree.LinkedBinaryTree._root

Undocumented