We insert \((u,p)\) , \((p,x)\)  and \((p,v)\)  and remove \((u,v)\)  from \(D\) . We find the labels of the three edges to insert as follows. We have that \(\mathsf {label}(u,p) = \mathsf {label}(u,v)\)  since \((u,p)\)  is the edge \((u,v)\)  shortened by adding the node \(p\)  and since only the first character of the edge affects the label. By definition, \(\mathsf {label}(p,x)\)  and \(\mathsf {label}(p,v)\)  consist of \(\mathsf {str}(p)\)  with a zero and a one appended, respectively. We compute \(\mathsf {str}(p)\)  by finding the longest common prefix \(\hat{p}\)  of \(x\)  and \(\mathsf {min}(v)\) . To do so, do bitwise XOR between \(x\)  and \(\mathsf {min}(v)\)  and find the index \(k\)  of the leftmost bit that is 1 in the result (see [1]}). Now \(k\)  indicates the leftmost bit where \(x\)  and \(\mathsf {min}(v)\)  differ. To extract the longest common prefix compute \(\hat{p} = x~\&~{\sim }((1\ll (k+1))-1)\) .
Given the labels we can easily construct the keys for the edges.
