segunda-feira, 28 de novembro de 2011

Árvores Binárias de Busca: Uma abordagem mais avançada

Por @Jo_Ohn_ (blog)
Demorou mas saiu! Depois de duas semanas escrevendo e fazendo o código funcionar, aqui estamos com o post de árvores binárias de busca! Agora vai!

Anteriormente nesse blog que vos fala, foi falado um pouco sobre Árvores em Python. Uma abordagem deveras simplista e que não acrescenta muito para a disseminação do conhecimento técnico mais arcano da computação. Em vista disso, resolvi revisitar o post e escrever algo mais elegante e digno de nota nesse blog.

Vou ser sincero, na verdade isso aconteceu porque recebi um e-mail onde um leitor pediu para que eu esclarecesse um pouco o conceito de árvores, em uma abordagem um pouco menos Orientada à Objetos. E já que estamos tratando de Python, uma linguagem multi-paradigma (imperativa, funcional e orientada à objetos), resolvi atender esse pedido com esse pedido com uma explicação mais detalhada de árvores, suas operações básicas e inclusive falar da minha preferida, a árvore AVL (se der até falo das outras: Red Black e Splay).

Ok, vamos ao post!

Árvores Binárias


Primeiramente, vamos à definição. Na Ciência da Computação, uma árvore é uma estrutura de dados hierárquica que organiza as informações na forma de nós e de sub-árvores. Embora possa haver muitos tipos diferentes de árvores, árvores binárias são especiais porque, quando ordenadas, permitem pesquisas, inserções e exclusões rápidas. Cada item em uma árvore consiste em informação juntamente com um elo ao membro esquerdo e um elo ao membro direito.

Veja que essa definição é recursiva. Vamos simplificar um pouco....


Primeiramente, temos o Nó. O Nó é a estrutura básica de uma árvore. Um nó possui a informação que ele armazena e possui dois ponteiros. Estes ponteiros são chamados de ramificações ou sub-árvores. Normalmente se define como esquerda e direita, para uma melhor visualização.

Cada Nó pode ter até duas ramificações (também chamadas de folhas). A profundidade de um nó é a distância (em quantidade de nós) deste nó até a raiz da árvore. O conjunto de nós com a mesma profundidade em uma árvore é chamado de nível. E para finalizar, o nó com a maior profundidade em uma árvore também define a altura dessa árvore.

Em termos mais específicos, podemos dizer que uma árvore é um tipo de grafo acíclico, conexo e que cada nó não têm grau maior que 2. Assim sendo, só existe um único caminho entre dois nós distintos.

Outra definição possível: árvores binárias são árvores que ou são nulas ou são constituídas por um nó raiz e duas subárvores binárias, a subárvore esquerda e a subárvore direita (por sua vez cada uma destas subárvores ou são nulas ou constituídas por um nó raiz e duas subárvores binárias, a subárvore esquerda e a subárvore direita).

Árvores Binárias de Busca

Agora que definimos mais ou menos o que é uma árvore binária, vamos avançar um pouco mais na teoria antes de implementar algum código.

Uma árvore binária de busca (também chamada de árvore binária ordenada) é um tipo de árvore binária que possui algumas propriedades específicas:

A ramificação da esquerda de um Nó contém somente Nós com valores menores que o valor do Nó atual;
A ramificação da direita de um Nó contém somente Nós com valores maiores que o valor do nó atual;
As duas ramificações de um Nó devem ser obrigatoriamente árvores binárias de busca.

Por maior e menor entenda como qualquer conjunto cujos elementos podem ser comparados de forma a definir uma sequência progressiva crescente.

Até agora falamos somente sobre a estrutura da árvore. Vamos dar continuidade, falando das operações que podemos executar em cima da árvore, agora com nossos primeiros exemplos em Python.

Operações em Árvores Binárias de Busca

As principais operações que podemos executar em uma árvore binária de busca são três: Busca (DUH), Inserção e Remoção. Existem outras operações que podem ser efetuadas como a travessia da árvore para recuperar os seus elementos ou rotação para fazer balanceamento. Árvores também podem ser utilizadas para fazer ordenação de elementos, que veremos mais para frente.

Considerações: Para facilitar um pouco mais as operações de árvores em uma estrutura não orientada à objetos, algumas funções adicionais e variáveis globais foram criadas para tornar o código um pouco mais limpo. Abaixo listo as primeiras, sendo que o resto das funções encontram-se no código completo no final do post:

