3
$\begingroup$

My question is about part 15.5 in CLRS (third edition)*, on optimal binary search trees. I am confused about the following sentences:

Consider any subtree of a binary search tree. It must contain keys in a contiguous range $k_i, …, k_j$ for some $1 \leq i \leq j \leq n$. In addition, a subtree that contains keys $k_i, …, k_j$ must also have as its leaves the dummy keys $d_{i-1}, … d_j$.

(where $(k_j)_{j \in {[1,\ …,\ n]}}$ is a sorted sequence containing the keys of the nodes in the BST).

The chapter does not include proof of this statement, which does not seem obvious to me at all.

Moreover, I do not understand why the tree (key: $d_0$, right child: (key: $k_1$, right child: $d_1$)) — where $d_0$ is the dummy node corresponding to values strictly less than $k_1$ and $d_1$ is the dummy node corresponding to values strictly greater than $k_1$ — is not a satisfactory counterexample. It satisfies the BST property ($d_0 < k_1 < d_1$) and $k_1$ is not an ancestor of $d_0$.


* Introduction to Algorithms, Cormen, Leiserson, Rivest & Stein

$\endgroup$
0
3
$\begingroup$

Let us prove by induction on depth that for every node $v$, there exist $a_v,b_v$ (possibly $\pm \infty$) such that the input $x$ reaches $v$ iff $a_v < x < b_v$. This is true for the root since we can take $a_r = -\infty$ and $b_r = +\infty$. Now suppose that it is true for some node $v$, and let $v_<,v_>$ be its two children. Suppose that node $v$ compares $x$ to $c_v$. Then $x$ reaches $v_<$ if $a_v < x < c_v$ and $v_>$ if $c_v < x < b_v$ (I'm not sure what happens when $x = c_v$ — that depends on the exact definition of BST). This implies your stated property.

Your example has three nodes. The first contains the values $d_0,k_1,d_1$, the second contains the values $k_1,d_1$, the third contains the value $d_1$. All of these are contiguous ranges (which is a more concise way to state the property in your post).

$\endgroup$
7
  • $\begingroup$ The value being compared against at the node $v$. $\endgroup$ Jul 30 at 14:04
  • $\begingroup$ Ahh. I get it. Thanks! $\endgroup$ Jul 30 at 14:05
  • $\begingroup$ Thank you. As for the second paragraph, I understand that my example does not contradict the contiguous range property, but the paragraph from the book that I quoted also specifies that every node $k_i$ should be an ancestor of the two dummy nodes $d_{i - 1}$ and $d_i$. This is the property which does not seem to be satisfied by my example. $\endgroup$ Jul 30 at 14:19
  • $\begingroup$ That seems like a different question, which requires more context. $\endgroup$ Jul 30 at 14:20
  • $\begingroup$ @user8171079 dummy nodes can not be internal nodes. They have to be the leaf nodes. $\endgroup$ Jul 30 at 14:30

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.