Please enable JavaScript.
Coggle requires JavaScript to display documents.
M8 (There are four type of rotations, Computer scientists have expended a…
M8
-
Computer scientists have expended a lot of effort in trying to find a structure
that preserves the good properties of the classical binary search tree—principally,
the logarithmic efficiency of the dictionary operations and having the set’s elements
sorted—but avoids its worst-case degeneracy. They have come up with two
approaches.
The first approach
An unbalanced
binary search tree is transformed into a balanced one. Because of this, such
trees are called self-balancing
An AVL tree requires the difference between
the heights of the left and right subtrees of every node never exceed 1.
An AVL tree requires the difference between
the heights of the left and right subtrees of every node never exceed 1.
If an insertion or deletion of a new node
creates a tree with a violated balance requirement, the tree is restructured
by one of a family of special transformations called rotations that restore the
balance required.
The second approach
Allow more than
one element in a node of a search tree. Specific cases of such trees are 2-3
trees, 2-3-4 trees, and more general and important B-trees
They differ in the
number of elements admissible in a single node of a search tree, but all are
perfectly balanced
An AVL tree is a binary search tree in which the balance factor of
every node, which is defined as the difference between the heights of the node’s
left and right subtrees, is either 0 or +1 or −1. (The height of the empty tree is
defined as−1. Of course, the balance factor can also be computed as the difference
between the numbers of levels rather than the height difference of the node’s left
and right subtrees.)
If an insertion of a new node makes an AVL tree unbalanced, we transform
the tree by a rotation.
A rotation in an AVL tree is a local transformation of its
subtree rooted at a node whose balance has become either +2 or −2. If there are
several such nodes, we rotate the tree rooted at the unbalanced node that is the
closest to the newly inserted leaf
A rotation in an AVL tree is a local transformation of its
subtree rooted at a node whose balance has become either +2 or −2. If there are
several such nodes, we rotate the tree rooted at the unbalanced node that is the
closest to the newly inserted leaf
How efficient are AVL trees? As with any search tree, the critical characteristic
is the tree’s height.
the height h of any AVL tree with n nodes
satisfies the inequalities
floor(log2 n) ≤h<1.4405 log2(n + 2) − 1.3277.
Thus, searching in an AVL tree requires,
on average, almost the same number of comparisons as searching in a sorted array
by binary search
The operation of key deletion in an AVL tree is considerably more difficult
than insertion, but fortunately it turns out to be in the same efficiency class as
insertion, i.e., logarithmic.
These impressive efficiency characteristics come at a price
The drawbacks of AVL trees are frequent rotations and the need to maintain balances
for its nodes. These drawbacks have prevented AVL trees from becoming
the standard structure for implementing dictionaries. At the same time, their underlying
idea—that of rebalancing a binary search tree via rotations—has proved
to be very fruitful and has led to discoveries of other interesting variations of the
classical binary search tree.
