Pergunta

Já vi árvores binárias e busca binária mencionadas em vários livros que li ultimamente, mas como ainda estou no início dos meus estudos em Ciência da Computação, ainda não fiz uma aula que realmente tratasse de algoritmos e dados estruturas de uma forma séria.

Eu verifiquei as fontes típicas (Wikipedia, Google) e a maioria das descrições da utilidade e implementação de (em particular) árvores Vermelho-Pretas parecem densas e difíceis de entender.Tenho certeza de que para alguém com a formação necessária, faz todo o sentido, mas no momento parece quase uma língua estrangeira.

Então, o que torna as árvores binárias úteis em algumas das tarefas comuns que você realiza durante a programação?Além disso, quais árvores você prefere usar (inclua um exemplo de implementação) e por quê?

Foi útil?

Solução

As árvores Red Black são boas para criar árvores bem equilibradas.O maior problema com as árvores de pesquisa binária é que você pode desequilibrá-las com muita facilidade.Imagine que seu primeiro número seja 15.Então, todos os números seguintes serão cada vez menores que 15.Você terá uma árvore muito pesada do lado esquerdo e nada do lado direito.

As árvores Red Black resolvem isso forçando sua árvore a ficar equilibrada sempre que você insere ou exclui.Isso é feito por meio de uma série de rotações entre nós ancestrais e nós filhos.O algoritmo é bastante simples, embora seja um pouco longo.Eu sugiro pegar o livro CLRS (Cormen, Lieserson, Rivest e Stein), "Introdução aos Algoritmos" e ler sobre Árvores RB.

A implementação também não é tão curta, então provavelmente não é melhor incluí-la aqui.No entanto, as árvores são usadas extensivamente para aplicativos de alto desempenho que precisam de acesso a muitos dados.Eles fornecem uma maneira muito eficiente de encontrar nós, com uma sobrecarga relativamente pequena de inserção/exclusão.Novamente, sugiro consultar o CLRS para saber como eles são usados.

Embora os BSTs possam não ser usados ​​explicitamente - um exemplo do uso de árvores em geral está em quase todos os RDBMS modernos.Da mesma forma, seu sistema de arquivos é quase certamente representado como algum tipo de estrutura em árvore, e os arquivos também são indexados dessa forma.As árvores alimentam o Google.As árvores alimentam quase todos os sites da Internet.

Outras dicas

Eu gostaria de abordar apenas a questão "Então, o que torna as árvores binárias úteis em algumas das tarefas comuns que você realiza durante a programação?"

Este é um grande tópico sobre o qual muitas pessoas discordam.Alguns dizem que os algoritmos ensinados em um curso de ciência da computação, como árvores de busca binária e gráficos direcionados, não são usados ​​na programação do dia-a-dia e, portanto, são irrelevantes.Outros discordam, dizendo que esses algoritmos e estruturas de dados são a base de toda a nossa programação e é essencial entendê-los, mesmo que você nunca precise escrever um para si mesmo.Isso se transforma em conversas sobre boas práticas de entrevista e contratação.Por exemplo, Steve Yegge tem um artigo sobre entrevistando no Google que aborda esta questão.Lembre-se deste debate;pessoas experientes discordam.

Na programação empresarial típica, talvez você não precise criar árvores binárias ou mesmo árvores com muita frequência.No entanto, você usará muitas classes que operam internamente usando árvores.Muitas das principais classes de organização em todas as linguagens usam árvores e hashes para armazenar e acessar dados.

Se você estiver envolvido em empreendimentos de alto desempenho ou em situações que estejam um pouco fora dos padrões da programação de negócios, você descobrirá que as árvores são suas amigas imediatas.Como disse outro postador, as árvores são estruturas de dados essenciais para bancos de dados e índices de todos os tipos.Eles são úteis na mineração e visualização de dados, gráficos avançados (2D e 3D) e em uma série de outros problemas computacionais.

Eu usei árvores binárias na forma de Árvores BSP (particionamento de espaço binário) em gráficos 3D.Atualmente estou analisando árvores novamente para classificar grandes quantidades de dados geocodificados e outros dados para visualização de informações em aplicativos Flash/Flex.Sempre que você estiver ultrapassando os limites do hardware ou quiser executar com especificações de hardware mais baixas, compreender e selecionar o melhor algoritmo pode fazer a diferença entre o fracasso e o sucesso.

Nenhuma das respostas menciona exatamente para que servem os BSTs.

Se o que você deseja fazer é apenas pesquisar por valores, uma tabela hash é muito mais rápida, inserção e pesquisa O(1) (melhor caso amortizado).

