Re: Sorted heap trees
- From: cri@xxxxxxxx
- Date: Fri, 28 Mar 2008 21:46:34 -0700 (PDT)
On Mar 28, 5:27 pm, Jon Harrop <use...@xxxxxxxxxxxxxx> wrote:
Richard Harter wrote:
It turns out that there are some special situations where a
sorted heap tree is better than an ordinary BST. I am wondering
if anyone knows the proper name for these type of trees and of
any references, e.g., properties, uses, adaptations of standard
algorithms for them.
I call them search trees. The most common form in computer science is
balanced search trees, where the maximum depth is O(log n). In natural
science, you can often accelerate computations by not balancing the tree.
An example of this is given at the end of chapter 3 of OCaml for Scientists.
Perhaps I err, but I opine that you haven't quite understood what the
post
was about. I dare say I wasn't clear enough - my apologies. Take it
as
given that I knew long ago what binary search trees are, balanced
trees are,
AVL trees are, heaps are, fibonacci heaps are, etc. You can indeed
use heap
trees as search trees, but they aren't your grandmother's standard
binary
search trees in comp sci 101.
.
- References:
- Sorted heap trees
- From: Richard Harter
- Re: Sorted heap trees
- From: Jon Harrop
- Sorted heap trees
- Prev by Date: Re: Sorted heap trees
- Next by Date: you have to system
- Previous by thread: Re: Sorted heap trees
- Next by thread: DO U LIKE ME
- Index(es):
Relevant Pages
|