ESQ = 0
VALOR = 1
DIR = 2

class todosnaonulos(object):
    def __init__(self, f):
        self.f = f
    
    def __call__(self, *args, **kwargs):
        for arg in args:
            if arg is None:
                return None
        retorno = self.f(*args, **kwargs)
        return retorno

@todosnaonulos
def valor(no):
    return no[VALOR]

Definição da nossa Árvore Binária de Busca

Para facilitar o entendimento dos exemplos, definimos nossa árvore usando o objeto Lista do python, conforme o exemplo abaixo:

No = [None, None, None]

No nosso caso, todas as vezes que uma sub-árvore for uma folha (não possuir ramificações) ela será representada por um objeto List, vazio nos índices 0 e 2, ao passo que uma ramificação vazia será representada pelo objeto None do Python. Nesta estrutura, o primeiro dos três elementos irá armazenar a sub-árvore da esquerda, o segundo elemento armazenará o valor para o nó e o terceiro irá armazenar a sub-árvore da direita.

Então, para o exemplo da imagem ao lado, teremos a seguinte estrutura:

arvore = [[[None, 1, None], 3, [[None, 4, None], 6, [None, 7, None]]], 8, [None, 10, [[None, 13, None], 14, None]]]

Pode parecer um pouco confuso, mas durante o uso você verá que essa estrutura simples é suficiente para demonstrar todas as operações de uma árvore.

Impressão visual da árvore

Ok, tudo bem. Você vai querer imprimir visualmente sua árvore para verificar se a mesma está correta. Você está certo. Aqui têm uma função que você pode usar para imprimir visualmente a árvore:

@todosnaonulos
def imprime(arvore, identacao = 0):
    if type(arvore) == list:
        imprime(arvore[ESQ], identacao + 3)
        print " " * identacao + str(valor(arvore))
        imprime(arvore[DIR], identacao + 3)
    elif arvore is not None:
            print " " * identacao + str(arvore)

A função que imprime a árvore é baseada na operação de travessia em ordem. Mais pra frente vou explicar com mais detalhes essa operação. O que você precisa saber agora é que essa função pegará aquilo ali em cima e transformará em algo mais fácil de visualizar:

>>> arvore = [[[None, 1, None], 3, [[None, 4, None], 6, [None, 7, None]]], 8, [None, 10, [[None, 13, None], 14, None]]]
>>> imprime(arvore)
      1
   3
         4
      6
         7
8
   10
         13
      14

Busca em Árvores Binárias

Como era de se esperar né, uma árvore binária de busca serve para ... buscar coisas. Mas a grande diferença de uma árvore binária para outras estruturas de dados é que a operação de busca na árvore têm um desempenho muito melhor - O(log n) na média, e O(n) no pior caso, quando a árvore se comporta como uma lista encadeada.

A busca pelo nosso valor começa à partir do nó raiz. Se a árvore for nula, significa que o valor que estamos procurando não existe na árvore. Caso a árvore não seja nula, se o valor for igual ao da raiz, a busca obteve sucesso. Se o valor é menor que o da raiz, a busca deve continuar pela sub-árvore da esquerda. Da mesma forma, se o valor é maior que o da raiz, a busca deve continuar na sub-árvore da direita. Esse processo é repetido até que o valor seja encontrado ou que a árvore indicada seja nula.

Para nossa implementação, um único ponto deve ser levado em consideração. Da forma como implementamos nossa árvore binária, os nós folha (nós que não possuam sub-árvores) são representados por uma lista com itens nulos, conforme falamos antes. Por isso, o algoritmo de busca deverá levar isso em consideração:

@todosnaonulos
def busca(arvore, val):
    if val < valor(arvore):
        return busca(arvore[ESQ], val)
    elif val > valor(arvore):
        return busca(arvore[DIR], val)
    else:
        return arvore

Aqui fizemos uma implementação recursiva da função de busca, que chama a si mesma cada vez que precisa continuar a busca nas sub-árvores.

@todosnaonulos
def existe(arvore, val):
    _prox = arvore
    while _prox is not None:
        if val < valor(_prox):
            _prox = _prox[ESQ]
        elif val > valor(_prox):
            _prox = _prox[DIR]
        else:
            return True
    return False

