Please enable JavaScript.
Coggle requires JavaScript to display documents.
AVL trees - Coggle Diagram
AVL trees
A balanced tree is more efficient than an unbalanced tree, in the worst case
-
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)
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
[log2 n] ≤ h < 1.4405 * log2(n + 2) − 1.3277
The inequalities immediately imply that the operations of searching and insertion
are O(log n) in the worst case. Getting an exact formula for the average height of an AVL tree constructed for random lists of keys has proved to be difficult,
but it is known from extensive experiments that it is about 1.01*log2 n + 0.1, expect when n is small
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