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

C, padovan string padovan string

Depth first search, DEPTH FIRST SEARCH (DFS) The approach adopted into ... DEPTH FIRST SEARCH (DFS) The approach adopted into depth first search is to search deeper whenever possible. This algorithm frequently searches deeper through visiting unvisite

Explain the different types of traversal on binary tree, Question 1 What i... Question 1 What is a data structure? Discuss briefly on types of data structures Question 2 Explain the insertion and deletion operation of linked list in detail Qu

Explain about the structured types - built-in types, Explain about the Stru... Explain about the Structured types - Built-In Types Values of the carrier set are not atomic, consisting rather than several atomic values arranged in some way. Common illu

Asymptotic notations, types of asymptotic notations types of asymptotic notations

Hash clash, Q. What do you understand by the term by hash clash? Explain in... Q. What do you understand by the term by hash clash? Explain in detail any one method to resolve the hash collisions.

Define binary tree, Define Binary Tree  A binary tree T is explained as... Define Binary Tree  A binary tree T is explained as a finite set of nodes that is either empty or having of root and two disjoint binary trees TL, and TR known as, respectively

Construct a minimum spanning tree, Construct G for α, n, and W given as com... Construct G for α, n, and W given as command line parameters. Throw away edges that have an asymmetric relation between nodes. That is, if A is connected to B, but B is not connect

Depth of complete binary tree, What will be depth do , of complete binary t... What will be depth do , of complete binary tree of n nodes, where nodes are labelled from 1 to n with root as node and last leaf node as node n

Bayesian statistics question, Suppose that there is a Beta(2,2) prior distr... Suppose that there is a Beta(2,2) prior distribution on the probability theta that a coin will yield a "head" when spun in a specified manner. The coin is independently spun 10 tim