avltree.txt

主要进行大规模的电路综合

                             AVL Tree Algorithm

An AVL Tree is a form of binary tree, however unlike a binary tree, the
worst case scenario for a search is O(log n). The AVL data structure
achieves this property by placing restrictions on the difference in height
between the sub-trees of a given node, and re-balancing the tree if it
violates these restrictions.

  ------------------------------------------------------------------------

AVL Tree Balance Requirements

The complexity of an AVL Tree comes from the balance requirements it
enforces on each node. A node is only allowed to possess one of three
possible states (or balance factors):

Left-High (balance factor -1)
The left-sub tree is one level taller than the right-sub tree

Balanced (balance factor 0)
The left and right sub-trees are both the same heights

Right-High (balance factor +1)
The right sub-tree is one level taller than the left-sub tree.

If the balance of a node becomes -2 (it was left high and a level was lost
from the left sub-tree) or +2 (it was right high and a level was lost from
the right sub-tree) it will require re-balancing. This is achieved by
performing a rotation about this node (see the section below on rotations).

  ------------------------------------------------------------------------

Inserting in an AVL Tree

Nodes are initially inserted into AVL Trees in the same manner as an
ordinary binary search tree (that is, they are always inserted as leaf
nodes). After insertion, however, the insertion algorithm for an AVL Tree
travels back along the path it took to find the point of insertion, and
checks the balance at each node on the path. If a node is found that is
unbalanced (that is, it has a balance factor of either -2 or +2), then a
rotation is performed (see the section below on rotations) based on the
inserted nodes position relative to the node being examined (the unbalanced
node).

NB. There will only ever be at most one rotation required after an insert
operation.

  ------------------------------------------------------------------------

Deleting from an AVL Tree

The deletion algorithm for AVL Trees is a little more complex, as there are
several extra steps involved in the deletion of a node. If the node is not
a leaf node (that is, is has at least one child), then the node must be
swapped with either it's in-order successor or predecessor (based on
availability). Once the node has been swapped we can delete it (and have
its parent pick up any children it may have - bear in mind that it will
only ever have at most one child). If a deletion node was originally a leaf
node, then it can simply be removed.

Now, as with the insertion algorithm, we traverse back up the path to the
root node, checking the balance of all nodes along the path. If we
encounter an unbalanced node we perform an appropriate rotation to balance
the node (see the section below on rotations).

NB. Unlike the insertion algorithm, more than one rotation may be required
after a delete operation, so in some cases we will have to continue back up
the tree after a rotation.

  ------------------------------------------------------------------------

AVL Tree Rotations

As mentioned previously, an AVL Tree and the nodes it contains must meet
strict balance requirements to maintain is O(log n) search capabilities.
These balance restrictions are maintained using various rotation functions.
Below is a diagrammatic overview of the four possible rotations that can be
performed on an unbalanced AVL Tree, illustrating the before and after
states of an AVL Tree requiring the rotation.

                                LL Rotation

                    [An LL Rotation - before and after]

                                RR Rotation

                    [An RR Rotation - before and after]

                                LR Rotation

                    [An LR Rotation - before and after]

                                RL Rotation

                    [An RL Rotation - before and after]