[Subject Prev][Subject Next][Thread Prev][Thread Next][Subject Index][Thread Index]

**Date**: Thu, 3 Jul 1997 13:43:52 -0400 (EDT)**From**: Charles Victor Bancroft <bancroft@america.net>- Content-Type: TEXT/PLAIN; charset=US-ASCII
- In-Reply-To: <199707011628.MAA09482@fuji.ccs.neu.edu>

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. . . .

**Re: hash & balanced trees***From*: Jay Carlson <nop@nop.com>

- Prev by Subject:
**Re: hash & balanced trees** - Next by Subject:
**re:hash & balanced trees** - Prev by thread:
**Re: hash & balanced trees** - Next by thread:
**re:hash & balanced trees** - Index(es):