Um BST será uma pesquisa O (log N), onde N é o número de nós na árvore, as inserções também são O (log N).

As árvores RB e AVL são importantes como outra resposta mencionada por causa desta propriedade, se um BST simples for criado com valores em ordem, a árvore será tão alta quanto o número de valores inseridos, o que é ruim para o desempenho da pesquisa.

A diferença entre as árvores RB e AVL está nas rotações necessárias para reequilibrar após uma inserção ou exclusão, as árvores AVL são O(log N) para rebalanceamentos enquanto as árvores RB são O(1).Um exemplo do benefício dessa complexidade constante é um caso em que você pode manter uma fonte de dados persistente; se precisar rastrear alterações para reversão, você terá que rastrear O (log N) possíveis alterações com uma árvore AVL.

Por que você estaria disposto a pagar pelo custo de uma árvore em uma tabela hash?ORDEM!As tabelas hash não têm ordem; os BSTs, por outro lado, são sempre ordenados naturalmente em virtude de sua estrutura.Portanto, se você estiver jogando um monte de dados em um array ou outro contêiner e depois os classificando, um BST pode ser uma solução melhor.

A propriedade order da árvore oferece vários recursos de iteração ordenada, em ordem, em profundidade, em largura, pré-encomenda e pós-ordem.Esses algoritmos de iteração são úteis em diferentes circunstâncias se você quiser procurá-los.

Árvores vermelhas e pretas são usadas internamente em quase todos os contêineres ordenados de bibliotecas de linguagem, C++ Set and Map, .NET SortedDictionary, Java TreeSet, etc...

Portanto, as árvores são muito úteis e você pode usá-las com frequência, mesmo sem saber.Você provavelmente nunca precisar você mesmo, embora eu o recomende fortemente como um exercício de programação interessante.

Árvores Red Black e árvores B são usadas em todos os tipos de armazenamento persistente;como as árvores estão equilibradas, o desempenho das travessias em largura e profundidade é mitigado.

Quase todos os sistemas de banco de dados modernos usam árvores para armazenamento de dados.

Os BSTs fazem o mundo girar, como disse Micheal.Se você está procurando uma boa árvore para implementar, dê uma olhada em Árvores AVL (Wikipédia).Eles têm uma condição de balanceamento, portanto é garantido que sejam O(logn).Esse tipo de eficiência de pesquisa torna lógico colocá-lo em qualquer tipo de processo de indexação.A única coisa que seria mais eficiente seria uma função de hashing, mas elas ficam feias rapidamente, rapidamente e com pressa.Além disso, você se depara com o Paradoxo do Aniversário (também conhecido como problema do pombo).

Que livro você está usando?Nós costumavamos Estruturas e análises de dados em Java por Mark Allen Weiss.Na verdade, estou com ele aberto no colo enquanto digito isso.Tem uma ótima seção sobre árvores Rubro-Negras, e ainda inclui o código necessário para implementar todas as árvores de que fala.

As árvores rubro-negras permanecem equilibradas, então você não precisa se aprofundar para retirar os itens.O tempo economizado torna as árvores RB O(log()n)) no PIOR caso, enquanto as árvores binárias azaradas podem entrar em uma configuração desequilibrada e causar recuperações em O(n) um caso ruim.Isso acontece na prática ou em dados aleatórios.Portanto, se você precisar de código crítico em termos de tempo (recuperações de banco de dados, servidor de rede, etc.), use árvores RB para oferecer suporte a listas/conjuntos ordenados ou não ordenados.

Mas RBTrees são para novatos!Se você estiver fazendo IA e precisar realizar uma pesquisa, você descobrirá que bifurca muitas informações de estado.Você pode usar um vermelho-preto persistente para bifurcar novos estados em O(log(n)).Uma árvore vermelho-preta persistente mantém uma cópia da árvore antes e depois de uma operação morfológica (inserir/excluir), mas sem copiar a árvore inteira (normalmente e operação O(log(n))).Eu abri o código-fonte de uma árvore vermelho-preta persistente para java

http://edinburghhacklab.com/2011/07/a-java-implementation-of-persistent-red-black-trees-open-sourced/

A melhor descrição de árvores rubro-negras que vi é aquela em 'Introdução aos Algoritmos' de Cormen, Leisersen e Rivest.Eu poderia até entender o suficiente para implementar parcialmente um (apenas inserção).Existem também alguns miniaplicativos, como Este em várias páginas da web que animam o processo e permitem observar e percorrer uma representação gráfica do algoritmo que constrói uma estrutura em árvore.

