(Picture above is Figure 18.8(a)) predecessor(x, k): x points to a node containi
ID: 3930485 • Letter: #
Question
(Picture above is Figure 18.8(a))
predecessor(x, k): x points to a node containing a key k. The function returns the predecessor key of k; it returns Nil if the predecessor of k does not exist in the tree. For example, in the B-tree in Figure 18.8 (a), the predecessor of P is O and the predecessor of Q is P.
Note that the predecessor of k is interpreted as the key immediately preceding k in the implicit ordering in the tree. So the predecessor of k may be equal to k if the tree has multiple occurrences of k. In case the predecessor of k is interpreted as the largest key less than k, the above algorithm needs to be modified to skip the multiple occurrences of k, please resolve this