Árvores 2-3

Livro de Sedgewick e Wayne: sec.3.3, p.424.  Website do livro: resumo sec.3.3, slides.  Código fonte, documentação, e dados de teste de todos os programas do livro: veja algs4.cs.​princeton.edu/​code/.

Como implementar uma tabela de símbolos em uma BST de modo que a árvore permaneça aproximadamente balanceada  (ou seja, tenha altura próxima de lg N, sendo N o número de nós)  qualquer que seja a sequência de buscas e inserções aplicada à árvore?  Esta página mostra como árvores 2-3 resolvem o problema em princípio. A implementação da ideia, usando árvores rubro-negras, será discutida na próxima página.

Árvores 2-3 de busca

• Por que a altura de uma BST cresce? Cada inserção (put) pode criar um novo nó e assim aumentar a altura da árvore.
• Solução: coloque mais de uma chave em cada nó!
• Difícil: faça isso de modo que nenhum nó tenha mais que 2 chaves.
• A árvore, que era binária, torna-se ternária.  Na verdade, uma mistura de binária e ternária.

  

• Uma árvore 2-3 de busca (2-3 search tree) é
  • uma árvore vazia;
  • ou um nó simples, que contém uma chave e dois links: um link esquerdo para uma árvore 2-3 que tem chaves menores que a chave do nó e um link direito para uma árvore 2-3 que tem chaves maiores;
  • ou um nó duplo, que contém duas chave e três links: um link esquerdo para uma árvore 2-3 que tem chaves menores; um link do meio para uma árvore 2-3 que tem chaves entre as duas chaves do nó; e um link direito para uma árvore 2-3 que tem chaves maiores.
• (Árvores 2-3 têm esse nome porque cada nó tem 2 ou 3 links.)
• Toda árvore 2-3 é perfeitamente balanceada:  todos os links null estão no mesmo nível.

Exercícios 1

1. Quantas chaves, no máximo, pode conter uma árvore 2-3 de altura 2? Qual o número mínimo de chaves em uma árvore 2-3 de altura 2?

Busca em árvore 2-3

• Exemplo de busca em uma árvores 2-3:

  

• Veja o video algs4.cs.princeton.edu/lectures/33Demo23Tree.mov de SW que ilustra operações sobre uma árvore 2-3: 
  • busca bem-sucedida (busca H),
  • busca malsucedida (busca B),
  • inserção em nó simples na base (insere K)
  • inserção em nó duplo na base (insere Z)
  • inserção em nó duplo na base e subdivisão da raiz (insere L)
  • construção de uma árvore 2-3 (insere S E A R C H E X A M P L E)

Inserção em árvore 2-3

• Exemplo: inserção em um nó simples (a operação não estraga o balanceamento):

  

• Exemplo: inserção em um nó duplo isolado:

  

• Exemplo: inserção em um nó duplo cujo pai é um nó simples (a operação não estraga o balanceamento):

  

• Exemplo: inserção em um nó duplo cujo pai é um nó duplo:

  

• Inserção em um nó duplo cujo pai é um nó duplo: repita a operação subindo em direção à raiz até encontrar um nó simples (nesse caso a altura não aumenta) ou até encontrar a raiz (nesse caso a altura aumenta).  A operação não estraga o balanceamento.
• Exemplo: Divisão da raiz (não estraga o balanceamento, mas aumenta a altura):

  

• A divisão de um nó triplo temporário envolve apenas 6 transformações.  As transformações são locais e portanto consome tempo constante

  

• As transformações preservam as propriedades globais da árvore (a árvore continua em ordem e perfeitamente balanceada):

  

• Passo-a-passo da construção de uma árvore 2-3 de busca.  (Cubra a figura com uma folha de papel; depois, descubra-a passo a passo; a cada passo, procure prever o resultado da operação seguinte):

  

• Na coluna direita da figura acima, as chaves são inseridas em ordem crescente. A árvore 2-3 resultante tem altura 2. A BST resultante teria altura 9.

Exercícios 2

1. (SW 3.3.1)  Desenhe a árvore 2-3 que resulta da inserção das chaves E A S Y Q U T I O N, nesta ordem, em uma árvore inicialmente vazia.
2. (SW 3.3.2)  Desenhe a árvore 2-3 que resulta da inserção das chaves Y L P M X H C R A E S nesta ordem, em uma árvore inicialmente vazia.
3. (SW 3.3.3)  Encontre uma ordem de inserção para as chaves S E A R C H X M que resulte em uma árvore 2-3 de altura 1.

Desempenho de pior caso

• Árvores 2-3, foram inventadas para garantir um bom desempenho no pior caso.  (Se você está satisfeito com bom desempenho médio, basta usar uma BST.)
• Considere uma árvore 2-3 com N nós.  Se temos apenas nós simples, a altura da árvore será ⌊lg N⌋.  Se temos apenas nós duplos, a altura da árvore será ⌊log₃ N⌋, que é igual a ⌊0.63 lg N⌋.  Conclusão: a altura nunca passa de lg N.
• Proposition F: Numa árvore 2-3 com N nós, busca e inserção nunca visitam mais que lg N nós, mesmo no pior caso.  (Cada visita faz no máximo 2 comparações de chaves.)
• Exemplo: Uma árvore 2-3 típica, construída com chaves em ordem aleatórias (quantas chaves diferentes há nessa árvore?)

  

Exercícios 3

1. (SW 3.3.4)  Mostre que a altura de uma árvore 2-3 fica entre algo próximo de ⌊log₃ N⌋ e algo próximo de ⌊lg N⌋.
2. Qual a altura de uma árvore 2-3 que tem 1 bilhão de chaves?

Implementação

• Para implementar uma árvore 2-3, use nós de dois tipos: um com uma chave e dois links e outro com duas chaves e três links. O código fica pesado e complicado…
• Uma ideia melhor:  usar BSTs (árvores binária de busca) para simultar árvores 2-3! Veja a próxima aula.

Exercícios 4

1. (SW 3.3.35)  Escreva um programa TwoThreeST.java que use dois tipos de nós para implementar árvores 2-3 diretamente.

Resumo das 4 implementações de TSs vistas até aqui

• Numa árvore 2-3, alguns nós envolvem uma comparação entre chaves enquanto outros envolvem três comparações. Assim, o número de comparações de chaves é no máximo o dobro do número de nós visitados.
• A tabela dá o número de comparações entre chaves numa TS com N chaves:

  	pior caso (tabela com N chaves)			caso médio (N chaves inseridas em ordem aleatória)
  	busca	inserção	delete	busca bem-sucedida	inseção	delete
  busca sequencial em lista ligada	N	N	N	N/2	N	N/2
  busca binária em vetor ordenado	lg N	N	N	lg N	N/2	N/2
  busca binária em BST	N	N	N	1.4 lg N	1.4 lg N	?
  árvore 2-3	c lg N	c lg N	c lg N	c lg N	c lg N	c lg N

  A última linha se refere a qualquer implementação razoável de árvores 2-3.  A constante c depende da implementação.