PHP AVL binary search tree

A set of PHP classes implementing binary search trees that comply to AVL rules. The API exposes methods for tree operations (insert, replace, delete, find), and for inorder traversal (find, first, last, prev, next, curr). Tree and traversal operations implement relaxed balance factors, and parent pointer node structures. Hooks for node comparison, error handling and diagnostic logging are provided via a callback interface.

What are AVL trees?
In an nutshell, AVL trees are a form of binary search trees that can be used to keep a set of data efficiently sorted while adding or removing elements. For more details, Wikipedia has articles for binary search trees and AVL trees.

What about 'relaxed balance factors'?
Without getting into all the theory, AVL trees in their 'canonical form', i.e. where the heights of the two child subtrees of any node differ by at most one, are very efficient for lookup, but require in average a rotation operation every two insert or delete operations. By default, Rbppavl handles trees in canonical AVL form, but optionally allows to 'relax' the balancing factor, allowing the height difference to be any integer value. Empirical evidence shows that, in average, each increase of the allowed imbalance almost halves the number of rotations expected. On the other side, the overall height of the tree will increase, and lookup operations become less efficient.

What about parent pointer node structures?
In Rbppavl, each node in the tree stores a link to its 'parent' node. This allows to simplify traversal by eliminating the need for a stack, i.e. given a node, getting to previous or next inorder node can be accomplished just with the information stored in the node itself.

Prerequisites

• PHP 5.2.13 (this is the lowest PHP release tested with)

License
GNU GPLv3

Documentation
Rbppavl documentation is available in the Rbppavl_doc directory. Documentation is generated by docBlox.

Acknowledgments
Large parts of Rbppavl implementation are taken from Ben Pfaff's GNU libavl.

Basic usage example

1. Include Rbppavl

   require_once 'Rbppavl/Rbppavl.php';

2. Define your data object and the callback interface to be used by Rbppavl

   class TestObject { public $q; }

   class TestCallback implements RbppavlCbInterface {

    public function compare($a, $b)    {
    	return ($a->q == $b->q) ? 0 : (($a->q < $b->q) ? -1 : 1);
    }
   
    public function dump($a)    {
    	return $a->q;
    }
   
    public function diagnosticMessage($severity, $id, $text, $params, $qText,$className = null) {
    	return null;
    }
   
    public function errorHandler($id, $text, $params, $qText, $className = null) {
    	return null;
    }
   

   }

3. Create a tree

   $tree = new RbppavlTree('TestCallback');

4. Insert some data objects

   $seq = array(12, 7, 36, 4, 1, 28, 3); foreach ($seq as $value) { $data = new TestObject; $data->q = $value; $t = $tree->insert($data); }

5. Perform inorder traversal, printing each value

   $trav = new RbppavlTraverser($tree); $r = $trav->first(); while ($r != NULL) { print($r->q . '
   '); $r = $trav->next(); }

More examples

The source code in the files listed below introduce more usage examples:

• simple_test.php generates a few random integers, inserts them in a standard AVL tree, validates the tree, performs an inorder traversal, then deletes the tree and its content.

• full_test.php demonstrate more complex test cases:

  • movie - Shows in detail the tree balancing operations while inserting and deleting a limited set of nodes from a canonical AVL tree.
  • forest - Generates a large number of trees of increasing imbalance, with random node values, to get summary statistics on height and rotations.
  • burp - Fill memory with random value node insertions, up to the threshold defined by memoryThreshold, then randomly deletes all the nodes.
  • lorem ipsum - Always repeats operations on the same set of data, the "Lorem ipsum" standard. Showcase for using strings instead of integers.
  • mirabilis res - Same as "Lorem ipsum", with latinized (?) diagnostic. Showcase for localization of diagnostic messages.