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

Design a binary search tree, Binary Search Tree usage: Write a progra... Binary Search Tree usage: Write a program to compare the time taken for a search in a skewed tree, a balanced tree, and a random tree. Specically, your program should do the

Program, What is a first-in-first-out data structure ? Write algorithms to... What is a first-in-first-out data structure ? Write algorithms to perform the following operations on it – create, insertion, deletion, for testing overflow and empty conditions.

Explain state space tree, Explain State Space Tree If it is convenient ... Explain State Space Tree If it is convenient to execute backtracking by constructing a tree of choices being made, the tree is known as a state space tree. Its root indicates a

Threads in main method, Create main method or a test class that creates 2 E... Create main method or a test class that creates 2 Element objects that are neighbours of each other, the first element temperature set at 100, the 2nd at 0 and use an appropriate h

Frequency count, what is frequency count with examble what is frequency count with examble

What are the languages which support assertions, What are the languages whi... What are the languages which support assertions Languages which support assertions often provide different levels of support. For instance, Java has an assert statement which t

Enumerate about the carrier set members, Enumerate about the carrier set me... Enumerate about the carrier set members Ruby is written in C, so carrier set members (which is, individual symbols) are implemented as fixed-size arrays of characters (which is

Merge sorting, ESO207: Programming Assignment 1 Due on 6 Sept, 2015. To be ... ESO207: Programming Assignment 1 Due on 6 Sept, 2015. To be submitted online. Problem In this assignment you are required to implement k-way Merge Sort algorithm. In this version p

Sequential search of a list is preferred over binary search, What are the c... What are the conditions under which sequential search of a list is preferred over binary search? Sequential Search is a preferred over binary search when the list is unordered

Surrounding of sub division method, Surrounding of sub division method ... Surrounding of sub division method A polygon surrounds a viewport if it completely encloses or covers the viewport. This happens if none of its sides cuts any edge of the viewp