Re: Red Black Guaruntees

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

I meant, is it possible to do a in-order traversal without a parent
pointer. With the parent pointer, one can go from a right-most child
and work their way *up* to the next-in-order node.

While you can retain your ancestors on one route down the tree, it
doesn't help you view the tree (as a whole) in sorted order later on.

The only way I can see it being done is to maintain a stack of nodes
as you navigate down the tree and to pop off the stack when you move
to the next node. However, this would require copying the entire tree
while iterating over the elements . . . it seems extreme. However,
since there is one pointer for each node in the tree for parent
pointers, I suppose the classic approach is fairly extreme as well.

.

Relevant Pages

  • Re: hacker challenge - traverse a list
    ... Here is a little challenge - print the contents of a binary tree ... I assume there are no up links, otherwise the algorithm is trivial. ... space hence unbounded number of bits in a pointer? ... Left branch *not* leaf, rotate: ...
    (comp.programming)
  • Re: question of style
    ... end of the day the quality of the code depends more on the quality of ... or the equivalent null pointer exceptions in Java, C, or whatever? ... But you have implemented a mutable tree. ...     def get: ...
    (comp.lang.python)
  • Re: Help me come up with a few and simple programming challenges
    ... >Dave Vandervies wrote: ... >> language, I'd probably pass around a pointer to the list's head pointer ... >(define (sublist tree lo hi) ...
    (comp.lang.scheme)
  • Re: Reading XML stream using unmanaged c++
    ... You don't need a back pointer to implement tree structures. ... but a back pointer is a handy thing to have when using a DOM node. ... XML is metadata, but an XML document is an XML metadata structure with actual data ...
    (microsoft.public.vc.mfc)
  • Re: hacker challenge - traverse a list
    ... void deleteEl; ... mangle and print the binary tree, then demangle it back to its ... node * tmptop = treetop; ... The basic idea is to convert the right pointer into a directly ordered ...
    (comp.programming)