BSTs: operações adicionais

Além das operações básicas put() e get(), algumas outras operações em TSs podem ser úteis, especialmente se as chaves forem comparáveis. Esta página trata da implementação dessas operações adicionais em BSTs (árvores binárias de busca).

Resumo:

mínimo e máximo
piso e teto
remoção de um nó

Pré-requisitos:

BSTs

Mínimo e máximo

Como as chaves de uma BST são comparáveis, podemos perguntar pela chave mínima e pela chave máxima. (Note que o mínimo e o máximo não estão definidos se a árvore for vazia.)

[Continuação do Algoritmo 3.3] Método min() da classe BST:

   // Devolve a menor chave da tabela de
   // símbolos (ou null se a tabela estiver
   // vazia).

   public Key min() {
      if (root == null) return null;
      return min(root);
   }

   // Devolve a menor chave da subárvore cuja
   // raiz é x. (Supõe que x não é null.)

   private Key min(Node x) {
      if (x.left == null) return x.key;
      return min(x.left);
   }

Desempenho: o número de nós visitados por uma execução de min() é no máximo 1 + h, sendo h a altura da BST.

Exercícios 1

O anexo desta página mostra várias maneiras alternativas de escrever o método min(). Discuta e critique cada uma delas.
Implemente o método max() na classe BST.

Piso e teto

Suponha que k é um objeto do tipo Key. O piso (floor) de k na BST é a maior chave da BST que é menor que ou igual a k.
Exemplo: Qual o piso de * na BST da figura, supondo que * vem antes de A no alfabeto? Qual o piso de H? Qual o piso de G?
Exemplo: Cálculo do piso de G:
Um objeto k não tem piso se todas as chaves da BST forem estritamente maiores que k.

[Continuação do Algoritmo 3.3] Método floor() da classe BST:

   // Devolve null se key não tem piso nesta
   // BST.

   public Key floor(Key key) {
      Node x = floor(root, key);
      if (x == null) return null;
      return x.key;
   }

   // Devolve o nó que contém o piso de key 
   // na subárvore com raiz x.
   // Devolve null se esse piso não existe.

   private Node floor(Node x, Key key) {
      if (x == null) return null;
      int cmp = key.compareTo(x.key);
      if (cmp == 0) return x;
      if (cmp < 0) return floor(x.left, key);
      Node t = floor(x.right, key);
      if (t != null) return t;
      else return x;
   }

O código é complicado! Digamos que você está procurando o piso de key na subárvore cuja raiz é x. Se key é igual a x.key, você encontrou o piso. Se key é menor que x.key, a resposta está na subárvore esquerda (ou não existe). Se key é maior que x.key, as coisas são um pouco mais difíceis: a resposta pode estar na subárvore direita, mas se key não tiver piso na subárvore direita então a resposta é x.key.
Desempenho: o número de nós visitados por uma execução de floor() é no máximo 1 + h, sendo h a altura da BST.

Exercícios 2

Critique a seguinte maneira de definir o piso: O piso de uma chave k é a maior chave da BST, menor que ou igual a k.
Quanto é floor(min())? Quanto é floor(max())?
Defina teto (ceiling) de um objeto k em uma BST. Implemente código para calcular o teto de um objeto.
Quanto é ceiling(min())? Quanto é ceiling(max())?
Quantos nós visita (ou seja, quantas comparações faz) cada execução de max() no pior caso? Mesma pergunta para ceiling().

Remoção de um nó em uma BST

Problema: remova (delete) um nó de uma BST e modifique a estrutura de modo que o que sobrar ainda seja uma BST.
A operação é difícil. Começamos com o caso especial de remover a menor chave [ignore os dizeres update node counts after recursive calls na figura]xs:

[Continuação do Algoritmo 3.3] Método deleteMin() da classe BST:

   // Remove o nó que tem a menor chave.
   // Supõe que a árvore não está vazia.

   public void deleteMin() {
      root = deleteMin(root);
   }

   // Remove o nó que tem a menor chave 
   // na subárvore (não vazia) cuja raiz é x 
   // e devolve a raiz da subárvore resultante.

   private Node deleteMin(Node x) {
      if (x.left == null) return x.right;
      x.left = deleteMin(x.left);
      return x;
   }

Outro caso especial relativamente fácil: remover um nó que não tem 2 filhos. Exemplo [ignore os dizeres update counts after recursive calls]:
Remover um nó que tem 2 filhos é mais difícil. Ideia: troque o nó pelo seu sucessor (que é o menor nó na subárvore direita). Exemplo [ignore os dizeres update node counts after recursive calls na figura]:
A operação geral de remoção será organizada assim: recebe uma chave e remove o nó que contém aquela chave.

[Continuação do Algoritmo 3.3] Método delete() da classe BST, inventado por T. Hibbard (1962):

   // Remove o nó que contém a chave key.
   // Se nenhum nó contém key, não faz nada.

   public void delete(Key key) { 
      root = delete(root, key); 
   }

   // Remove da subárvore cuja raiz éx
   // o nó que contém a chave key
   // e devolve a raiz da subárvore resultante.
   // (Se key não está na subárvore,
   // não faz nada e devolve x.)

   private Node delete(Node x, Key key) {
      if (x == null) return null;
      int cmp = key.compareTo(x.key);
      if (cmp < 0) x.left = delete(x.left, key);
      else if (cmp > 0) x.right = delete(x.right, key);
      else {
         if (x.right == null) return x.left;
         if (x.left == null) return x.right;
         Node t = x;
         x = min(t.right);  // note que x.left == null
         x.right = deleteMin(t.right);
         x.left = t.left;
      }
      return x;
   }

Desempenho de delete() no pior caso: proporcional à altura da árvore.

Exercícios 3

Implemente o método deleteMax() da classe BST.
Quantos nós visita (ou seja, quantas comparações faz) cada execução de delete() no pior caso?
(SW 3.2.17) Desenhe a sequência de BSTs que resulta quando você remove as chaves da BST do Exercício SW 3.2.1, uma a uma, na mesma ordem em que as chaves foram inseridas.
(SW 3.2.18) Desenhe a sequência de BSTs que resulta quando você remove as chaves da BST do Exercício SW 3.2.1, uma a uma, em ordem alfabética.
(SW 3.2.30) Reconstrução de BSTs. Suponha dada uma lista de todos os nós de uma BST, em pré-ordem. Projete um algoritmo que reconstrua a BST a partir dessa lista.