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

 

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:

 

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

Ask an Expert

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

Write your message here..

Related Questions

Write down the algorithm of quick sort, Write down the algorithm of quick s... Write down the algorithm of quick sort. An algorithm for quick sort: void quicksort ( int a[ ], int lower, int upper ) {  int i ;  if ( upper > lower ) {   i = split ( a,

Comp. sci algorithms, 1. develop an algorithm which reads two decimal numbe... 1. develop an algorithm which reads two decimal numbers x and y and determines and prints out wether x>y or y>x. the input values, x and y, are whole number > or equal to 0, which

Define wire-frame model, Define Wire-frame Model This skeletal view is ... Define Wire-frame Model This skeletal view is called a Wire-frame Model. Although not a realistic representation  of the object, it is still very useful in the early stages of

Algorithm for sorting a deck of cards, What is wrong with the following alg... What is wrong with the following algorithm for sorting a deck of cards (considering the basic properties of algorithms)? I. Put the cards together into a pile II. For each ca

Asymptotic notation, Asymptotic notation Let us describe a few function... Asymptotic notation Let us describe a few functions in terms of above asymptotic notation. Example: f(n) = 3n 3 + 2n 2 + 4n + 3 = 3n 3 + 2n 2 + O (n), as 4n + 3 is of

Determine the class invariants- ruby, Determine the class invariants- Ruby ... Determine the class invariants- Ruby Ruby has many predefined exceptions classes (like ArgumentError) and new ones can be created easily by sub-classing StandardError, so it's

Briefly explain the prim''s algorithm, Question 1 Describe the following- ... Question 1 Describe the following- Well known Sorting Algorithms Divide and Conquer Techniques Question 2 Describe in your own words the different asymptotic func

Stack, how we will make projects on stack in c? how we will make projects on stack in c?

The two famous methods for traversing, The two famous methods for traversin... The two famous methods for traversing are:- a) Depth first traversal b) Breadth first

Algorithms, characteristics of a good algorithm characteristics of a good algorithm