Já que você pergunta qual árvore as pessoas usam, você precisa saber que uma árvore Red Black é fundamentalmente uma árvore B 2-3-4 (ou seja, uma árvore B de ordem 4).Uma árvore B é não equivalente a uma árvore binária (conforme perguntado na sua pergunta).

Aquié um excelente recurso que descreve a abstração inicial conhecida como árvore B binária simétrica que mais tarde evoluiu para o RBTree.Você precisaria de um bom domínio das árvores B antes que fizesse sentido.Para resumir:um link 'vermelho' em uma árvore Red Black é uma forma de representar nós que fazem parte de um nó de árvore B (valores dentro de um intervalo de chaves), enquanto links 'pretos' são nós que estão conectados verticalmente em uma árvore B.

Então, aqui está o que você obtém quando traduz as regras de uma árvore Red Black em termos de uma árvore B (estou usando o formato Regra da árvore rubro-negra => Equivalente à árvore B):

1) Um nó é vermelho ou preto.=> Um nó em uma árvore b pode fazer parte de um nó ou ser um nó em um novo nível.

2) A raiz é preta.(Esta regra às vezes é omitida, pois não afeta a análise) => O nó raiz pode ser considerado parte de um nó raiz interno ou filho de um nó pai imaginário.

3) Todas as folhas (NIL) são pretas.(Todas as folhas têm a mesma cor da raiz.) => Como uma forma de representar uma árvore RB é omitindo as folhas, podemos descartar isso.

4) Ambos os filhos de cada nó vermelho são pretos.=> Os filhos de um nó interno em uma árvore B sempre estão em outro nível.

5) Cada caminho simples de um determinado nó até qualquer uma de suas folhas descendentes contém o mesmo número de nós pretos.=> Uma árvore B é mantida equilibrada, pois requer que todos os nós folha estejam na mesma profundidade (portanto, a altura de um nó da árvore B é representada pelo número de links pretos da raiz até a folha de uma árvore Red Black )

Além disso, há uma implementação 'não padrão' mais simples de Robert Sedgewick aqui:(Ele é o autor do livro Algoritmos junto com Wayne)

Muito calor aqui, mas pouca luz, então vamos ver se podemos fornecer alguma.

Primeiro, uma árvore RB é uma estrutura de dados associativa, ao contrário, digamos, de um array, que não pode pegar uma chave e retornar um valor associado, bem, a menos que seja uma "chave" inteira em um índice esparso de 0% de inteiros contíguos.Um array também não pode crescer em tamanho (sim, eu também sei sobre realloc(), mas nos bastidores isso requer um novo array e depois um memcpy()), então se você tiver algum desses requisitos, um array não servirá .A eficiência da memória de um array é perfeita.Desperdício zero, mas não muito inteligente ou flexível - apesar de realloc().

Segundo, em contraste com um bsearch() em uma matriz de elementos, que É uma estrutura de dados associativa, uma árvore RB pode aumentar (E diminuir) de tamanho dinamicamente.O bsearch() funciona bem para indexar uma estrutura de dados de tamanho conhecido, que permanecerá desse tamanho.Portanto, se você não sabe o tamanho dos seus dados com antecedência ou se novos elementos precisam ser adicionados ou excluídos, bsearch() está fora de questão.Bsearch() e qsort() são bem suportados no C clássico e têm boa eficiência de memória, mas não são dinâmicos o suficiente para muitos aplicativos.Eles são meus favoritos porque são rápidos, fáceis e, se você não estiver lidando com aplicativos em tempo real, muitas vezes são flexíveis o suficiente.Além disso, em C/C++ você pode classificar uma matriz de ponteiros para registros de dados, apontando para o membro struc{}, por exemplo, que deseja comparar e, em seguida, reorganizar o ponteiro na matriz de ponteiros de modo que a leitura dos ponteiros em ordem no final do ponteiro, a classificação produz seus dados em ordem de classificação.Usar isso com arquivos de dados mapeados na memória é extremamente eficiente em termos de memória, rápido e bastante fácil.Tudo o que você precisa fazer é adicionar alguns "*" às suas funções de comparação.

Terceiro, em contraste com uma tabela hash, que também deve ter um tamanho fixo e não pode ser cultivada depois de preenchida, uma árvore RB crescerá automaticamente e se equilibrará para manter sua garantia de desempenho O(log(n)).Especialmente se a chave da árvore RB for um int, ela pode ser mais rápida que um hash, porque mesmo que a complexidade de uma tabela hash seja O(1), esse 1 pode ser um cálculo de hash muito caro.As comparações múltiplas de inteiros de 1 clock de uma árvore geralmente superam os cálculos de hash de 100 clocks ou mais, para não falar de rehashing e malloc()ing espaço para colisões de hash e rehashes.Por fim, se você deseja acesso ISAM, bem como acesso de chave aos seus dados, um hash é descartado, pois não há ordenação dos dados inerente à tabela hash, em contraste com a ordenação natural dos dados em qualquer implementação de árvore.O uso clássico de uma tabela hash é fornecer acesso com chave a uma tabela de palavras reservadas para um compilador.A eficiência da memória é excelente.

