I'm not sure how to construct a balanced search tree out of a few numbers and their associated search probabilities.
Please explain using the following example:
15 0.2
10 0.22
107 0.02
30 0.05
12 0.18
105 0.25
120 0.08
Asked
Active
Viewed 32 times
0
-
1A balanced search tree does not take the search probabilities into account. You are probably after an optimal search tree, which can be imbalanced. – Apr 05 '17 at 09:30
-
The question asked for what u said also, which I can do. However, I do want an algorithm for constructing a/the balanced tree, even if it means ignoring their probabilities. – Ahmad Abdelzaher Apr 05 '17 at 09:37
1 Answers
0
To build a balanced search tree, sort the array and recursively pick the medians.
10 12 15 30 105 107 120
10 12 15 30 105 107 120
10 12 15 30 105 107 120
-
Thanks. What if I only do one iteration, wouldn't this tree be balanced?
10 12 15 30 105 107 120
– Ahmad Abdelzaher Apr 05 '17 at 09:47 -
-
picture an upside down v with 30 is the root, can you see it? – Ahmad Abdelzaher Apr 05 '17 at 09:53
-
I meant for the left side 30 parent of 15, parent of 12, of 10. Perfect upside down v.(sorry I'm on phone) – Ahmad Abdelzaher Apr 05 '17 at 09:57
-
U show 30 parent of 12 and from 12 it's an upside v of 10 and 15 from left to right. I'm talking about 30 parent of 15,...etc, no other branches except for the big upside down v. – Ahmad Abdelzaher Apr 05 '17 at 10:09
-
@AhmadAbdelzaher: a single upside down V is not balanced at all. It is very close to the most imbalanced which is possible. – Apr 05 '17 at 10:19
-
what defines a balanced tree? isn't it the same height (depth)? – Ahmad Abdelzaher Apr 05 '17 at 10:31
-
@AhmadAbdelzaher: that's one possible definition, there are others. But according to it, the V is imbalanced. – Apr 05 '17 at 10:46