Are you sure about any transforming it to any to any other tree and not to any other "binary" tree?

If so, then your example with B is wrong.

If so, then your example with B is wrong.

Solved

Posted on 2005-04-05

This is homework. I'm simply looking for a helpful suggestion to nudge me.

I have to show that any binary search tree with n nodes can be restructured into any other n node tree in O(n) rotations.

So here's what I've done:

Tree A. (disregard the values....they are just for me to distinguish them)

1

/ \

2 3

/ \ / \

4 5 6 7

Tree B.

7

/ \

6 5

/ \ / \

4 3 2 1

These will be my test trees. I want to make A look like B (re-order the nodes properly)

So, my thought is to make A a left chain.

Note: I've put x's where some null nodes are located.

step 1. (every step is a single left rotation)

3

/ \

1 7

/ \ / \

2 6 x x

/ \

4 5

step 2.

7

/ \

3 x

/ \

1 x

/ \

2 6

/ \

4 5

step 3.

7

/ \

3 x

/ \

6 x

/ \

1 x

/ \

2 x

/ \

4 5

step 4.

7

/ \

3 x

/ \

6 x

/ \

1 x

/ \

5 x

/ \

2 x

/ \

4 x

K.

Now, I do the same thing for Tree B. All left rotations, and I end up with:

1

/ \

5 x

/ \

2 x

/ \

7 x

/ \

3 x

/ \

6 x

/ \

4 x

Now, I think I need to use the rotations in some type of reverse order of tree B's movement to a left chain to restructure A to look like B in the beginning.

Can someone offer a tip? Many thanks.

I have to show that any binary search tree with n nodes can be restructured into any other n node tree in O(n) rotations.

So here's what I've done:

Tree A. (disregard the values....they are just for me to distinguish them)

1

/ \

2 3

/ \ / \

4 5 6 7

Tree B.

7

/ \

6 5

/ \ / \

4 3 2 1

These will be my test trees. I want to make A look like B (re-order the nodes properly)

So, my thought is to make A a left chain.

Note: I've put x's where some null nodes are located.

step 1. (every step is a single left rotation)

3

/ \

1 7

/ \ / \

2 6 x x

/ \

4 5

step 2.

7

/ \

3 x

/ \

1 x

/ \

2 6

/ \

4 5

step 3.

7

/ \

3 x

/ \

6 x

/ \

1 x

/ \

2 x

/ \

4 5

step 4.

7

/ \

3 x

/ \

6 x

/ \

1 x

/ \

5 x

/ \

2 x

/ \

4 x

K.

Now, I do the same thing for Tree B. All left rotations, and I end up with:

1

/ \

5 x

/ \

2 x

/ \

7 x

/ \

3 x

/ \

6 x

/ \

4 x

Now, I think I need to use the rotations in some type of reverse order of tree B's movement to a left chain to restructure A to look like B in the beginning.

Can someone offer a tip? Many thanks.

8 Comments

If so, then your example with B is wrong.

I tried to remember but no luck.

It was also tough to find information about it on the web.

I managed to this just now "http://www.cs.utoronto.ca

I will read it tomorow. Try to read it your self and see if it helps.

Do you have any available material?

Question:

Show that any n-node binary tree can be converted to any other n-node binary tree

with O(n) rotations.

Answer:

We need to show here that any n-node binary tree can be converted to an n-node balance tree performing O(n) restructure operations.

Proof: We start by converting the binary tree to a left chain. By that we mean that each internal node has only one left child and NULL right childs. We apply a single rotation to the bottom three internal nodes. We continue in the same way applying the single rotation to the internal nodes moving from the bottom of the tree to the root. When we reach the root and we apply the rotation that contains the root then the tree will be balanced. Observe that in the left chain we had n internal nodes and thus we are going to need n/2 left rotations to obtain the balance tree. So the number of total rotations we need to perform is bounded by O(n).

Does this answer fulfill what the question is asking? If so, can you explain how? Thanks!!!!

1. change bst A to balanced bst A -> O(N)

2. change bst B to balanced bst B (record changes) -> O(N) [so far O(2N) = O(N)] now bst A = bst B

3. apply on bst A the revese sequence of the changes applied on bst B -> O(N) [ so far O(3N) = O(N)] and now bst A becomes B.

Title | # Comments | Views | Activity |
---|---|---|---|

PGP Decryption code using Bouncy Castle jars | 11 | 71 | |

Jave - Remove carriage return + special characters from text | 3 | 52 | |

java set up | 1 | 37 | |

Unable to start eclipse ? | 17 | 49 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**22** Experts available now in Live!