Re: Red Black Guaruntees

"jehugaleahsa@xxxxxxxxx" <jehugaleahsa@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 Pfaff
http://benpfaff.org
.

Relevant Pages

  • Re: Easy balanced tree
    ... The tree can hold between 4 and 7 values, if it was lower than 4 ... then the array would be smaller so we ignore those cases. ... Secondly there is wasted space in the middle of the array (with ... rdrop nip nip; ...
    (comp.lang.forth)
  • Re: Is it possible to have mutable-in-place (associative-)array objects in PHP?
    ... This is the way all languages work. ... just that array variables aren't objects ... and for each I must find the appropriate path in the tree I'm ... treeptr <- rootOfTree ...
    (comp.lang.php)
  • Re: [opensuse] Recover md RAID-1.
    ... md: md0 stopped. ... Then try booting the array with just /dev/sdb1 as a member. ... A ball hitting a tree shall be deemed not to have hit the tree. ...
    (SuSE)
  • Re: data structure for network protocol
    ... As a first thought, I was considering linked lists, but they are probably ... The second option is tree. ... hash tables. ... in an ordinary array (the main cost is that, if the number of items gets ...
    (comp.programming)
  • Re: array moving left
    ... I have an array in which elements are present. ... Instead maintain a binary tree of deletion points. ... The left child weight of a node is the number of nodes under it on the ... deletions have occurred to the left of the element. ...
    (comp.programming)