From f9151159b80fba15d3de731892d4b52196439fbc Mon Sep 17 00:00:00 2001 From: "Christopher R. Hertel" Date: Tue, 14 Oct 1997 19:32:30 +0000 Subject: Added a very small piece of documentation to describe the binary tree modules. (This used to be commit 781be1daac75092666c1753f21871f2923a6f775) --- source3/ubiqx/BinaryTrees.readme | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+) create mode 100644 source3/ubiqx/BinaryTrees.readme (limited to 'source3') diff --git a/source3/ubiqx/BinaryTrees.readme b/source3/ubiqx/BinaryTrees.readme new file mode 100644 index 0000000000..ec99a43d17 --- /dev/null +++ b/source3/ubiqx/BinaryTrees.readme @@ -0,0 +1,24 @@ +Short: Binary AVL & Splay trees non-recursive. +Uploader: crh@ubiqx.mn.org (Christopher R. Hertel) +Author: crh@ubiqx.mn.org (Christopher R. Hertel) +Type: dev/c +Version: 2.4. + +Written in C using OOP techniques, these modules provide three forms of +binary tree: Simple (unbalanced) AVL (height-balanced), and Splay. AVL +trees are re-balanced after every insertion or deletion. For each node in +the tree, the difference in height between the left and right subtree is +at most 1. Splay trees use a different approach. Each time a node is +accessed (inserted, deleted, or directly found via a search), the node is +bubbled to the top of the tree. This has the effect of making the tree +'bushier' and placing the most frequently accessed nodes nearer to the +top. + +The functions are non-recursive to limit stack space usage, and can also +be made into a run-time library. The type of tree used is determined by +which header file is included with your program. No other code changes +are necessary. + +Pretty darn fast, too, IMHO. + +Chris Hertel -- cgit