Não há problema em não entender completamente as árvores RB? [fechadas]

15

Então eu só aprendi árvores negras vermelhas em Cormen e uau! Normalmente eu gosto de entender todos os algoritmos e estruturas de dados até o ponto em que eu posso reconstruí-los a partir do zero sem ter que trapacear olhando o pseudo código. Eu realmente gosto de algoritmos, então eu gosto de aprender como eles funcionam e eu costumo ir linha por linha e tentar alguns casos, olhando o código e verificando se o que está acontecendo é o que eu entendi que deveria acontecer.

Apenas entender o que está acontecendo me levou MUITO tempo para as árvores RB. Mesmo com as explicações do livro, ainda achei difícil entender o código. Sem mencionar que eu não conseguia entender como / porque as rotações funcionam. Eu não acho nada intuitivo. Quero dizer, os três (seis, na verdade) casos diferentes para inserção e, em seguida, os quatro casos para exclusão? É possível entender isso? É impossível reconstruir esse código sem trapacear. Até a árvore binária eu poderia implementar o material fora da minha cabeça, com alguns ajustes sempre funcionaria, mas com árvores RB eu nem vou tentar. Quero dizer, até o professor fica confuso às vezes, então acho que não é tão fácil assim, mas, ao mesmo tempo, não deveríamos ter que entender tudo o que está acontecendo ou, pelo menos, por quê? O livro não explica realmente como alguém surgiu com a ideia de rotações. Como alguém notou que com 2 rotações você poderia resolver qualquer problema de inserção? Isso é incrível!

Minha pergunta é: eu realmente tenho que entender 100% das árvores RB? Eu me sinto meio ruim pulando coisas sem entender completamente. Obrigado antecipadamente caras! (PS: não há tag para RB-tree, na verdade nem mesmo para tree, apenas binary-tree, então eu só coloquei algoritmos)

    
por Bernardo Pires 29.05.2011 / 22:48
fonte

6 respostas

13

Você parece equiparar a ideia de "compreensão" a "poder escrever o código sem olhar para o livro". Estas são duas coisas diferentes. Se você puder ver como a rotação dos nós da árvore reorganiza a árvore para manter o equilíbrio, você a entende. Ser capaz de recordar imediatamente todos os casos para os quais as rotações se aplicam não é o ponto.

Eu mesmo, eu provavelmente poderia descobrir as rotações se eu tivesse caneta / papel / várias horas para brincar com ele. Mas eu certamente não poderia simplesmente escrever sem pensar. Se eu realmente tivesse que escrever um algoritmo desse tipo, procuraria para ter certeza de que estava obtendo todos os detalhes corretamente. É claro que, em quase todas as situações, eu já usava código escrito.

Onde tudo isso vem em uso é quando você se depara com uma situação que não se encaixa em nenhum dos algoritmos. Você nunca precisará escrever sua própria implementação de árvore. Mas você poderia se encontrar, digamos, precisando achatar uma série de listas duplamente ligadas. Nesse caso, ter entendido a ideia básica por trás da rotação pode ser muito útil.

    
por 29.05.2011 / 23:51
fonte
4

Se você estiver familiarizado com a programação funcional, talvez encontre essa abordagem melhor para eles (Okasaki, 1999):

link

Se não, pelo menos, tenha coragem com a frase de abertura:

Everybody learns about balanced binary search trees in their introductory computer science classes, but even the stouthearted tremble at the thought of actually implementing such a beast.

    
por 30.05.2011 / 00:13
fonte
3

Você não precisa entender as rotações em detalhes. Você deve entender a relação entre árvores RB e 2-3-4 árvores (veja Sedgewick). Todas essas rotações malucas fazem muito mais sentido quando você pensa nelas como de 2 a 3 árvores. Se seu professor não ensinou as árvores RB como um detalhe de implementação para 2-3-4 árvores, você provavelmente deveria ler algo em 2-3-4 árvores. (O tratamento de Sedgewick é muito bom; a Wikipedia não o tem.)

Em geral, entender os detalhes da implementação do motivo pelo qual um algoritmo funciona é às vezes útil. Entender a lógica do motivo pelo qual o algoritmo funciona é quase sempre útil. Ser capaz de criar o algoritmo por si só não é necessário, embora quanto mais algoritmos você entender, maior a chance que você terá.

    
por 30.05.2011 / 08:40
fonte
1

Se você precisar de "RB Trees By Heart" para o seu exame na próxima semana, você terá que morder a bala e aprendê-las. Nesse caso, você deve reconsiderar seus métodos de aprendizado. Talvez tentar explicar RB Trees a um colega de classe lhe ajude mais do que outra noite de escrita solitária de códigos.

Se as Árvores RB forem uma base para o seu próximo curso depois das férias, pule-as agora (sem sentimentos ruins) e concentre-se no curso deste semestre. Mas mantenha os olhos abertos para tópicos que possam prepará-lo para uma segunda tentativa em RB Trees.

Se você sinceramente sentir que nunca precisará deles (cf. comentário de Anna Lear), dê um beijo de despedida sem arrependimentos - ninguém sabe mais do que uma gota no mar do conhecimento (pena que os professores geralmente pensam é o mais importante).

    
por 29.05.2011 / 23:52
fonte
1

A chave para programar o sucesso é nunca desistir :

Hoje suas árvores RB amanhã serão outra coisa. A maior lição é não desistir .

Para mim, essa é uma das principais essências da programação, não desistir ...

Eu sugiro que você continue tentando , e quando você falhar FAÇA DE NOVO .

"Until you get, until it clicks, until it runs."

Porque uma vez que você supera as montanhas, o céu fica claro. Sua mente muda de entendimento, você é temporariamente elevado <(até a próxima montanha) . Essa elevação temporal vale mais do que todo o dinheiro do mundo ..

    
por 30.05.2011 / 00:10
fonte
0

A melhor maneira de entender é testá-lo :

  • Existem 3 ou 6 rotações. Pegue um pedaço de papel e escreva-o um por um.
  • Depois de conseguir, implemente uma Red Black Tree. Tudo bem se você tiver que procurar algumas coisas.

É assim que fizemos na faculdade. E para o exame, conseguimos explicar como uma parte funcionava.

    
por 30.05.2011 / 11:26
fonte

Tags