Quarto, e muito inferior em qualquer lista, está a lista vinculada, ou duplamente vinculada, que, em contraste com uma matriz, suporta naturalmente inserções e exclusões de elementos e, como isso implica, redimensionamento.É a mais lenta de todas as estruturas de dados, pois cada elemento só sabe como chegar ao próximo elemento, então você tem que pesquisar, em média, links (element_knt/2) para encontrar seu dado.É usado principalmente onde inserções e exclusões em algum lugar no meio da lista são comuns e, principalmente, onde a lista é circular e alimenta um processo caro que torna o tempo de leitura dos links relativamente pequeno.Meu RX geral é usar um array arbitrariamente grande em vez de uma lista vinculada se seu único requisito for que ele seja capaz de aumentar de tamanho.Se você ficar sem tamanho com um array, poderá realloc() um array maior.O STL faz isso "nos bastidores" quando você usa um vetor.Rude, mas potencialmente milhares de vezes mais rápido se você não precisar de inserções, exclusões ou pesquisas com chave.A eficiência da memória é baixa, especialmente para listas duplamente vinculadas.Na verdade, uma lista duplamente vinculada, que requer dois ponteiros, é exatamente tão ineficiente em termos de memória quanto uma árvore vermelha e preta, embora não tenha NENHUMA de suas características de recuperação ordenada e rápida.

Quinto, as árvores suportam muitas operações adicionais em seus dados classificados do que qualquer outra estrutura de dados.Por exemplo, muitas consultas de banco de dados fazem uso do fato de que um intervalo de valores de folha pode ser facilmente especificado especificando seu pai comum e, em seguida, concentrando o processamento subsequente na parte da árvore que o pai "possui".O potencial para multi-threading oferecido por esta abordagem deveria ser óbvio, já que apenas uma pequena região da árvore precisa ser bloqueada - ou seja, apenas os nós que o pai possui e o próprio pai.

Resumindo, as árvores são o Cadillac das estruturas de dados.Você paga um preço alto em termos de memória usada, mas obtém uma estrutura de dados totalmente autossustentável.É por isso que, como apontado em outras respostas aqui, os bancos de dados de transações usam quase exclusivamente árvores.

Se você quiser ver como uma árvore Vermelho-Preta deve parecer graficamente, codifiquei uma implementação de uma árvore Vermelho-Preta que você pode baixe aqui

IME, quase ninguém entende o algoritmo da árvore RB.As pessoas podem repetir as regras para você, mas não entendem por que essas regras e de onde elas vêm.Eu não sou exceção :-)

Por esta razão, prefiro o algoritmo AVL, porque é fácil de compreender.Depois de entendê-lo, você poderá codificá-lo do zero, porque faz sentido para você.

As árvores podem ser rápidas.Se você tiver um milhão de nós em uma árvore binária balanceada, serão necessárias, em média, vinte comparações para encontrar qualquer item.Se você tiver um milhão de nós em uma lista vinculada, serão necessárias, em média, quinhentas mil comparações para encontrar o mesmo item.

Porém, se a árvore estiver desequilibrada, ela pode ser tão lenta quanto uma lista, e também leva mais memória para armazenar.Imagine uma árvore onde a maioria dos nós tem um filho direito, mas nenhum filho esquerdo;isto é uma lista, mas você ainda precisa manter espaço de memória para colocar no nó esquerdo, se algum aparecer.

De qualquer forma, o Árvore AVL foi o primeiro algoritmo de árvore binária balanceada, e o artigo da Wikipedia sobre ele é bastante claro.O artigo da Wikipedia sobre árvores rubro-negras é claro como lama, honestamente.

Além das árvores binárias, as árvores B são árvores onde cada nó pode ter muitos valores.Árvore B é não uma árvore binária, por acaso é o nome dela.Eles são realmente úteis para utilizar a memória de forma eficiente;cada nó da árvore pode ser dimensionado para caber em um bloco de memória, para que você não encontre (lentamente) toneladas de coisas diferentes na memória que foram paginadas para o disco.Aqui está um exemplo fenomenal do Árvore B.

Licenciado em: CC-BY-SA com atribuição
Não afiliado a StackOverflow
scroll top