As árvores binárias são excelentes! Muito eficientes e bastante simples de implementar. O problema de árvores binárias comuns, é que elas se degeneram e nem sempre se degeneram em listas encadeadas, mas em algo entre a árvore ideal e uma lista encadeada - normalmente um tempo médio pior que lg(n) e melhor que (n/2).

Teoricamente, depois de "n" inserções e remoções aleatórias em uma árvore binária comum, espera-se que o tempo médio de pesquisa, remoção e inserção sejam de O(sqrt(n)). Apesar de não crescer tão rápido quanto n/2, sqrt(n) cresce mais rápido que lg(n), então a teórica super-eficiência das árvores é perdida.

Como citado na introdução, o que podemos fazer para tentar preservar essa eficiência é balancear a árvore a cada inserção e remoção, mantendo os tempos de inserção e remoção em [lg(n) + k] (onde 'k' é uma constante determinada pelo número de operações necessárias para balancear a árvore) e mantendo o tempo de pesquisa médio sempre em lg(n). Fonte:

• Desmos Graphing Calculator

Todas as imagens do artigo foram feitas por mim, exceto esta última sobre a comparação das performances. Todo o conteúdo (texto e código fonte) foi escrito por mim (do código, exceto a função de imprimir a árvore lateralmente. Essa foi idéia do Herbert Schildt, autor de C Completo e Total).

Por motivos didáticos, criei um pequeno programa interativo para demonstrar como as árvores binárias vão crescendo. O código-fonte na próxima seção é um aplicativo interativo que recebe os seguintes comandos simples:

• i 20 :: vai inserir o elemento 20 na árvore;
• d 20 :: vai remover o elemento 20 da árvore;
• m :: vai mostrar a árvore na tela;
• o :: transversalização ordenada;
• r :: transversalização pré-ordenada;
• p :: transversalização pós-ordenada;
• s :: sai do programa.

Exemplo de output:

    |    Arvores Binarias
    |    Implementacao em C para o Viva O Linux
    |
    |    Autor: Enzo Ferber
    |    2015
    |

                Lista de comandos
                -----------------
                i %d - Inserir um elemento
                d %d - Deletar um elemento
                m    - Mostrar a arvore lateralmente
                o    - Transversalizacao Ordenada
                r    - Transversalizacao Pre-Ordenada
                p    - Transversalizacao Pos-Ordenada
                s    - Sair do programa
                h    - Mostra a ajuda

ArvoreBinaria> i 10 20 30 5 15 25 2 8 12 17
ArvoreBinaria> m
    30
      25
  20
      17
    15
      12
10
    8
  5
    2
ArvoreBinaria> o
2 5 8 10 12 15 17 20 25 30
ArvoreBinaria> d 5 2 8
ArvoreBinaria> m
    30
      25
  20
      17
    15
      12
10
ArvoreBinaria> p
12 17 15 25 30 20 10
ArvoreBinaria> r
10 20 15 12 17 30 25
ArvoreBinaria> d 10 20 15 12 17 25 30
ArvoreBinaria> m
ArvoreBinaria> i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
ArvoreBinaria> m
                                    19
                                  18
                                17
                              16
                            15
                          14
                        13
                      12
                    11
                  10
                9
              8
            7
          6
        5
      4
    3
  2
1
ArvoreBinaria>>

Observações finais

1. Vale ressaltar que o algoritmo usado para imprimir a árvore lateralmente é muito interessante e vale a pena ser lido.

2. Deixei intencionalmente a função para destruir uma árvore como exercício. Como você implementaria uma função para destruir a árvore? É possível escrever essa função de forma recursiva ou apenas iterativa?

3. Observe a degeneração no último output do exemplo! É uma lista encadeada!

4. Pense um pouco: é possível implementar árvores binárias de forma iterativa? É mais simples ou complexo?

5. Download dos fontes: CodigosFonte_Completo.zip

Bons estudos!