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
Program segment for the deletion of any element from the queue delmq(i)  /* Delete any element from queue i */ { int i,x; if ( front[i] == rear[i]) printf("Queue is

Data Structure and Algorithm 1. Explain linked list and its types. How do you represent linked list in memory? 2. List and elucidate the types of binary tree. 3. Descr

This is a k-ary position tree wherein all levels are filled from left to right. There are a number of specialized trees. They are binary trees, AVL-trees, binary search trees, 2

CMY Model  The cyan, magenta, yellow (CMY) colour model is a subtractive model based on the colour absorption properties of paints and inks. As such it has become the standard

Define the term counting - Pseudocode Counting in 1s is quite simple; use of statement count = count + 1 would enable counting to be done (for example in controlling a repeat

Explain Floyd's algorithm It is convenient to record the lengths of shortest paths in an n by n matrix D known as the  distance matrix: the element d ij   in the i th   row an


for (i = 0; i sequence of statements } Here, the loop executes n times. Thus, the sequence of statements also executes n times. Since we suppose the time complexity of th

Determine about the unreachable code assertion An unreachable code assertion is an assertion that is placed at a point in a program that shouldn't be executed under any circum

Any Binary search tree has to contain following properties to be called as a red- black tree. 1. Each node of a tree must be either red or black. 2. The root node is always b