View source for Inserção numa BST

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 <code>STinsert</code> 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 <code>STinsert</code> (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 <code>STinsert</code> do ADT tabela de sÃmbolos. 

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