Line 1: | Line 1: | ||
A função de remoção actua recursivamente. Quanto um elemento é removido, as suas duas sub-árvores são [[Junção de Duas BSTs (caso particular)|ligadas]] e ancoradas na árvore principal. | A função de remoção actua recursivamente. Quanto um elemento é removido, as suas duas sub-árvores são [[Junção de Duas BSTs (caso particular)|ligadas]] e ancoradas na árvore principal. | ||
− | link deleteR(link h, Key v) { | + | link '''deleteR'''(link h, Key v) { |
Key t = key(h->item); | Key t = key(h->item); | ||
if (h == z) return z; | if (h == z) return z; | ||
− | if (less(v, t)) { h->l = deleteR(h->l, v); } | + | if (less(v, t)) { h->l = '''deleteR'''(h->l, v); } |
− | if (less(t, v)) { h->r = deleteR(h->r, v); } | + | if (less(t, v)) { h->r = '''deleteR'''(h->r, v); } |
if (eq(t, v)) { | if (eq(t, v)) { | ||
− | link x = h; h = joinLR(h->l, h->r); free(x); | + | link x = h; |
+ | h = '''joinLR'''(h->l, h->r); | ||
+ | free(x); | ||
} | } | ||
return h; | return h; | ||
} | } | ||
− | + | ||
− | void STdelete(Key v) { head = deleteR(head, v); } | + | Implementação da função <code>STdelete</code> do ADT da tabela de sÃmbolos. |
+ | |||
+ | void '''STdelete'''(Key v) { | ||
+ | head = '''deleteR'''(head, v); | ||
+ | } |
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); }