Aqui fizemos uma implementação interativa (sem recursão, usando um laço de repetição) que percorre a árvore atrás do valor informado e retorna True se o valor estiver na árvore.

As duas funções fazem a mesma coisa, com a diferença que a primeira retorna o nó caso o encontre e a segunda retorna True. Caso não encontrem retornam, respectivamente, None e False.

Inserção

A inserção não difere muito de uma busca. Se a raiz não for igual ao valor que queremos inserir, nós percorremos as sub-árvores da esquerda ou da direita, de acordo com o modo que fizemos com a busca. Eventualmente, vamos alcançar um nó folha e então iremos adicionar o valor, à esquerda ou à direita, dependendo do valor do nó. Em outras palavras, nós examinamos a raiz e recursivamente inserimos o novo nó ao chegarmos a um nó vazio.

Assim, vamos implementar, levando em consideração nosso caso específico de implementação:

@todosnaonulos
def cria_no(val):
    return [None, val, None]

@todosnaonulos
def insere(arvore, val):
    if len(arvore) == 0:
        #Caso a lista esteja vazia, a função cria o nó na lista.
        arvore.append(None)
        arvore.append(val)
        arvore.append(None)
    elif val < valor(arvore):
        if arvore[ESQ] is None:
            arvore[ESQ] = cria_no(val)
        else:
            insere(arvore[ESQ], val)
    elif val > valor(arvore):
        if arvore[DIR] is None:
            arvore[DIR] = cria_no(val)
        else:
            insere(arvore[DIR], val)

Nessa nossa função, nós inserimos a nova informação utilizando a árvore original como base para reconstruirmos uma nova, sem que com isso alteremos a árvore original. Qualquer referência à árvore original continua válida, tornando a árvore uma estrutura de dados persistente. A reconstrução da árvore nesse código executa em O(log n) nos casos médios e O(n) no pior cenário.

Remover

Remover um item de uma árvore é a operação mais dispendiosa em termos de código (não em execução) de uma árvore, já que temos de tratar três casos especiais de configurações de nós: Nós sem filhos, Nós com somente um filho e Nós com dois filhos.

  • Nó sem filhos: Deletar um nó sem filhos é simples. Você precisa somente apagar sua referência no nó pai, sem haver processamento adicional.
  • Nó com um filho: Para deletar um nó com somente um filho, você remove o nó e substitui ele pelo seu filho na referência do pai.
  • Nó com dois filhos: Para deletar um nó com dois filhos, o processo é um pouco mais complexo. Primeiramente, precisamos encontrar o nó que irá substituir o nó que estamos deletando. Esse nó deverá ser o seu sucessor ou antecessor dentro da árvore. O sucessor ou o antecessor são fáceis de encontrar: O sucessor é o nó mais à esquerda da sub-árvore direita, e o antecessor o nó mais à direita da sub-arvore da esquerda. Em ambos os casos, esse nó será um nó sem filhos ou com somente um filho. Depois de encontrarmos o nó que irá substituí-lo, nós copiamos o valor desse nó para o nó que está sendo removido, e caso o nó sucessor/antecessor possua um filho, ele deve ser passado para o nó pai do nó sucessor/antecessor.

Em vista dessa quantidade de operações dentro da operação de remover, eu adicionei várias outras funções para facilitar essa rotina e diminuir o tamanho do código da função de remover. Essas rotinas você encontrará no código final. Segue aí o código do remove!

