Definição – o que significa a árvore de pesquisa binária com autobalanceamento?
Uma árvore de pesquisa binária com autobalanceamento é um tipo de estrutura de dados que se autoajusta para fornecer níveis consistentes de acesso ao nó. Em uma árvore de busca binária de autobalanceamento, as conexões do nó superior para os nós adicionais são classificadas e reajustadas de forma que a árvore seja uniforme e as linhas de trajetória de busca para cada nó final sejam iguais em termos de comprimento.
Uma árvore de busca binária com equilíbrio automático também é conhecida como árvore balanceada ou árvore de busca binária com altura balanceada.
Definirtec explica a árvore de pesquisa binária com equilíbrio automático
Uma árvore de pesquisa binária em geral fornece uma estrutura de dados com um nó no topo e um ou dois nós conectados a ela em cada nível subsequente. As árvores de pesquisa binárias suportam três operações – os operadores podem inserir componentes, excluir componentes ou pesquisar alguns números ou outro conteúdo de nó. Parte do benefício das árvores de pesquisa binárias é que o sistema pode classificar para ignorar metade da árvore em todos os níveis, levando a cargas de trabalho de pesquisa mais eficientes.
O aspecto positivo de uma árvore de busca binária de autobalanceamento é que o acesso ao nó é igual – por exemplo, em vez de ter que dar cinco passos em um lado da árvore, ou três passos no outro lado da árvore, por causa do eu -estrutura de nó ajustada, a pesquisa iria apenas um certo número de etapas (n) para qualquer nó final dado. Isso é conseguido retirando conexões de nós individuais e substituindo-as por binárias para encurtar membros específicos da árvore.
A desvantagem de uma busca binária de auto-equilíbrio três é que ela só funciona se as conexões dos nós forem “agnósticas de nível” – em outras palavras, se um nó individual pode ser reajustado para um nível anterior, a fim de encurtar o galho da árvore . Por exemplo, se uma árvore de busca binária de auto-equilíbrio é composta com um determinado número no topo, e dois números subsequentes em cada lado, e há uma cadeia de três números adicionais com conexões de nó único, o ajuste da árvore colocaria o quinto nó junto com o terceiro nó em vez do quarto nó, de modo que o terceiro nó tem dois nós de conexão em vez de um. No entanto, se a estrutura de dados precisa identificar o conteúdo de um nó específico como sendo relacionado em um relacionamento pai / filho específico, ajustar esses nós para se adequar à uniformidade da estrutura de árvore não vai funcionar.