ipc.c: Adding Andrews become_root code to the main branch.
[samba.git] / source3 / ubiqx / BinaryTrees.readme
1 Short: Binary AVL & Splay trees non-recursive.
2 Uploader: crh@ubiqx.mn.org (Christopher R. Hertel)
3 Author: crh@ubiqx.mn.org (Christopher R. Hertel)
4 Type: dev/c
5 Version: 2.4.
6
7 Written in C using OOP techniques, these modules provide three forms of
8 binary tree: Simple (unbalanced) AVL (height-balanced), and Splay.  AVL
9 trees are re-balanced after every insertion or deletion.  For each node in
10 the tree, the difference in height between the left and right subtree is
11 at most 1.  Splay trees use a different approach.  Each time a node is
12 accessed (inserted, deleted, or directly found via a search), the node is
13 bubbled to the top of the tree.  This has the effect of making the tree
14 'bushier' and placing the most frequently accessed nodes nearer to the
15 top.
16
17 The functions are non-recursive to limit stack space usage, and can also
18 be made into a run-time library.  The type of tree used is determined by
19 which header file is included with your program.  No other code changes
20 are necessary.
21
22 Pretty darn fast, too, IMHO. 
23
24 Chris Hertel