Rotations in binary tree, Data Structure & Algorithms

How can you rotate a Binary Tree? Explain right and left rotations by taking an example.

 If after we have inserted a node in a Binary search tree, the balancing factor (height of left subtree - height of right subtree) of each node remains 0, 1 and -1 then there is no need of modification or alteration of original tree. If balancing factor of any node is either +2 or -2, the tree becomes unbalanced. It can be balanced by using left rotation or right rotation or a combination of both the rotations.

For example

1.  In the tree drawn below, after inserting node 70 , the balance factor of tree  at the root node (2) so the tree is rotated left to have a height balanced tree shown by (a) to (b):

1900_Rotations_in_Binary_Tree.png

 

2.  In the tree drawn below, after inserting 10 the balance factor of tree at root node is +2 so the tree is rotated right to have height balanced tree as shown by(a) to (b) below:997_Rotations_in_Binary_Tree_assignment_help.png

 

Posted Date: 7/10/2012 1:11:36 AM | Location : United States







Related Discussions:- Rotations in binary tree, Assignment Help, Ask Question on Rotations in binary tree, Get Answer, Expert's Help, Rotations in binary tree Discussions

Write discussion on Rotations in binary tree
Your posts are moderated
Related Questions

The objective analysis of an algorithm is to determine its efficiency. Efficiency is based on the resources which are used by the algorithm. For instance, CPU utilization (Ti


Hubs - In reality a multiport repeater - Connects stations in a physical star topology - As well may create multiple levels of hierarchy to remove length limitation of 10

what are the disadvantages of sparse matrix?

In this unit, we described about the data structure Queue. It had two ends. One is front from where the elements can be removed and the other is rear where the elements can be inse

Exact analysis of insertion sort: Let us assume the following pseudocode to analyse the exact runtime complexity of insertion sort. T j   is the time taken to execute the s

: Write an algorithm to evaluate a postfix expression. Execute your algorithm using the following postfix expression as your input: a b + c d +*f ­ .

The fundamental element of linked list is a "record" structure of at least two fields. The object which holds the data & refers to the next element into the list is called a node .

B Tree Unlike a binary-tree, every node of a B-tree may have a variable number of keys and children. The keys are stored in non-decreasing order. Every key has an associated ch