# hash & balanced trees

Charles Victor Bancroft (bancroft@america.net)
Thu, 3 Jul 1997 13:43:52 -0400 (EDT)

- Messages sorted by:[ date ][ thread ][ subject ][ author ]

    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.

    . . .