Please enable JavaScript.
Coggle requires JavaScript to display documents.
M9 - Algorithms and Data Structures - Coggle Diagram
M9 - Algorithms and Data Structures
6 Transform-and-Conquer
6.3 Balanced Search Trees
AVL Trees
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.
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.
the rotations are not trivial transformations, though fortunately they can be done in constant time
If there are several such nodes, we rotate the tree rooted at the unbalanced node that is the closest to the newly inserted leaf.
There are only four types of rotations
The first rotation type is called the
single right rotation, or R-rotation.
rotating the edge connecting the root and its left child in the binary tree to the right.
The symmetric
single left rotation, or L-rotation
(the mirror image of the single R-rotation)
The second rotation type is called the
double left-right rotation (LR rotation)
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
The
double right-left rotation (RL-rotation)
(the mirror image of the double LR-rotation)
How efficient are AVL trees?
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.
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
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.
trying to find a structure that preserves the good properties of the classical binary search tree but avoids its worst-case degeneracy. They have come up with two approaches:
The first approach is of the
instance-simplification
variety: an unbalanced binary search tree is transformed into a balanced one
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
A
red-black tree
tolerates the height of one subtree being twice as large as the other
The second approach is of the representation-change variety: 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.
First, in the transformation stage, the problem’s instance is modified to be, for one reason or another, more amenable to solution
Then, in the second or conquering stage, it is solved.
Transformation to a simpler or more convenient instance of the same problem—we call it
instance simplification
Transformation to a different representation of the same instance—we call it
representation change
Transformation to an instance of a different problem for which an algorithm is already available—we call it
problem reduction
.