12.2 Querying a binary search tree

12.2-1

Suppose that we have numbers between \(1\) and \(1000\) in a binary search tree, and we want to search for the number \(363\). Which of the following sequences could not be the sequence of nodes examined?

a. \(2, 252, 401, 398, 330, 344, 397, 363\).

b. \(924, 220, 911, 244, 898, 258, 362, 363\).

c. \(925, 202, 911, 240, 912, 245, 363\).

d. \(2, 399, 387, 219, 266, 382, 381, 278, 363\).

e. \(935, 278, 347, 621, 299, 392, 358, 363\).

• c. could not be the sequence of nodes explored because we take the left child from the \(911\) node, and yet somehow manage to get to the \(912\) node which cannot belong the left subtree of \(911\) because it is greater.
• e. is also impossible because we take the right subtree on the \(347\) node and yet later come across the \(299\) node.

12.2-2

Write recursive versions of \(\text{TREE-MINIMUM}\) and \(\text{TREE-MAXIMUM}\).

1
2
3
4

TREE-MINIMUM(x)
    if x.left != NIL
        return TREE-MINIMUM(x.left)
    else return x

1
2
3
4

TREE-MAXIMUM(x)
    if x.right != NIL
        return TREE-MAXIMUM(x.right)
    else return x

12.2-3

Write the \(\text{TREE-PREDECESSOR}\) procedure.

1
2
3
4
5
6
7
8

TREE-PREDECESSOR(x)
    if x.left != NIL
        return TREE-MAXIMUM(x.left)
    y = x.p
    while y != NIL and x == y.left
        x = y
        y = y.p
    return y

12.2-4

Professor Bunyan thinks he has discovered a remarkable property of binary search trees. Suppose that the search for key \(k\) in a binary search tree ends up in a leaf. Consider three sets: \(A\), the keys to the left of the search path; \(B\), the keys on the search path; and \(C\), the keys to the right of the search path. Professor Bunyan claims that any three keys \(a \in A\), \(b \in B\), and \(c \in C\) must satisfy \(a \le b \le c\). Give a smallest possible counterexample to the professor's claim.

Search for \(9\) in this tree. Then \(A = \\{7\\}\), \(B = \\{5, 8, 9\\}\) and \(C = \\{\\}\). So, since \(7 > 5\) it breaks professor's claim.

12.2-5

Show that if a node in a binary search tree has two children, then its successor has no left child and its predecessor has no right child.

Suppose the node \(x\) has two children. Then it's successor is the minimum element of the BST rooted at \(x.right\). If it had a left child then it wouldn't be the minimum element. So, it must not have a left child. Similarly, the predecessor must be the maximum element of the left subtree, so cannot have a right child.

12.2-6

Consider a binary search tree \(T\) whose keys are distinct. Show that if the right subtree of a node \(x\) in \(T\) is empty and \(x\) has a successor \(y\), then \(y\) is the lowest ancestor of \(x\) whose left child is also an ancestor of \(x\). (Recall that every node is its own ancestor.)

First we establish that \(y\) must be an ancestor of \(x\). If \(y\) weren't an ancestor of \(x\), then let \(z\) denote the first common ancestor of \(x\) and \(y\). By the binary-search-tree property, \(x < z < y\), so \(y\) cannot be the successor of \(x\).

Next observe that \(y.left\) must be an ancestor of \(x\) because if it weren't, then \(y.right\) would be an ancestor of \(x\), implying that \(x > y\). Finally, suppose that \(y\) is not the lowest ancestor of \(x\) whose left child is also an ancestor of \(x\). Let \(z\) denote this lowest ancestor. Then \(z\) must be in the left subtree of \(y\), which implies \(z < y\), contradicting the fact that \(y\) is the successor of \(x\).

12.2-7

An alternative method of performing an inorder tree walk of an \(n\)-node binary search tree finds the minimum element in the tree by calling \(\text{TREE-MINIMUM}\) and then making \(n - 1\) calls to \(\text{TREE-SUCCESSOR}\). Prove that this algorithm runs in \(\Theta(n)\) time.

To show this bound on the runtime, we will show that using this procedure, we traverse each edge twice. This will suffice because the number of edges in a tree is one less than the number of vertices.

Consider a vertex of a BST, say \(x\). Then, we have that the edge between \(x.p\) and \(x\) gets used when successor is called on \(x.p\) and gets used again when it is called on the largest element in the subtree rooted at \(x\). Since these are the only two times that that edge can be used, apart from the initial finding of tree minimum. We have that the runtime is \(O(n)\). We trivially get the runtime is \(\Omega(n)\) because that is the size of the output.

12.2-8

Prove that no matter what node we start at in a height-\(h\) binary search tree, \(k\) successive calls to \(\text{TREE-SUCCESSOR}\) take \(O(k + h)\) time.

Suppose \(x\) is the starting node and \(y\) is the ending node. The distance between \(x\) and \(y\) is at most \(2h\), and all the edges connecting the \(k\) nodes are visited twice, therefore it takes \(O(k + h)\) time.

12.2-9

Let \(T\) be a binary search tree whose keys are distinct, let \(x\) be a leaf node, and let \(y\) be its parent. Show that \(y.key\) is either the smallest key in \(T\) larger than \(x.key\) or the largest key in \(T\) smaller than \(x.key\).

• If \(x = y.left\), then calling successor on \(x\) will result in no iterations of the while loop, and so will return \(y\).
• If \(x = y.right\), the while loop for calling predecessor (see exercise 3) will be run no times, and so \(y\) will be returned.

本页面的全部内容在 小熊老师 - 莆田青少年编程俱乐部 0594codes.cn 协议之条款下提供，附加条款亦可能应用