O que é uma árvore de pesquisa?

Uma árvore de pesquisa é uma estrutura de dados usada na programação de computadores para conter e organizar uma lista de dados.Cada árvore de pesquisa é composta por um conjunto ordenado de nós.Estes nós podem ser conectados a zero ou mais Os nós individuais contêm alguns dados, bem como links para outros nós. Os dados contidos nos nós da árvore geralmente são ordenados de alguma forma para permitir que algoritmos eficientes pesquisem, insira e remova nós com facilidade.

Os nós de uma árvore de pesquisa são descritos com quatro termos importantes: o topo de uma árvore, onde está localizado o primeiro nó, é chamado de raiz.Se um nó contém links para sub -nodes, esse nó é conhecido como pai.Nós que estão abaixo do pai são chamados filhos, e qualquer nó que não possui nós filhos é chamado de folha.Portanto, um nó raiz é identificado porque não possui um pai e os nós folha não terão filhos.

Um programa pode percorrer uma árvore em busca de dados iniciando em um nó específico, executando uma verificação condicional e, em seguida, movendo-se para o próximo nó lógico, se os dados necessários não estiverem presentes. Dependendo da estrutura de dados usada , essa pesquisa pode levar um tempo variável. Se a árvore de pesquisa estiver organizada durante o processo de adição e remoção de nós, a pesquisa poderá ser muito rápida. Quando uma árvore é montada aleatoriamente, não é classificado ou permite vários pais, a pesquisa pode demorar muito tempo.

Um fator que afeta o uso de árvores de pesquisa é a questão do equilíbrio.Uma árvore balanceada é aquela em que os filhos direito e esquerdo do nó raiz contêm a mesma profundidade de nós filhos ou estão dentro de uma contagem de um nó A profundidade de uma árvore é o número de nós da folha mais baixa de uma árvore até a raiz.Uma árvore desequilibrada pode ter todos os nós em apenas um lado ou ter todos os os nós dispostos de maneira linear, sem ramificações.Quando a profundidade de uma árvore aumenta, a velocidade dos algoritmos de pesquisa pode diminuir drasticamente.

Existem certos tipos de árvores de pesquisa que são descritas como auto balanceamento.Essas árvores usam operações como rotação de árvore para ajudar a manter o equilíbrio, preservando a ordem dos dados nas folhas. rotações em árvore podem tornar um programa mais lento ao adicionar e remover nós, isso é compensado pela velocidade na qual os dados podem ser recuperados.

Embora existam muitos tipos de árvores de pesquisa, a estrutura de dados da árvore mais comum é uma árvore de pesquisa binária.Este tipo de dados consiste em nós com zero a dois nós filhos.Há apenas um nó raiz, e todas as folhas da árvore são ordenadas da esquerda para a direita em valores crescentes de acordo com os dados que eles possuem.Muitos algoritmos existem para árvores de pesquisa binária que podem facilite os pedidos de dados.

Não há uma implementação padrão única para os nós da árvore de pesquisa.Os nós podem ser representados por uma ampla variedade de estruturas de dados.Arrays de arrays podem ser usados, pois podem multiplicar listas vinculadas. A árvore de pesquisa usa uma estrutura de dados personalizada projetada para ajudar na conclusão das operações necessárias solicitadas pelo programa.Algumas bibliotecas de programação padrão ainda incluem suas próprias implementações internas de árvores de pesquisa.