MOO-cows Mailing List Archive
[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]
Re: hash & balanced trees
The definition of a minimal set of verbs for the $dictionary is a task
at one level of abstraction. So as the moo version of such an interface
begins to gel, it is important not to prejudice it towards and lower
level implementation approach. Having said that, the shameless advocacy
of a particular algorithm follows . . .
> I'm staring at all those baroque search techniques at the back of the
> data structures book and my head hurts. Thinking is hard. Anybody
> have any ideas?
Perhaps the most interesting tree algorithm that someone else has
already coded . . . originally developed a long time ago in a place far
away . . . published by the master of algorithms . . . translated into
several contexts including an integration w/ prolog . . . eeek
Tom Howland, hacked this very much to work with Prolog. He worked
from some files gotten from Vic Bancroft of KnowledgeWare, who got it
presumably from Tony Bolmarcich (TONYB at YKTVMH) and Tim Bell (BELLTG
at WINVMB) who I suspect work for IBM and translated it from a PL/I
source. Presumably they got it from Niklaus Wirth, "Algorithms and Data
Structures", Prentice-Hall, 1986, but AVL trees were originally
described in: G.M. Adelson-Velskii and E.M. Landis, Doklady Akademia
Nauk, SSSR, 146(1962), 263-266; English translation in Soviet Math, 3,
1259-1263.
[Note: borrowed explaination follows]
An AVL tree is an ordered tree with the following characteristics.
- each node (subtree) points to two node (it is a binary tree).
- for every node, the heights of its two subtrees differ by at most 1
(this is the balance constraint).
During node insertion and deletion, the balance constraint may
temporarily be violated. A tree is rebalanced by a process called
rotation. There are two categories of rotation: single and double.
Here is an example of a single rotation.
Before Insertion After Insertion After Rotation
| | |
5 5 3
/ \ / \ / \
3 6 3 6 2 5
/ \ / \ / / \
2 4 2 4 1 4 6
/
1
The tree was balanced before the insertion. After the insertion, the
node with value 5 is not balanced (its left subtree has a depth of 3,
while its right subtree has a depth of 1). The balance is restored by a
single rotation at that node.
Here is an example of a double rotation.
Before Insertion After Insertion After Rotation
| | |
5 5 4
/ \ / \ / \
2 6 2 6 2 5
/ \ / \ / \ \
1 4 1 4 1 3 6
/
3
The tree was balanced before the insertion. After the insertion, the
node with value 5 is not balanced (its left subtree has a depth of 3,
while its right subtree has a depth of 1). The balance is restored by a
double rotation at that node.
. . .
References:
Home |
Subject Index |
Thread Index