0

Randomly built binary search tree

Define a randomly built binary search tree on \(n\) keys as one that arises from inserting the keys in random order into an initially empty tree, where each of the \(n!\) permutations of the input keys is equally likely.

  • Prove that the expected height of a randomly built binary search tree on \(n\) distinct keys is \(O({\log}n)\)
Source: from book "Introduction to Algorithms"

Related Content