1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

A pair questions for Math/CS buffs

Discussion in 'Members' Lounge' started by lsvtec, Nov 13, 2003.

  1. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR
    1. I need an algorithm that given a sorted array builds a binary search tree with height O(lg n ) and has a run time of O( n ).

    2. I need an algorithm that given 2 BST's with height n1 and n2 respectively, will concatinate them into 1 tree with height O( lg( n1 + n2 ) ) and has a run-time of O( n1 + n2 ).

    Anybody?
     
  2. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR
    For problem 1, a recursive method that splits the array into 3 parts: the middle element, everything bigger than that, and everything smaller than that. It inserts the middle element into the tree and calls itself on the bigger and smaller portions. Great, except that insertion into a BST is O( lg n ) meaning this method is O( n lg n ) . Not fast enough, how do I get around the extra cost of insertion?
     
  3. pissedoffsol

    pissedoffsol RETIRED

    Messages:
    49,693
    Likes Received:
    54
    Joined:
    Sep 28, 2002
    Location:
    Retirement Home
    holy fuck dude....

    i don't know what any of that means except recursive and concactinate!!!!

    :ph34r: :ph34r: :blink: :blink: :blink:
     
  4. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR
    It's from my algorithms class. I can't wait to be done with this shit.
     
  5. pissedoffsol

    pissedoffsol RETIRED

    Messages:
    49,693
    Likes Received:
    54
    Joined:
    Sep 28, 2002
    Location:
    Retirement Home
    if it was php, i'd use the concat() function. lol
     
  6. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR
    concat would have the same problem as I mentioned early, not fast enough. I would be willing to bet that concat doesn't work on a binary search tree. :)
     
  7. djyox

    djyox Senior Member

    Messages:
    982
    Likes Received:
    0
    Joined:
    Sep 30, 2002
    Location:
    Twin Cities, Minnesota
    hmmm, makes me feel like I need to go to school just to even read that what you said.
     
  8. pissedoffsol

    pissedoffsol RETIRED

    Messages:
    49,693
    Likes Received:
    54
    Joined:
    Sep 28, 2002
    Location:
    Retirement Home
    i don't even know what binary search tree is.

    here's an algorthim for ya:

    while($lsvtec everUsesThisInRealLife())
    {
    return false;
    }
     
  9. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR

    :werd: unfortunately that line of logic never seems to persuade the Dean. :)

    On a lighter note I think I finally worked out a solution to each of these.

    In case anyone actually cares:
    #1 goes something like this:
    BuildBST( array, i, j ) array is the array, i is the front index of the portion we are looking at and j is the back
    if( j == i )
    then return reference to item at index i
    else if( j - i == 1 )
    then right child of element i <- reference to element j
    return a reference to element i
    else mid <- floor( (i + j) / 2 )
    left child of element mid <- BuildBST( array, i , mid - 1 )
    right child of element mid <- BuildBST( array, mid +1, j )
    return reference to element mid

    #2 is even easier once #1 is worked out:
    MergeBST( tree1, tree2)
    Build a sorted array from these trees like this:
    while( tree1 has more elements and tree2 has more elements )
    do
    min1 <- minimum( tree1 )
    min2 <- minimum( tree2 )
    if( min1 < min2 )
    then append min1 to array and remove min1 from tree1
    else append min2 to array and remove min2 from tree2
    while( tree1 has more elements )
    do append them to the array in non-decreasing order remove each element after appending
    while( tree2 has more elements )
    do append them to the array in non-decreasing order remove each element after appending

    Use the method described in #1 to build a tree from this array.

    voila, both run in linear time and I am fucking tired. Wish me luck on my test tomorrow.
     
  10. pissedoffsol

    pissedoffsol RETIRED

    Messages:
    49,693
    Likes Received:
    54
    Joined:
    Sep 28, 2002
    Location:
    Retirement Home
    i think i speak for everyone here..... when isay

    riiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiigggggggghhhhhhhhttttttttttt
     
  11. B16

    B16 Super Moderator VIP

    Messages:
    11,539
    Likes Received:
    534
    Joined:
    Sep 30, 2002
    Location:
    yay area, CA
    man, been a long time since i saw that stuff, that was in my data structures class. do you have to do an AVL tree too? balanced, those suck, lol, especially deleting from them.
     
  12. jiahanhao

    jiahanhao Senior Member

    Messages:
    647
    Likes Received:
    0
    Joined:
    Sep 20, 2003
    Location:
    Southern Cali...
    Your psuedo-code looks pretty good, I just did the same type of assignment a few quarters ago... just wait till you get to ternary search trees.. and the square list (I dunno if that's what it's called)... gawd they are bitches (most spell-check programs use TST's).
     
  13. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR
    Yeah we have covered AVL trees, deleting from them is the only difficult part but all it really is is pointer manipulation.

    No ternary search trees yet but have no fear, they wouldn't let us off that easy. :)
     
  14. Bob Vila

    Bob Vila ɐןıʌ qoq Admin VIP

    Messages:
    4,670
    Likes Received:
    57
    Joined:
    Jul 4, 2003
    Location:
    Bristol, Ct.
    i knew I should have paid attention in class...

    oh well ;)
     
  15. blink1_8_2dude

    blink1_8_2dude Senior Member

    Messages:
    192
    Likes Received:
    0
    Joined:
    Mar 19, 2003
    damn dude im still on logarythms in college algebra
     
  16. liquid00meth

    liquid00meth Senior Member

    Messages:
    3,201
    Likes Received:
    0
    Joined:
    Nov 26, 2002
    Location:
    Laconia, NH
    I just did a BST class assignment. Our creation method is still n lg n I think though.
     
  17. dcsports413

    dcsports413 Senior Member

    Messages:
    276
    Likes Received:
    0
    Joined:
    May 4, 2003

    Do you mean 'logarithms'? You might what to go back and take a spelling class. :)
     
  18. lsvtec

    lsvtec GNU/Linux Evangelist

    Messages:
    5,453
    Likes Received:
    4
    Joined:
    Sep 30, 2002
    Location:
    Greater Portland, OR

    n lg n is the best you can do when creating a BST from an unsorted array. This is because Insertion is n lg n. The only way to make building faster is to sort your input and write a build method that takes advantage of that.
     
  19. Tonyd0821

    Tonyd0821 Banned

    Messages:
    5,088
    Likes Received:
    0
    Joined:
    Feb 26, 2003

    so what can you do with all that shit you just did?

    whats the real life application?
    :blink:
     
  20. B16

    B16 Super Moderator VIP

    Messages:
    11,539
    Likes Received:
    534
    Joined:
    Sep 30, 2002
    Location:
    yay area, CA

    sorting a list and searching it, quickly
     
Verification:
Draft saved Draft deleted

Share This Page