Re: Red Black Guaruntees
- From: "jehugaleahsa@xxxxxxxxx" <jehugaleahsa@xxxxxxxxx>
- Date: Wed, 31 Oct 2007 01:52:16 -0000
On Oct 30, 6:13 pm, Ben Pfaff <b...@xxxxxxxxxxxxxxx> wrote:
"jehugalea...@xxxxxxxxx" <jehugalea...@xxxxxxxxx> writes:
By the way, is it possible to do efficient in-order iterators for a
tree if it doesn't have parent pointers?
If you don't mind taking a performance hit whenever the tree
changes, then your iterator can contain an array of the ancestors
of the current node. You can use serial numbers in the iterator
and the tree to detect when the tree has changed and thus that
the array of ancestors needs to be refreshed.
Example implementation:
http://adtinfo.org/libavl.html/Traversal-of-an-AVL-Tree.html
--
Ben Pfaffhttp://benpfaff.org
Ah, I see . . . I understand what you were saying. Very
interesting . . . but I still don't like it.
.
- References:
- Red Black Guaruntees
- From: jehugaleahsa@xxxxxxxxx
- Re: Red Black Guaruntees
- From: Ben Pfaff
- Red Black Guaruntees
- Prev by Date: Re: Red Black Guaruntees
- Next by Date: Re: Calculate the precision of a floating point number (ie: the number of decimal places)
- Previous by thread: Re: Red Black Guaruntees
- Next by thread: Re: Red Black Guaruntees
- Index(es):
Relevant Pages
|
