Remoção de Elementos de uma BST

A função de remoção actua recursivamente. Quanto um elemento é removido, as suas duas sub-árvores são ligadas e ancoradas na árvore principal.

 link deleteR(link h, Key v) {
   Key t = key(h->item);
   if (h == z) return z;
   if (less(v, t)) { h->l = deleteR(h->l, v); }
   if (less(t, v)) { h->r = deleteR(h->r, v); }
   if (eq(t, v))   {
     link x = h;
     h = joinLR(h->l, h->r);
     free(x);
   }
   return h;
 }

Implementação da função STdelete do ADT da tabela de símbolos.

 void STdelete(Key v) {
   head = deleteR(head, v);
 }