D4Ly
asked on
bst restructure to another bst
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.
ASKER
I always miss something somewhere. yes, its is to another BINARY tree. ;p Thanks!
ASKER
so, any ideas?
I studied that a while ago (this why I remember about two binary trees).
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/~travis/ipl.pdf"
I will read it tomorow. Try to read it your self and see if it helps.
Do you have any available material?
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/~travis/ipl.pdf"
I will read it tomorow. Try to read it your self and see if it helps.
Do you have any available material?
ASKER
Okay, so here's the answer [the teacher wanted]...the answer doesn't fullfil the question as I can tell however:
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!!!!
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!!!!
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
ASKER
champion!
Thanks very much. Sorry for the late reponse. Your article helped visualize things somewhat in terms of what I had to look for, so I got partial credit :)
Thanks very much. Sorry for the late reponse. Your article helped visualize things somewhat in terms of what I had to look for, so I got partial credit :)
:-)
If so, then your example with B is wrong.