First do \((I, P) = \mathsf {pRetrieve}{}(\,\overline{X}\,)\)  on \(D\) .
Then compute \(c =\mathsf {compress}(I)\)  such that the \(i\) th rightmost bit in \(c\)  is 1 if \(I\langle i \rangle  = 1\)  and zero otherwise. Find the index \(k\)  of the leftmost bit in \(c\)  that is 1 (see [1]}). Then \(\overline{X}\langle k \rangle  = \mathsf {key}(u,v)\)  where \((u,v)\)  is the exit edge of \(x\) . Furthermore, the values stored at the addresses \(P\langle k \rangle \)  and \(P\langle k \rangle  + 1\)  are the min- and max-pointers of \((u,v)\) , respectively.