@todosnaonulos
def remove(arvore, val, suc_substitui=True):
    def _remove(original, arvore, val):
        if val < valor(arvore):
            _remove(original, arvore[ESQ], val)
        elif val > valor(arvore):
            _remove(original, arvore[DIR], val)
        else:
            if arvore[ESQ] is not None and arvore[DIR] is not None:
                #Nó com dois filhos
                _subst = sucessor(arvore) if suc_substitui else antecessor(arvore)
                _subst_pai = pai(original, _subst)
                arvore[VALOR] = valor(_subst)
                if suc_substitui:
                    if _subst_pai is not arvore:
                        _subst_pai[ESQ] = _subst[DIR]
                    else:
                        _subst_pai[DIR] = _subst[DIR]
                else:
                    if _subst_pai is not arvore:
                        _subst_pai[DIR] = _subst[ESQ]
                    else:
                        _subst_pai[ESQ] = _subst[ESQ]
            elif arvore[ESQ] is not None or arvore[DIR] is not None:
                #Nó com um filho
                if arvore[ESQ] is not None:
                    arvore[VALOR] = arvore[ESQ][VALOR]
                    arvore[DIR] = arvore[ESQ][DIR]
                    arvore[ESQ] = arvore[ESQ][ESQ]
                else:
                    arvore[VALOR] = arvore[DIR][VALOR]
                    arvore[ESQ] = arvore[DIR][ESQ]
                    arvore[DIR] = arvore[DIR][DIR]
            else:
                #Nó sem nenhum filho
                if arvore is original:
                    #Caso a árvore seja o último elemento, remove-se os itens da
                    #lista ao invés de tentar remover seus filhos (inexistentes).
                    arvore.pop()
                    arvore.pop()
                    arvore.pop()
                else:
                    _pai = pai(original, arvore)
                    if _pai[ESQ] is arvore:
                        _pai[ESQ] = None
                    else:
                        _pai[DIR] = None
    if not existe(arvore, val): return None
    _remove(arvore, arvore, val)

Perceba que eu criei uma outra função dentro da primeira. Isso foi necessário pois para eu conseguir recuperar a referência do pai do nó em uma função recursiva, precisaria ter a referência à arvore original. Então, a função de dentro simplesmente passa a árvore duas vezes como referência, sendo que o parâmetro original não é alterado, ao passo que o arvore sim. Daí, na hora de encontrar o pai de um nó, essa referência é utilizada. Essa função, apesar de mais longa na implementação, também executa em O(log n) no caso médio e O(n) no pior cenário.

Outras operações com Árvores

Percorrer

Depois que uma árvore binária foi criada, seus elementos podem ser recuperados em ordem através do processo de percorrer toda a árvore à partir da raiz, e então ir percorrendo recursivamente cada uma das sub-árvores, continuando nesse processo até que toda a árvore tenha sido percorrida. Aqui inserimos uma característica nova. Para cada elemento que o percorrimento retornar, uma função é chamada e têm o elemento passado como parâmetro. Veja abaixo:

@todosnaonulos
def percorre(arvore, func):
    if arvore is not None:
        percorre(arvore[ESQ], func)
        func(valor(arvore))
        percorre(arvore[DIR], func)

Ordenar

Várias operações podem ser feitas usando árvores binárias de busca. Podemos citar, por exemplo, algoritmos de ordenação. O HeapSort é um desses algoritmos que usam uma árvore para fazer a ordenação de uma lista de valores. No entanto, ao invés de usar uma árvore binária de busca, o algoritmo usa um tipo de árvore chamada Heap, onde a ordem dos elementos é diferente. Usando uma árvore binária de busca, temos um código de ordenação um pouco melhor, já que a ordenação é feita na medida que os objetos entram na árvore. No entanto, devido essa necessidade de se adicionar o item ordenadamente à cada inserção, essa estrutura acaba não sendo a melhor escolha para ordenação. Aqui, temos um exemplo de como usaríamos a árvore para ordenar. Veja o exemplo:

@todosnaonulos
def organiza(valores):
    _arvore = None
    if valores is not None:
        _arvore = []
        for _v in valores:
            insere(_arvore, _v)
        _res = []
        percorre(_arvore, lambda valor: _res.append(valor))
        return _res

Conclusão

Árvores binárias são uma estrutura realmente fascinante quando pensamos em busca de informações, pois elas nos permitem acesso extremamente rápido, independente da quantidade de itens na árvore. Mesmo em situações onde a quantidade de itens pode passar dos milhões, as árvores oferecem uma alternativa viável ao problema da organização de tais dados.

Quanto ao comentário no início do post, realmente não deu tempo de falar das árvores AVL e Red Black, e isso vai ficar pra um post futuro. Mas, esse vou fazer com mais calma e tranquilidade, já que esse daqui ficou bem completo e já ajuda bastante nos seus estudos de estruturas de dados, não é mesmo?

Um abraço pra vcs todos!

Segue abaixo o código completo, que pode ser baixado também do Pastebin.com, com todo o Syntax Highlight habilitado hehehehe:

#!/usr/bin/env python
# -*- coding: utf-8 -*-

"""Exemplos de implementação de Árvores Binárias de Busca em Python

Autor: Eduardo Rolim
Blog: www.tocadoelfo.com.br

Descrição: Módulo contendo várias rotinas de manipulação de árvores binárias de
busca simples e balanceadas.
A implementação utiliza listas em Python para servir como nó, e todas as funções
funcionam utilizando este modelo.
"""

