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
One of the best known methods for external sorting on tapes is the polyphase sort. Principle: The basic strategy of this sort is to distribute ordered initial runs of predetermi

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

Arrays are simple, however reliable to employ in more condition than you can count. Arrays are utilized in those problems while the number of items to be solved out is fixed. They

Arrays :- To execute a stack we need a variable called top, that holds the index of the top element of stack and an array to hold the part of the stack.

Q. Describe the term hashing. Explain any two usually used hash functions. Explain one method of collision resolution.

As part of an experiment, a school measured heights (in metres) of all its 500 students. Write an algorithm, using a flowchart that inputs the heights of all 500 students and ou

Determine the Disjoint of division method A polygon is disjoint from the viewport if the x- and y-extents of the polygon do not overlap the viewport anywhere. In this case; reg

I am looking for assignment help on the topic Data Structures. It would be great if anyone help me.

algorithm for multiplication of two sparse matrices using linked lists..

for i=1 to n if a[i}>7 for j=2 to n a[j]=a{j}+j for n=2 to n a[k]=a[j]+i else if a[1]>4 && a[1] for 2 to a[1] a[j]= a{j]+5 else for 2to n a[j]=a[j]+i ..