Rvore Bin Ria

Árvore binária

Definição

Uma árvore binária é uma estrutura de dados na qual cada nó tem até dois nós filhos, (existem também as árvores estritamente binárias, a qual nenhum nó possui um nó filho único), mas ambas árvores tem nós filhos cujos nomes geralmente é distinguido como sub-árvore esquerda e sub-árvore direita. Nós com filhos são nós pai e nós filhos podem conter referência à seus pais. Muitas vezes há uma referência para o nó root (o antepassado de todos nós), se ele existir. Qualquer nó nessa estrutura pode ser alcançado, iniciando no nó root e seguindo repetidamente referências dos filhos esquerdo ou direito. Uma árvore que não possui nenhum outro nó além do nó root é chamada de árvore nula.

Se cada nó pai pode ter até duas ligações (uma com cada nó filho) e cada nó filho pode ter apenas uma ligação (com seu pai), então o número total de ligações da árvore é o número de nós da árvore subtraído por um. Estas ligações são chamadas de graus.

Árvores binárias são usadas para implementar árvores de busca binária, aplicações eficientes de busca e algoritmos de ordenação.
Operações comuns

Existem uma variedade de diferentes operações que podem ser feitas numa árvore binária, foram selecionadas três delas:
Inserção

Através de função recursiva um nó é inserido na árvore adequadamente. Considerando a estrutura a seguir:

typedef struct tag_node { uint32_t data; struct tag_node *left, *right;
} node_t, *nodeptr_t;

O algoritmo de inserção funciona da seguinte forma:

nodeptr_t insert(nodeptr_t node, uint32_t data) { /* se a árvore não estiver vazia, percorre a árvore */ if(node) { if(data <= node->data) node->left = insert(node->left, data); else node->right = insert(node->right, data); return node; /* retorna o ponteiro node inalterado */ }

/* caso contrário, retorna um novo nó */ nodeptr_t node = calloc(1, sizeof node_t); node->data = data; node->left = node->right = 0; return node;
}

Remoção

O algoritmo de remoção de