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
padovan string

Explain the term totalling To add up a series numbers the subsequent type of statement must be used: Total = total + number  This literally means (new) total = (old) t

Dequeue (a double ended queue) is an abstract data type alike to queue, where insertion and deletion of elements are allowed at both of the ends. Like a linear queue & a circular q

Preorder traversal of a binary tree struct NODE { struct NODE *left; int value;     /* can take any data type */ struct NODE *right; };   preorder(struct N

explain the prims''s algorithm with suitable example?

Q. Give the adjacency matrix for the graph drawn below:                                                 Ans: Adjacency matrix for the graph given to us

A queue is a particular type of collection or abstract data type in which the entities in the collection are went in order and the principal functions on the collection are the add

Sort the following array of elements using quick sort: 3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8.

Write an algorithm to add an element at the end of circular linked list.   Algorithm to Add the Element at the End of Circular Linked List. IINSENDCLL( INFO, LINK, START, A

In this part, students are allowed to implement the following simplifications in their table and data design. o Availability for the beauty therapists don't have to be considere