dsap.searchtree.splay_tree.SplayTreeMap

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	_splay	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	_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).
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 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.