Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees - Coggle Diagram
Balanced Search Trees
Rotations
The first rotation type is called the single right rotation, or R-rotation. Note that this rotation is performed after a new key is inserted into the
left subtree of the left child of a tree whose root had the balance of +1 before the insertion.
The symmetric single left rotation, or L-rotation, is the mirror image of the single R-rotation. It is performed after a new key is inserted into the right subtree of the right child of a tree whose root had the balance of −1 before the insertion.
The second rotation type is called the double left-right rotation (LRrotation).It is, in fact, a combination of two rotations: we perform the L-rotation of the left subtree of root r followed by the R-rotation of the new tree rooted at r. It is performed after a new key is inserted into the right subtree of the left child of a tree whose root had the balance of +1 before the insertion.
-
Note that the rotations are not trivial transformations, though fortunately they
can be done in constant time.
Not only should they guarantee that a resulting tree is balanced, but they should also preserve the basic requirements of a binary search tree.
As you trace the algorithm’s operations, keep in mind that if there are several nodes with the ±2 balance, the rotation is done for the tree rooted at
the unbalanced node that is the closest to the newly inserted leaf.
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.
How efficient are AVL trees? As with any search tree, the critical characteristic is the tree’s height. It turns out that it is bounded both above and below by logarithmic functions.
Specifically, the height h of any AVL tree with n nodes satisfies the inequalities floor{log2 n} ≤ h < 1.4405 log2(n + 2) − 1.3277.
The inequalities immediately imply that the operations of searching and insertion are Θ(log n) in the worst case.
Formula for the average height of an AVL tree constructed for random lists of keys is known from extensive experiments that it is about 1.01log2 n + 0.1 except when n is small.
Thus, searching in an AVL tree requires,
on average, almost the same number of Thus, searching in an AVL tree requires,
on average, almost the same number of
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.