How to construct a balanced search tree?

Question

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

Answer 1

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