# Variáveis de contexto para os índices da lista: [ESQ, VALOR, DIR]
ESQ = 0
VALOR = 1
DIR = 2

class todosnaonulos(object):
    """Decorador de função utilizado para verificar se todos os parâmetros passados
    para a função decorada são não-nulos. Caso algum deles seja nulo, a função
    decorada não é executada e retorna None.
    """
    def __init__(self, f):
        self.f = f
    
    def __call__(self, *args, **kwargs):
        for arg in args:
            if arg is None:
                return None
        retorno = self.f(*args, **kwargs)
        return retorno

############# Funções comuns à todas as árvores binárias de busca #############

@todosnaonulos
def valor(no):
    """Função que recupera o valor armazenado no nó.
    """
    return no[VALOR]

@todosnaonulos
def imprime(arvore, identacao = 0):
    """Função para imprimir visualmente a árvore no terminal.
    """
    if type(arvore) == list:
        imprime(arvore[ESQ], identacao + 3)
        print " " * identacao + str(valor(arvore))
        imprime(arvore[DIR], identacao + 3)
    elif arvore is not None:
            print " " * identacao + str(arvore)

@todosnaonulos
def busca(arvore, val):
    """Função para retornar o nó correspondente ao valor informado.
    """
    if val < valor(arvore):
        return busca(arvore[ESQ], val)
    elif val > valor(arvore):
        return busca(arvore[DIR], val)
    else:
        return arvore

@todosnaonulos
def existe(arvore, val):
    """Função para verificar a existência de um valor na árvore.
    """
    _prox = arvore
    while _prox is not None:
        if val < valor(_prox):
            _prox = _prox[ESQ]
        elif val > valor(_prox):
            _prox = _prox[DIR]
        else:
            return True
    return False

def insere_alt(arvore, val):
    """Função para inserir novos itens na árvore.
    ### A cada inserção, essa função recria a árvore ###
    """
    if arvore is None:
        return [None, val, None]
    else:
        if val < valor(arvore):
            return [insere(arvore[ESQ], val), valor(arvore), arvore[DIR]]
        elif val > valor(arvore):
            return [arvore[ESQ], valor(arvore), insere(arvore[DIR], val)]
        else:
            return arvore

@todosnaonulos
def cria_no(val):
    """Função que cria um nó com valor já setado.
    """
    return [None, val, None]

@todosnaonulos
def insere(arvore, val):
    """Função para inserir novos itens na árvore. Caso a lista esteja vazia, ela
    é populada inicialmente com o valor e os dois nós vazios.
    """
    if len(arvore) == 0:
        #Caso a lista esteja vazia, a função cria o nó na lista.
        arvore.append(None)
        arvore.append(val)
        arvore.append(None)
    elif val < valor(arvore):
        if arvore[ESQ] is None:
            arvore[ESQ] = cria_no(val)
        else:
            insere(arvore[ESQ], val)
    elif val > valor(arvore):
        if arvore[DIR] is None:
            arvore[DIR] = cria_no(val)
        else:
            insere(arvore[DIR], val)

@todosnaonulos
def menor(arvore):
    """Função que retorna o menor nó dentro da árvore informada.
    """
    _no = arvore[ESQ]
    if _no is not None:
        while _no[ESQ] is not None:
            _no = _no[ESQ]
    else: 
        _no = arvore
    return _no

@todosnaonulos
def maior(arvore):
    """Função que retorna o maior nó dentro da árvore informada.
    """
    _no = arvore[DIR]
    if _no is not None:
        while _no[DIR] is not None:
            _no = _no[DIR]
    else: 
        _no = arvore
    return _no

@todosnaonulos
def antecessor(arvore):
    """Função que retorna o antecessor do nó atual. O antecessor é o maior nó
    dentro da sub-árvore da esquerda (que contém todos os nós menores que o atual)
    """
    return maior(arvore[ESQ])

@todosnaonulos
def sucessor(arvore):
    """Função que retorna o sucessor do nó atual. O sucessor é o menor nó dentro
    da sub-árvore da direita (que contém todos os nós maiores que o atual)
    """
    return menor(arvore[DIR])

