Revision as of 10:17, 19 May 2005

Variações sobre o processo de inserção de elementos em BSTs.

Versão Recursiva

Função de inserção recursiva numa BST.

 link insertR(link h, Item item) {
   Key v = key(item), t = key(h->item);
   if (h == z) return NEW(item, z, z, 1);
   if less(v, t) h->l = insertR(h->l, item);
   else          h->r = insertR(h->r, item);
   h->N++;
   return h;
 }

Implementação da função do ADT

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

 void STinsert(Item item) {
   head = insertR(head, item);
 }

Versão Não Recursiva

Implementação directa, não recursiva, da função STinsert (ADT).

 void STinsert(Item item) {
   Key  v = key(item);
   link p = head, x = p;
   if (head == z)  {
     head = NEW(item, z, z, 1);
     return;
   }
   while (x != z) {
     p = x;
     x->N++;
     x = less(v, key(x->item)) ? x->l : x->r;
   }
   x = NEW(item, z, z, 1);
   if (less(v, key(p->item))) p->l = x; else p->r = x;
 }

Inserção na Raiz

 link insertT(link h, Item item) {
   Key v = key(item);
   if (h == z) return NEW(item, z, z, 1);
   if (less(v, key(h->item))) {
     h->l = insertT(h->l, item); h = rotR(h);
   }
   else {
     h->r = insertT(h->r, item); h = rotL(h);
   }
   return h;
 }

Implementação da função do ADT

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

 void STinsert(Item item) {
   return head = insertT(head, item);
 }