blob: ec99a43d17f48828d79d93dd32b39eaee3c6e9b9 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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
|
