Package flumotion :: Package common :: Module avltree
[show private | hide private]
[frames | no frames]

Module flumotion.common.avltree

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
AVLTree  

Function Summary
  debug(tree, level)
Print out a debugging representation of an AVL tree.
  delete(tree, value)
Delete a value from an AVL tree.
  fromseq(seq)
Populate and return an AVL tree from an iterable sequence.
  height(tree)
Return the height of an AVL tree.
  insert(tree, value)
Insert a value into an AVL tree.
  iterate(tree)
Iterate over an AVL tree, starting with the lowest-ordered value.
  iteratereversed(tree)
Iterate over an AVL tree, starting with the highest-ordered value.
  lookup(tree, value)
Look up a node in an AVL tree.
  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.

Function Details

debug(tree, level=0)

Print out a debugging representation of an AVL tree.

delete(tree, value)

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

fromseq(seq)

Populate and return an AVL tree from an iterable sequence.

height(tree)

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

insert(tree, value)

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

iterate(tree)

Iterate over an AVL tree, starting with the lowest-ordered value.

iteratereversed(tree)

Iterate over an AVL tree, starting with the highest-ordered value.

lookup(tree, value)

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

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.

Generated by Epydoc 2.1 on Sat Apr 14 13:16:51 2007 http://epydoc.sf.net