| T.R | Title | User | Personal
Name | Date | Lines |
|---|
| 925.1 | | CLT::GILBERT | speciation sometimes converges | Fri Sep 02 1988 16:50 | 5 |
| If you're writing code for VMS, have a look at the VAX RTL routines
(LIB$INSERT_TREE, and a few others). The algorithm to *maintain*
a balanced binary tree is rather tedious. I have an elegant algorithm
to *balance* an unbalanced binary tree that's basically O(N). There
are also 2-3 trees, which are as difficult to keep balanced.
|
| 925.2 | Keep a balance count | AKQJ10::YARBROUGH | I prefer Pi | Fri Sep 02 1988 17:25 | 18 |
| > Any suggestions on the best approach to maintain balance on a binary
> tree while adding nodes, without having to transverse the entire
> tree?
> A search of the tree is necessary to preclude any redundancy.
If the tree is currently balanced, it costs only O(log(n)) to check whether
the key of interest is already there, and also O(Log(n)) to insert and
rebalance; it's not necessary to traverse the whole tree to rebalance if
you keep some information in each node about how deep it is. The
LIB$...TREE routines allow you to insert only if no key match, and looks
for the proper key position only once, so the process is very quick.
If you are interested in the balancing algorithm used, it's described in
G. H. Gonnet's "Handbook of Algorithms and Data Structures", or in Knuth
"Art of Computer Programing", Vol. I.
Lynn
|
| 925.3 | Help in trimming the tree too? | STAR::CAPPELLOF | Carl J. Appellof | Sat Sep 03 1988 15:26 | 2 |
| How about any algorithms to re-balance a binary tree after REMOVEing
a node? There doesn't seem to be a LIB$DELETE_TREE!
|
| 925.4 | | CLT::GILBERT | speciation sometimes converges | Sun Sep 04 1988 19:44 | 2 |
| There is some occasional discussion of this in the VAX/VMS RTL notes
conference. See CLT::RTL, note 43.21, in particular.
|
| 925.5 | | HPSTEK::XIA | | Mon Sep 05 1988 23:08 | 4 |
| re .3
It is much easier to balance a tree after inserting a node than
to balance a tree after deleting a node.
Eugene
|
| 925.6 | | CTCADM::ROTH | If you plant ice you'll harvest wind | Tue Sep 06 1988 10:52 | 22 |
| The LIB$INSERT_TREE is basically the insertion part of the standard
AVL tree algorithm from Wirth's book. I don't know why they didn't
also provide the delete routine as well, since it's also in that book.
Except that inserting is used much more often in the context of that
routine.
I've coded both 2-3 and AVL trees routines as well as a few variants,
and the AVL tree routine is probably the best general nearly-balanced
tree routine. One variant of the 2-3 tree I tried (SBB trees) was
acutally *slower* than the basic 2-3 tree routine, and hardly justified
the extra coding effort recomended by the authors of the paper on it.
If I recall, deleting is slightly more work - the code is a bit
more tricky to do.
On the other hand, 'occasionally' balancing a tree would amortize
the cost over much tree activity and may be a much better approach
in some cases.
The little book by Gonnet is great to have around by the way.
- Jim
|