Operações adicionais em TSs

Além das operações fundamentais de inserção (put) e busca (get), uma tabela de símbolos pode aceitar operações adicionais.  Algumas dessas operações só fazem sentido se a TS for ordenada.

Operação de remoção

• Alguns clientes de TSs precisam de uma operação de remoção (deletion).
• Linha adicional na API da tabela de símbolos:

  void	delete(Key key)	remove chave key e o correspondente valor

Exercícios 1

1. (SW 3.1.5)  Implemente a operação de remoção na classe SequentialSearchST.
2. (SW 3.1.16)  Implemente a operação delete na classe BinarySearchST.

Operações em TSs ordenadas

• Se as chaves são comparáveis, a API da tabela de símbolos pode ter as seguintes operações adicionais:

  Key	min()	a menor chave desta TS
  Key	max()	a maior chave desta TS
  Key	floor(Key key)	o piso de key, ou seja, a maior chave ≤ key
  Key	ceiling(Key key)	o teto de key, ou seja, a menor chave ≥ key
  Key	select(int k)	chave cujo posto é k
  void	deleteMin()	remove a menor chave (e o valor associado)
  void	deleteMax()	remove a maior chave (e o valor associado)

• [Continuação do Algoritmo 3.2]  Operações adicionais na classe BinarySearchST:

     public Key min() { 
        return keys[0]; 
     }
  
     public Key max() {
        return keys[N-1];
     }
  
     public Key select(int k) {
        return keys[k];
     }
  
     public Key ceiling(Key key) {
        int i = rank(key);
        return keys[i];
     }
  

• Acrescente os métodos floor(), deleteMin(), deleteMax() à classe BinarySearchST.
• Custos das operações em BinarySearchST para tabela com N chaves:

  método	ordem de crescimento do tempo de execução
  delete()	N
  min()	1
  max()	1
  floor()	log N
  ceiling()	log N
  rank()	log N
  select()	1
  deleteMin()	N
  deleteMax()	1

Exercícios 2

1. (SW 3.1.17)  Defina o piso de um inteiro k em um conjunto S de inteiros.  Que acontece se S é vazio?
2. Defina o teto de um inteiro k em um conjunto S de inteiros.  Que acontece se S é vazio?
3. Qual o resultado de select(k) se k não está no intervalo 0..N-1?