Árvores binárias de busca

Uma árvore binária de busca balanceada com 1023 chaves acha qualquer uma delas em no máximo 10 comparações; construída a partir de uma entrada ordenada, as mesmas chaves podem levar 1023.

Busca binária embutida na forma

A busca binária num array ordenado acha uma chave em cerca de log₂ n verificações, mas inserir num array ordenado move valores. Uma tabela hash insere rápido, mas esquece a ordem: ela não consegue dizer com facilidade qual é a menor chave ou a próxima chave depois de 40. Uma árvore binária de busca (BST) tenta ter as duas coisas. Ela é feita de nós, como uma lista encadeada, mas cada nó tem dois ponteiros, left e right. O nó do topo é a raiz; um nó sem filhos é uma folha.

Uma regra faz dela uma árvore de busca: para todo nó, todas as chaves da subárvore esquerda são menores e todas as chaves da subárvore direita são maiores. Para buscar uma chave, comece na raiz e compare. Igual quer dizer encontrada. Menor quer dizer ir para a esquerda, maior quer dizer ir para a direita. Cada comparação descarta uma subárvore inteira, como a busca binária descarta metade da lista. Buscar 60 na árvore 50, 30, 70, 20, 40, 60, 80 compara com 50, depois 70, depois 60: 3 comparações.

Inserir segue o mesmo caminho. Vá para a esquerda ou para a direita até o ponteiro de que você precisa estar vazio e pendure o nó novo ali. Inserir 45 compara com 50 (vai para a esquerda), 30 (vai para a direita) e 40 (vai para a direita), e 40 não tem filho direito, então 45 vira esse filho. Apagar um nó que não é folha exige mais uma ideia: as notas do MIT trocam o item dele com a chave seguinte ou anterior na ordem e apagam a partir dali. A regra de contagem do laboratório é uma comparação por nó do caminho.

A altura é tudo

Quantas comparações uma busca pode levar? No máximo uma por nível, então o custo depende da altura da árvore, o número de arestas no caminho mais longo da raiz até uma folha. As notas do MIT dizem assim: as operações de árvore rodam em tempo O(h). A árvore 50, 30, 70, 20, 40, 60, 80 tem altura 2, então nenhuma busca precisa de mais de 3 comparações. Uma árvore perfeitamente balanceada com 1023 nós tem altura 9 e precisa de no máximo 10.

Mas a forma depende da ordem de inserção. Insira 10, 20, 30, 40, 50, 60, 70 em ordem crescente e cada chave é maior que tudo o que veio antes, então cada nó novo vai para a direita do último. A árvore vira uma cadeia de altura 6, e buscar 70 leva 7 comparações: uma lista encadeada com ponteiros extras. Com 1023 chaves ordenadas, a pior busca leva 1023 comparações em vez de 10.

As árvores balanceadas resolvem isso remodelando-se depois de cada inserção ou remoção. O primeiro esquema foi a árvore AVL, de Georgy Adelson-Velsky e Evgenii Landis, em 1962, que a aula 7 do MIT trata. Ela mantém, em todo nó, as alturas das duas subárvores com diferença de no máximo 1, e conserta qualquer quebra com pequenos movimentos locais chamados rotações. Isso mantém a altura em O(log n), então busca, inserção e remoção continuam O(log n), seja qual for a ordem de chegada das chaves.

Chaves em ordem de graça

Uma BST guarda mais do que a presença das chaves. Visite a subárvore esquerda, depois o nó, depois a subárvore direita, de forma recursiva, e as chaves saem em ordem crescente. Esse percurso em ordem (o MIT chama de ordem de travessia) é como uma BST responde a "menor chave", "maior chave" e "próxima chave depois de 40", as operações de ordem da interface Set do MIT que uma tabela hash não faz rápido.