[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
RE: TREAPS
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
>
> [...]
- Follow-Ups:
- RE: TREAPS
- From: Yoshiharu Kohayakawa <yoshi@ime.usp.br>
- References:
- TREAPS
- From: Evelyn Cristina Pinto <ecp@linux.ime.usp.br>