Olaf Krzikalla
Joaquin M Lopez Munoz schrieb:
* if p is in A, insertion takes place before k1, * if p is in K, insertion takes place before p, * if p is in B, insertion takes place before b1.
That was clear to me. However thanks for the example. I can use it to describe the point of my uncertainty: assume our hint points to k2 and we want to insert an element with key k (say kn). If "the position just prior to k2" means k1, then it's unclear whether kn is inserted before k1 or after k1 - both positions are equal close to k1. However if "the position just prior to k2" means the position between k1 and k2, then all is well defined and works as intended.
It is the latter --the position between k1 and k2. Joaquín M López Muñoz Telefónica, Investigación y Desarrollo