Balanced search trees .
Balanced search trees
Description:
The disadvantage of a binary search tree is that its height can be as large as N-1, which means that the time needed to perform insertion and deletion and many other operations can be O(N) in the worst case. Balanced binary search tree is a tree with small height, O(log N). (A binary tree with N node has height at least Θ(log N) )
Example of balanced search trees:
• Instance simplification variety AVL trees, Red-black trees
• Representation change variety: 2-3 trees, 2-3-4 trees, B-trees
AVL trees
Definition:
An AVL tree is a binary search tree in which the balance factor (defined as:
difference between the heights of the node’s left and right sub-trees) of every node is either 0 or +1 or -1.
NOTE:
The height of the empty tree is defined as -1
Basic operations like insertion, deletion, searching key, has efficiency as Θ(log n)
AVL tree rotation
If an insertion of a new node makes an AVL tree unbalanced, we transform the tree by a rotation.
Rotation Definition:
A rotation in an AVL tree is a local transformation of its sub-tree rooted at a node whose balance has become either +2 or -2.
NOTE:
If there are several such nodes, we rotate the tree rooted at the unbalanced node that is the closest to the newly inserted leaf
Types of rotations:
There are 4 types of rotations:
1. Single R – rotation
2. Single L – rotation
3. Double LR – rotation
4. Double RL – rotation
Single R – rotation
• Single right rotation
• Rotates the edge connecting the root and its left child in the binary tree
• Example:
• Here rotation is performed after a new key is inserted into the left sub-tree of the left child of a tree whose root had the balance of +1 before the insertion
Single L – rotation
• Single left rotation
• Rotates the edge connecting the root and its right child in the binary tree
• Example:
• Here rotation is performed after a new key is inserted into the right sub-tree of the right child of a tree whose root had the balance of -1 before the insertion
Double LR – rotation
• Double left-right rotation
• Combination of two rotations
1. perform left rotation of the left sub-tree of root r
2. perform right rotation of the new tree rooted at r
• It is performed after a new key is inserted into the right sub-tree of the left child of a tree whose root had the balance of +1 before the insertion
• Example:
Double RL – rotation
• Double right-left rotation
• Combination of two rotations
1. perform right rotation of the right sub-tree of root r
2. perform left rotation of the new tree rooted at r
• It is performed after a new key is inserted into the left sub-tree of the right child of a tree whose root had the balance of -1 before the insertion
• Example:
• General form: A shaded node is the last node inserted. It can be either in the left sub-tree or in the right sub-tree of the root’s grandchild.
Limitations of AVL trees
• Requires frequent rotations to maintain balances for the tree’s nodes
• Even though the deletion operation efficiency is Θ(log n), it is considerably more difficult than insertion
2-3 trees
Definition:
2-3 tree is a height balanced search tree, that has all its leaves on the same level and can
have nodes of two kinds:
• 2-node: contains a single key K and has two children- the left child serves as the root of a sub-tree whose keys are less than K, and the right child serves as the root of a sub-tree whose keys are greater than K
• 3-node: contains two ordered keys K1 and K2, (K1 < K2) and has three children.
The leftmost child serves as the root of a sub-tree with keys less than K1, middle child serves as the root of a sub-tree with keys between K1 and K2, and the rightmost child serves as the root of a sub-tree with keys greater than K2
Construction of 2-3 tree:
Question: Construct a 2-3 tree by successive insertion for the following list
9, 5, 8, 3, 2, 4, 7
Solution:
i. Insert 9 into empty tree
Comments
Post a Comment