I'm working on the following task and would like to know if I did it right:
Consider a randomized search tree with values
$x_i := \frac{i^2 - log_2(i)}{2}$ and the priorities $p_i := 256 - > |256 - i|$
both for $ i = 1,...,511$.
Determine the exact form and depth for each of the resulting search tree.
At first we note that $x$ is a strictly increasing function, therefore applies $x_i < x_j$ for $i < j$. Then we see that $p$ is a symmetric "saw tooth" function with it's largest value at i=256. ($p$ further assumes all integer values between 1 and 256.)
Please see the attached picture for my sketch of the tree. (I drew the $x_i$ inside the nodes and wrote the priorities above the nodes.)
With these observations we can deduce, that the depth of the tree is $256 -1 = 255$.
Is my reasoning correct ?
Thanks for any answers.
