# A pair questions for Math/CS buffs

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

1. ### lsvtecGNU/Linux Evangelist

Messages:
5,453
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. ### lsvtecGNU/Linux Evangelist

Messages:
5,453
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. ### pissedoffsolRETIRED

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

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

4. ### lsvtecGNU/Linux Evangelist

Messages:
5,453
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. ### pissedoffsolRETIRED

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

6. ### lsvtecGNU/Linux Evangelist

Messages:
5,453
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. ### djyoxSenior Member

Messages:
982
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. ### pissedoffsolRETIRED

Messages:
49,693
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. ### lsvtecGNU/Linux Evangelist

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

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. ### pissedoffsolRETIRED

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

riiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiigggggggghhhhhhhhttttttttttt

11. ### B16Super ModeratorVIP

Messages:
11,589
556
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. ### jiahanhaoSenior Member

Messages:
647
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. ### lsvtecGNU/Linux Evangelist

Messages:
5,453
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.

Messages:
4,672
60
Joined:
Jul 4, 2003
Location:
Bristol, Ct.
i knew I should have paid attention in class...

oh well

Messages:
192
0
Joined:
Mar 19, 2003
damn dude im still on logarythms in college algebra

16. ### liquid00methSenior Member

Messages:
3,201
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. ### dcsports413Senior Member

Messages:
276
0
Joined:
May 4, 2003

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

18. ### lsvtecGNU/Linux Evangelist

Messages:
5,453
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. ### Tonyd0821Banned

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

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

whats the real life application?

Messages:
11,589