Os dados são geralmente armazenados em estruturas de árvore binária usando algoritmos especializados. Muitas vantagens derivam do armazenamento dos dados na estrutura em árvore . Por exemplo, procurar uma árvore binária ordenada é muito mais rápido do que a classificação de uma estrutura de dados seqüencial , como uma matriz . Uma estrutura de dados em árvore podem assumir diversos tipos de padrões durante o curso de acesso a dados e de modificação . Entender esses padrões podem ajudar você a criar melhores algoritmos para otimizar um algoritmo de árvore . Componentes básicos de uma árvore binária
Uma árvore binária consiste em nós , que armazenam dados e apontam para outros nós na árvore. O nó de raiz é o ponto de partida da árvore e ocupa o nível superior . Ele pode ter até dois filhos nós . Esses nós filhos também podem ter até dois filhos nós . O número de nós filhos de um dado nó é chamado o grau do nó . Um nó sem filhos e um grau de zero é chamado de folha . O comprimento nos gânglios do nó de raiz para o nó mais distante da folha é a altura da árvore . A profundidade de um nó é a distância a partir do nó de raiz para ele . Cada nó que tem a mesma profundidade é dito ser no mesmo nível .
Completa Binary Tree
Uma árvore binária completa é uma árvore em que cada nó tem exatamente dois ou zero de crianças. Em outras palavras , cada nó ou de dois filhos , ou uma folha . Um exemplo de uma árvore binária completa é a decisão Diagrama binário, ou BDD .
Perfeito Binary Tree
Uma árvore binária perfeito tem as mesmas propriedades do árvore binária completa , mas todos os nós folhas estão no mesmo nível , o que significa que a profundidade de todas as folhas é a mesma em uma árvore binária perfeito . Uma vez que também é uma árvore binária completa , todos os nós , exceto nós folha têm um grau de 2.
Árvore binária equilibrada
Uma árvore binária balanceada é aquela em que a profundidade de cada nó de folha é o mesmo ou é diferente de um valor de um . Adição e remoção de nós de uma árvore binária equilibrada pode desequilibrá-lo , de modo que uma série de ajustes chamados rotações deve ocorrer para reequilibrar a árvore. Mantendo uma árvore equilibrada garante que o tempo de busca médio para qualquer nó é o ideal. Sobrecarga significativa é necessária para manter o equilíbrio de uma árvore.
Degenerada Binary Tree
Uma árvore binária degenerada é aquele em que todos os nós , exceto o nó folha tem exatamente um nó filho . Tem as mesmas características de uma lista encadeada , o que aumenta o tempo de pesquisa para qualquer nó de uma quantidade considerável de desempenho . Por exemplo, considere um caso em que o nó que está sendo procurado é o nó folha . A árvore inteira deve ser percorrido a fim de encontrar esse nó. Com uma árvore binária equilibrada , encontrar um nó de folha apenas requer um número de percursos de nó igual à profundidade do nó de folha . Com árvores de grande porte , a diferença no desempenho pode ser significativo.
