A pair questions for Math/CS buffs

[lsvtec]

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?

 

[lsvtec]

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?

 

[posol]

holy fuck dude....

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

 

[lsvtec]

It's from my algorithms class. I can't wait to be done with this shit.

 

[posol]

if it was php, i'd use the concat() function. lol

 

[lsvtec]

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.

 

[djyox]

hmmm, makes me feel like I need to go to school just to even read that what you said.

 

[posol]

i don't even know what binary search tree is.

here's an algorthim for ya:

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

 

[lsvtec]

Originally posted by pissedoffsol@Nov 13 2003, 12:03 AM
i don't even know what binary search tree is.

here's an algorthim for ya:

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

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.

 

[posol]

i think i speak for everyone here..... when isay

riiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiiigggggggghhhhhhhhttttttttttt

 

[B16]

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.

 

[jiahanhao]

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).

 

[lsvtec]

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.

 

[Bob Vila]

i knew I should have paid attention in class...

oh well

 

[blink1_8_2dude]

damn dude im still on logarythms in college algebra

 

[liquid00meth]

I just did a BST class assignment. Our creation method is still n lg n I think though.

 

[dcsports413]

Originally posted by blink1_8_2dude@Nov 13 2003, 01:11 PM
damn dude im still on logarythms in college algebra

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

 

[lsvtec]

Originally posted by liquid00meth@Nov 13 2003, 12:13 PM
I just did a BST class assignment. Our creation method is still n lg n I think though.

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.

 

[Tonyd0821]

Originally posted by lsvtec+Nov 13 2003, 01:34 PM-->

liquid00meth

@Nov 13 2003, 12:13 PM
I just did a BST class assignment. Our creation method is still n lg n I think though.

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.

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

whats the real life application?

 

[B16]

Originally posted by Tonyd0821+Nov 13 2003, 10:49 AM-->

Originally posted by lsvtec@Nov 13 2003, 01:34 PM
liquid00meth

@Nov 13 2003, 12:13 PM
I just did a BST class assignment.  Our creation method is still n lg n I think though.

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.

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

whats the real life application?

sorting a list and searching it, quickly