Função que devolve o número de elementos de uma árvore

Função que nos diz se um elemento pertence ou não a uma árvore (sem ordem)

Função que nos diz se um elemento pertence ou não a uma árvore (com ordem)

Quantas comparações temos que fazer ( no pior caso )?

Função para inserir um elemento numa árvore binária ordenada

Procedimento para inserir um elemento numa árvore ordenada

Animação Gráfica (Applet)
 

Função que devolve o número de elementos de uma árvore

    Função ContarElem ( Árvore ) --> Inteiro
        começar
            se EvaziaArv ( Árvore )
                devolver 0
            senão
                devolver 1 + ContarElem ( fe ( Árvore ) ) + ContarElem ( fd ( Árvore ) )
        acabar
 
 
 

Função que nos diz se um elemento pertence ou não a uma árvore (sem ordem)

    Função PertenceArv ( Elemento , Árvore ) --> boolean
        começar
            se EvaziaArv  ( Árvore )
                devolver Falso
            senão
                começar
                    se No ( Árvore ) = Elemento
                        devolver Verdadeiro
                    senão
                        devolver PertenceArv ( x, fe ( Árvore ))  OU  PertenceArv ( x, fd ( Árvore ))
                acabar
        acabar
 

Exemplo de uma árvore:

Para que a árvore seja útil é melhor que seja uma árvore ordenada

Para que a árvore seja ordenada, os elementos do filho direito têm de ser >= que o pai e os elementos do filho esquerdo têm de ser < que o pai.

Exemplo de uma árvore ordenada

    Função PertenceArvOrd ( Elemento , Árvore ) --> boolean
        começar
            se EvaziaArv ( Árvore )
                devolver Falso
            senão
                começar
                    se No ( Árvore ) = Elemento
                        devolver Verdadeiro
                    senão
                        começar
                             se Elemento < No ( Árvore )
                                devolver PertenceArvOrd ( Elemento, fe ( Árvore ))
                            senão
                                devolver PertenceArvOrd ( Elemento, fd ( Árvore )
                        acabar
                acabar
        acabar
 
 

Quantas comparações temos que fazer ( no pior caso )?

    Altura = log₂ ( elementos +1 )
 

A árvores ordenadas "servem" mas têm um problema

Neste caso, em que temos cinco elementos, para procurar o 5, tinhamos que fazer cinco comparações. A árvore tem de ser equilibrada.

Função para inserir um elemento numa árvore binária ordenada

    Função InserArvOrd ( Elemento , Árvore ) --> Árvore
        começar
            se EvaziaArv ( Árvore )
                devolver CriarArv (Árvore, NULL, NULL )
            senão
                começar
                    se ( Elemento < No ( Árvore )
                        devolver CriarArv ( No ( Árvore ), InserArvOrd ( Elemento, fe ( Árvore )), fd ( Árvore) )
                    senão
                        devolver CriarArv ( No ( Árvore ), fe ( Árvore ), InserArvOrd ( Elemento, fd ( Árvore ))
                acabar
        acabar
 
 

Exemplo:

• Quantos espaços de memória são reservados no final?

Procedimento para inserir um elemento numa árvore ordenada

    Procedimento InserArvOrd ( Elemento , Árvore* )
        começar
            se EvaziaArv ( Árvore )
                Árvore <-- CriarArv (Árvore, NULL, NULL )
            senão
                começar
                    se ( Elemento < No ( Árvore )
                   InserArvOrd ( Elemento, apont fe ( Árvore ))
                    senão
                   InserArvOrd ( Elemento, apont fd ( Árvore ))
                acabar
        acabar

• E agora quantas caixas?

Animação Gráfica (Applet)