patternMinor
Observations about the structure of an optimal Binary Search Tree
Viewed 0 times
theoptimalsearchobservationsbinarystructureabouttree
Problem
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
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
Solution
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 $ be its two children. Suppose that node $v$ compares $x$ to $c_v$. Then $x$ reaches $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).
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).
Context
StackExchange Computer Science Q#142790, answer score: 3
Revisions (0)
No revisions yet.