Package flumotion :: Package common :: Module avltree
[hide private]

Module avltree

source code

A pure python functional-style self-balancing binary search tree implementation, with an object-oriented wrapper. Useful for maintaining sorted sets, traversing sets in order, and closest-match lookups.

Classes [hide private]
  AVLTree
Functions [hide private]
 
node(l, v, r, b)
Make an AVL tree node, consisting of a left tree, a value, a right tree, and the "balance factor": the difference in lengths between the right and left sides, respectively.
source code
 
height(tree)
Return the height of an AVL tree.
source code
 
debug(tree, level=0)
Print out a debugging representation of an AVL tree.
source code
 
fromseq(seq)
Populate and return an AVL tree from an iterable sequence.
source code
 
_balance(hdiff, l, v, r, b)
Internal method to rebalance an AVL tree, called as needed.
source code
 
insert(tree, value)
Insert a value into an AVL tree.
source code
 
delete(tree, value)
Delete a value from an AVL tree.
source code
 
lookup(tree, value)
Look up a node in an AVL tree.
source code
 
iterate(tree)
Iterate over an AVL tree, starting with the lowest-ordered value.
source code
 
iteratereversed(tree)
Iterate over an AVL tree, starting with the highest-ordered value.
source code
Function Details [hide private]

height(tree)

source code 

Return the height of an AVL tree. Relies on the balance factors being consistent.

insert(tree, value)

source code 

Insert a value into an AVL tree. Returns a tuple of (heightdifference, tree). The original tree is unmodified.

delete(tree, value)

source code 

Delete a value from an AVL tree. Like insert, returns a tuple of (heightdifference, tree). The original tree is unmodified.

lookup(tree, value)

source code 

Look up a node in an AVL tree. Returns a node tuple or False if the value was not found.