Assume that a full binary tree is layed out in memory recursively in the following way. First the Root followed by Tree representation of left subtree followed by tree representation of right subtree. Assume tree is complete and full.

If a search path requires to go from array location $a[i]$ to $a[k]$, then its referrred to as a jump and its of size $k-i$, since you travelled $k-i$ units of memory.

Given this arrangement of the tree, what is the expected size of a jump in this tree?

  • 1
    $\begingroup$ What probability distribution on $i$ do you have in mind? Are you interested in an unsuccessful search that goes through a random path on the tree? $\endgroup$ – Yuval Filmus Jul 24 '18 at 14:18
  • 1
    $\begingroup$ What do you think? Have you attempted to calculate the expected size? $\endgroup$ – Yuval Filmus Jul 24 '18 at 14:18
  • $\begingroup$ probability distribution is over all the successful search paths. I honestly have clue, but intuitively seems that it should be around $n/\log n$ $\endgroup$ – Vk1 Jul 24 '18 at 14:22
  • $\begingroup$ If it helps, you can assume that the searches are only on elements which are leaves of this tree. $\endgroup$ – Vk1 Jul 24 '18 at 14:32

Consider a binary search tree with layers $0,\ldots,h$, where layer $\ell$ contains $2^\ell$ nodes. The left child of a node $x$ is located next to it (at distance 1). If $x$ is at layer $\ell$, then its left subtree contain $2^{h-\ell}-1$ nodes, and so the right child of $x$ is at distance $2^{h-\ell}$. These observations are illustrated in the figure:


Here $h = 3$, and the root ($\ell = 0$) has a left child at distance $1$ and a right child at distance $2^{h-\ell} = 8$.

We will calculate the average size of a jump in a random root-to-leaf path. This corresponds to searching for a random leaf.

The expected jump at level $\ell$ is thus $\frac{1+2^{h-\ell}}{2}$. Since there are $h$ jumps overall (at levels $0$ to $h-1$), the average jump is $$ \frac{1}{h} \sum_{\ell=0}^{h-1} \frac{1+2^{h-\ell}}{2} = \frac{1}{2} + \frac{1 + \cdots + 2^{h-1}}{h} = \frac{1}{2} + \frac{2^h-1}{h}. $$ Since the number of nodes in the tree is $n := 2^{h+1}-1$, the average jump is $\Theta(n/\log n)$. The same holds for the number of leaves $m := 2^h$.

  • $\begingroup$ So using this what can we say about "probability" of search path having a jump of size $\Theta(n/\log n)$? I am assuming this is trivial for you, but I am unable to solve this. Thanks for the answer :) $\endgroup$ – Vk1 Jul 24 '18 at 19:25
  • $\begingroup$ Don't expect me to solve the entire exercise for you. $\endgroup$ – Yuval Filmus Jul 24 '18 at 19:33
  • $\begingroup$ If its not too much to ask, can you give a hint as to what I should be aiming for? I am a bit weak with topics related to expectation. Could you suggest me a probability related book for comp science students? $\endgroup$ – Vk1 Jul 24 '18 at 20:01
  • $\begingroup$ I suggest first studying discrete probability, and only then solving questions on discrete probability. $\endgroup$ – Yuval Filmus Jul 24 '18 at 20:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.