I would like to find out the Expected height of a binary tree where the insertions are based on a random function. I.e. for each node I visit, there is a $\frac{1}{2}$ probability of choosing right or left. I know that the following property holds for height $h$, but it's difficult to add the probability:$$h_{tree}= 1+max(h_{left}, h_{right})$$I think that this version/random tree differs from the random (search) tree mentioned in CLRS chapter 12.4, where you pick a random element from a sorted list $\{1,\dots, n\}$ and insert based on whether the visited node is greater or less than the inserted element. Because, here we choose each path on each visited node to be random.

Note: the binary tree has all its elements at the leafs and internal nodes are only used for routing (see Figure 1.)

insert(i, tree):
    if at leaf v:
        split(); //Create a parent u and set its children to be the leaf v and element i.
        int left = random()
        int right = random()
        if (left > right):
            insert(i, left-subtree):
            insert(i, right-subtree)

Figure 1: example of binary tree

  • $\begingroup$ does split create a parent with two children (split removes two leaves and adds two new ones)? Or does it create a parent with just one child? $\endgroup$
    – plshelp
    Mar 13 '21 at 17:59
  • $\begingroup$ split is only used when the inserted element ends at a leaf. So, a parent node with two children is created. The first child is the old leaf, and the second child is the newly inserted element. $\endgroup$
    – hello_moto
    Mar 13 '21 at 18:12
  • $\begingroup$ Are you looking for a lower and upper bound or exact values? $\endgroup$
    – plshelp
    Mar 13 '21 at 18:45
  • $\begingroup$ The expected height. Due to the probability there is no exact value. $\endgroup$
    – hello_moto
    Mar 13 '21 at 18:52
  • $\begingroup$ The expected value is a well defined exact value. This seems to be what you are searching for: en.wikipedia.org/wiki/Random_binary_tree#Random_split_trees If you look at your version and pretend that the leaves are just placeholders, the wikipedia version and yours are the same. $O(\log n)$ is the expected height. If you look into the article you can find even better approximations. $\endgroup$
    – plshelp
    Mar 13 '21 at 19:02

Your Answer

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

Browse other questions tagged or ask your own question.