RE: TREAPS

[Yoshiharu Kohayakawa <yoshi@ime.usp.br>]

Evelyn Cristina Pinto writes:
 > Eu li o programa do Knuth Wordtest e nao consegui entender exatamente o
 > que uma Treap faz.

Sim, a parte mais especifica sobre o treap é complicado...

 > O que entendi foi que ele usa Heap para espalhar os dados e depois ABB
 > para buscar as palavras no arquivo dado, mas parece que de alguma forma o
 > programa monta as duas arvores ao mesmo tempo. Eh isso mesmo?

Sim, é uma única árvore.  Cada nó tem duas chaves.  No wordtest, a chave
principal é uma palavra e a secundária é um inteiro.  Se voce leva em conta as
palavras, a árvore está organizada como uma ABB.  Se voce olha para os
inteiros, a árvore está organizada como um heap.

 > Procurei, entao na Internet algum material sobre isso. Estou deixando o
 > que encontrei aqui para todos os alunos verem, mas ainda nao ficou claro
 > como uma Treap funciona. Gostaria que alguem pudesse explicar melhor isso.
 > 
 > Pelo pouco que entendi ela tem um otimo desempenho em busca.
 > 
 > Professor, em que livro podemos encontrar alguma coisa?

Infelizmente, nao conheço um livro adequado para nos...  Yoshi

 > Valeu turma!
 > 
 >  Evelyn Cristina Pinto   <ecp@linux.ime.usp.br>
 > 
 > The first part of this page is in German - please ignore it if you do not
 > understand it!
 > 
 > Idea behind Treaps
 > Implementation of Treaps
 > Implementation of the test driver
 > Results of the measurements
 > 
 > [...]