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)

image

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:

image

• 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:

image

• 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:

image

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:

image

• 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.

image

image

image

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

image

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

image

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

image

Comments

Popular posts from this blog

Data Structure Visualization:Introduction and Value of Data Structure Rendering

Binary Space Partitioning Trees:BSP Tree as a Hierarchy of Regions.

Drawing Trees:HV-Layout