Please enable JavaScript.
Coggle requires JavaScript to display documents.
Balanced Search Trees, Is the mirror image of the
single R-rotation,…
Balanced Search Trees
Compared to the straightforward implementation of a dictionary by an array We gain in the time efficiency of searching, insertion, and deletion, which are all in Θ(log n) in average cases
In the worst case, these operations are in Θ(n) because the tree can degenerate into a severely unbalanced one with its height equal to n − 1.
An AVL tree requires the difference between
the heights of the left and right subtrees of every node never exceed 1.
An unbalanced binary search tree is transformed into a balanced one. Because of this, such trees are called self-balancing.
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.
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.
Right rotation(R-rotation):
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( L-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.
Double left-right rotation (LRrotation):
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.
-
AVL trees efficiency As with any search tree, the critical characteristic is the tree’s height.
-
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
AVL limitations:
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.
The other approach allows more than
one element in a node of a search tree(B-trees, most importantly)
-
-
Not only should they guarantee that a resulting tree is balanced, but they should also preserve the basic requirements of a binary search tree