Find the element that will serve as the root element of a complete binary search tree. Give the index. I just need help finding the mathematical equation for this.
Find the element that will serve as the root element of a complete binary search tree. Give the index. I just need help finding the mathematical equation for this.
Okay there are some things that are assumed here, for instance it is assumed that the data is in some particular format to begin with. Since your instructor asked for an index, I will guess that the data is in an array. So you need to figure out which element in the array will be the root element in the tree, and return the index. Now, ANY element could be the root, it really doesn't matter, so is the question really asking, "what is the ideal element for the root of the tree assuming 'ideal' means balanced?" And finally, you can ask yourself, if I want a balanced tree, what IS a good choice for a root element? Is it the smallest value? The largest? Does it matter? Why?
The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.
If I'm not mistaken, but doesn't a complete binary search tree have only one possibility for the root? I forget what the mathematical term for it is but I would think the root is always the number thats the middle of the of numbers, in other words the only number that has X items greater than it and X items less than it.
I don't think theres a mathematical equation for it though since the values could be heavily skewed for example the array [2,1,10000000] the root would be 2 but I don't know how you would come up with that with an equation. A simple algorithm could do it though.
What? In a 'complete' binary search tree, the root does matter. Given any ordering of elements, there is only one way to make a complete binary search tree.Originally Posted by IfYouSaySo
Mr. Acclude, I believe your effort to figure out your calculation can be simplified with these questions, all directly calculable from the total number of elements.
1. How many elements will be in the bottom row of a tree of size N?
2. How many elements (in the bottom row) will lie to the left of the center of the tree?
3. How many elements won't be in the bottom row of the tree? Of these how many are left of center?
My mistake. 'Complete' basically means 'balanced'. It's probably a more strict definition actually. At any rate the choice is the middle element. I was going to let him figure that out, since it is homework and all, but whatever.
The crows maintain that a single crow could destroy the heavens. Doubtless this is so. But it proves nothing against the heavens, for the heavens signify simply: the impossibility of crows.
No it's homework, teacher said to go think about it, and I was wondering and couldn't figure it out. And yea your right a algorithm not a equestion.