@todosnaonulos
def pai(arvore, no):
    """Função que retorna o nó pai do nó atual, buscando o mesmo através da árvore.
    """
    if not existe(arvore, valor(no)): return None
    _filho = arvore
    _pai = None
    while _filho is not None and valor(_filho) != valor(no):
        _pai = _filho
        if valor(no) < valor(_filho):
            _filho = _filho[ESQ]
        elif valor(no) > valor(_filho):
            _filho = _filho[DIR]
    return _pai

@todosnaonulos
def remove(arvore, val, suc_substitui=True):
    """Função que remove um determinado valor de dentro da árvore.
    Existem três casos relacionados à remoção:
    - Nó sem filhos: Remove o nó da árvore (apaga sua referência no nó pai);
    - Nó com um filho: Remove o nó da árvore e o substitui pelo seu filho;
    - Nó com dois filhos: Não delete o nó. Em vez disso, deve-se procurar o nó
      sucessor ou antecessor, substituir o valor do mesmo no lugar do valor
      do nó, então deleta-se o sucessor ou antecessor.
      * A opção 'suc_substitui' determina se vai ser usado o sucessor ou o
        antecessor.
    """
    def _remove(original, arvore, val):
        """Função interna que duplica o parâmetro árvore de forma a possibilitar
        a utilização da função pai() dentro das chamadas recursivas da função.
        """
        if val < valor(arvore):
            _remove(original, arvore[ESQ], val)
        elif val > valor(arvore):
            _remove(original, arvore[DIR], val)
        else:
            if arvore[ESQ] is not None and arvore[DIR] is not None:
                #Nó com dois filhos
                _subst = sucessor(arvore) if suc_substitui else antecessor(arvore)
                _subst_pai = pai(original, _subst)
                arvore[VALOR] = valor(_subst)
                if suc_substitui:
                    if _subst_pai is not arvore:
                        _subst_pai[ESQ] = _subst[DIR]
                    else:
                        _subst_pai[DIR] = _subst[DIR]
                else:
                    if _subst_pai is not arvore:
                        _subst_pai[DIR] = _subst[ESQ]
                    else:
                        _subst_pai[ESQ] = _subst[ESQ]
            elif arvore[ESQ] is not None or arvore[DIR] is not None:
                #Nó com um filho
                if arvore[ESQ] is not None:
                    arvore[VALOR] = arvore[ESQ][VALOR]
                    arvore[DIR] = arvore[ESQ][DIR]
                    arvore[ESQ] = arvore[ESQ][ESQ]
                else:
                    arvore[VALOR] = arvore[DIR][VALOR]
                    arvore[ESQ] = arvore[DIR][ESQ]
                    arvore[DIR] = arvore[DIR][DIR]
            else:
                #Nó sem nenhum filho
                if arvore is original:
                    #Caso a árvore seja o último elemento, remove-se os itens da
                    #lista ao invés de tentar remover seus filhos (inexistentes).
                    while len(arvore) > 0:
                        arvore.pop()
                else:
                    _pai = pai(original, arvore)
                    if _pai[ESQ] is arvore:
                        _pai[ESQ] = None
                    else:
                        _pai[DIR] = None
    if not existe(arvore, val): return None
    _remove(arvore, arvore, val)

@todosnaonulos
def percorre(arvore, func):
    """Função que percorre a árvore retornando seus elementos em ordem crescente.
    """
    if arvore is not None:
        percorre(arvore[ESQ], func)
        func(valor(arvore))
        percorre(arvore[DIR], func)

@todosnaonulos
def organiza(valores):
    """Função que utiliza uma árvore para fazer ordenação dos elementos.
    Funciona de maneira próxima ao HeapSort, com a exceção de que nesse algoritmo,
    a árvore está implicitamente implementada, ao contrário dessa implementação.
    """
    _arvore = None
    if valores is not None:
        _arvore = []
        for _v in valores:
            insere(_arvore, _v)
        _res = []
        percorre(_arvore, lambda valor: _res.append(valor))
        return _res

def caso_cria():
    tree = cria_no(8)
    insere(tree, 2)
    insere(tree, 1)
    insere(tree, 6)
    insere(tree, 4)
    insere(tree, 7)
    insere(tree, 3)
    insere(tree, 10)
    insere(tree, 14)
    insere(tree, 13)
    insere(tree, 5)
    return tree

Fontes:

Wikipédia
Universidade de Kent
Universidade de Stanford