Remoção de Elementos de uma BST: Difference between revisions
From Wiki**3
No edit summary |
No edit summary |
||
| 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); | |||
} | |||
Revision as of 06:47, 19 May 2005
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);
}