Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with
or
.
Download ZIP
Newer
Older
100644 122 lines (92 sloc) 4.581 kB
c3099d7 @mondrake initial push
authored
1 # PHP AVL binary search tree #
2
3 A set of PHP classes implementing binary search trees that comply to AVL
4 rules.
5 The API exposes methods for tree operations (insert, replace, delete,
6 find), and for inorder traversal (find, first, last, prev, next, curr).
7 Tree and traversal operations implement relaxed balance factors, and
8 parent pointer node structures.
9 Hooks for node comparison, error handling and diagnostic logging
10 are provided via a callback interface.
11
12 <strong>What are AVL trees?</strong>
13 In an nutshell, AVL trees are a form of binary search trees that can be
14 used to keep a set of data efficiently sorted while adding or removing
15 elements.
16 For more details, Wikipedia has articles for [binary search trees](http://en.wikipedia.org/wiki/Binary_search_tree)
17 and [AVL trees](http://en.wikipedia.org/wiki/AVL_tree).
18
19 <strong>What about 'relaxed balance factors'?</strong>
20 Without getting into all the theory, AVL trees in their 'canonical
21 form', i.e. where the heights of the two child subtrees of any node
22 differ by at most one, are very efficient for lookup, but require in
23 average a rotation operation every two insert or delete operations. By
24 default, Rbppavl handles trees in canonical AVL form, but optionally
25 allows to 'relax' the balancing factor, allowing the height difference
26 to be any integer value. Empirical evidence shows that, in average, each
27 increase of the allowed imbalance almost _halves_ the number of
28 rotations expected. On the other side, the overall height of the tree
29 will increase, and lookup operations become less efficient.
30
31 <strong>What about parent pointer node structures?</strong>
32 In Rbppavl, each node in the tree stores a link to its 'parent' node.
33 This allows to simplify traversal by eliminating the need for a stack,
34 i.e. given a node, getting to previous or next inorder node can be
35 accomplished just with the information stored in the node itself.
36
37 <strong>Prerequisites</strong>
38 - PHP 5.2.13 (this is the lowest PHP release _tested_ with)
39
40 <strong>License</strong>
41 [GNU GPLv3](http://www.gnu.org/licenses/gpl.html)
42
43 <strong>Documentation</strong>
44 Rbppavl documentation is available in the *Rbppavl_doc* directory.
45 Documentation is generated by [docBlox](http://www.docblox-project.org/).
46
47 <strong>Acknowledgments</strong>
48 Large parts of Rbppavl implementation are taken from Ben Pfaff's [GNU libavl](http://adtinfo.org/).
49
50 # Basic usage example #
51
52 1) Include Rbppavl
53
54 require_once 'Rbppavl/Rbppavl.php';
55
56 2) Define your data object and the callback interface to be used by Rbppavl
57
58 class TestObject {
59 public $q;
60 }
61
62 class TestCallback implements RbppavlCbInterface {
63
64 public function compare($a, $b) {
65 return ($a->q == $b->q) ? 0 : (($a->q < $b->q) ? -1 : 1);
66 }
67
68 public function dump($a) {
69 return $a->q;
70 }
71
72 public function diagnosticMessage($severity, $id, $text, $params, $qText,$className = null) {
73 return null;
74 }
75
76 public function errorHandler($id, $text, $params, $qText, $className = null) {
77 return null;
78 }
79 }
80
81 3) Create a tree
82
83 $tree = new RbppavlTree('TestCallback');
84
85 4) Insert some data objects
86
87 $seq = array(12, 7, 36, 4, 1, 28, 3);
88 foreach ($seq as $value) {
89 $data = new TestObject;
90 $data->q = $value;
91 $t = $tree->insert($data);
92 }
93
94 5) Perform inorder traversal, printing each value
95
96 $trav = new RbppavlTraverser($tree);
97 $r = $trav->first();
98 while ($r != NULL) {
99 print($r->q . '<br/>');
100 $r = $trav->next();
101 }
102
103 # More examples #
104
105 The source code in the files listed below introduce more usage examples:
106
107 * <strong>simple_test.php</strong> generates a few random integers, inserts them in a standard AVL tree,
108 validates the tree, performs an inorder traversal, then deletes the tree and its content.
109
110 * <strong>full_test.php</strong> demonstrate more complex test cases:
111 - _movie_ - Shows in detail the tree balancing operations while
112 inserting and deleting a limited set of nodes from a canonical AVL tree.
113 - _forest_ - Generates a large number of trees of increasing imbalance, with
114 random node values, to get summary statistics on height and rotations.
115 - _burp_ - Fill memory with random value node insertions, up to the threshold
116 defined by memoryThreshold, then randomly deletes all the nodes.
117 - _lorem ipsum_ - Always repeats operations on the same set of data, the "Lorem ipsum"
118 standard. Showcase for using strings instead of integers.
119 - _mirabilis res_ - Same as "Lorem ipsum", with latinized (?) diagnostic.
120 Showcase for localization of diagnostic messages.
121
Something went wrong with that request. Please try again.