[Okta Webinar] Learn how to a build a cloud-first strategyRegister Now

x
  • Status: Solved
  • Priority: Medium
  • Security: Public
  • Views: 312
  • Last Modified:

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.
0
D4Ly
Asked:
D4Ly
  • 4
  • 4
1 Solution
 
aozarovCommented:
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.
0
 
D4LyAuthor Commented:
I always miss something somewhere.  yes, its is to another BINARY tree. ;p Thanks!
0
 
D4LyAuthor Commented:
so, any ideas?
0
Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

 
aozarovCommented:
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?
0
 
D4LyAuthor Commented:
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!!!!

0
 
aozarovCommented:
If you know that you can change any bst to balanced bst in O(N) steps then (assuming both trees contain the same nodes):
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.
0
 
D4LyAuthor Commented:
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 :)

0
 
aozarovCommented:
:-)
0

Featured Post

New feature and membership benefit!

New feature! Upgrade and increase expert visibility of your issues with Priority Questions.

  • 4
  • 4
Tackle projects and never again get stuck behind a technical roadblock.
Join Now