Vertebral traverse

from Wikipedia, the free encyclopedia
not yet visited
visited once
visited twice

In computer science, vortex traversal refers to a memory-efficient iterative algorithm for examining all nodes of a binary tree .

description

The algorithm was published independently by Lindstrom and Dwyer. It traverses a given binary tree. By using pointer inversion ( link reversal , according to Schorr / Waite), it does not need an external storage tank ; he remembers the way back by skillfully modifying the tree pointers.

The name "vertebral traversing" comes from the idea that each knot has three pointers (to the parent, left and right child knot) at an angle of 120 ° each, which are rotated ("swirled") further by 120 ° with each visit, see pictures. The algorithm visits each node three times. After the third visit, the original node state is restored.

Actually stored in the tree are only two pointers, which point to the left and right child in the initial and final state (green and blue in the picture). The third one (red in the picture) only exists for the current node and is kept in local variables ( prv, cur) in the algorithm ( see below ).

implementation

An implementation in C can look like this: 

struct _node {
    int key;
    struct _node *left;
    struct _node *right;
};

extern void visit(struct _node *tree);

void rotate(struct _node **prv,struct _node **cur) {
    struct _node * const savedLeft = (*cur)->left;
    (*cur)->left  = (*cur)->right;
    (*cur)->right = *prv;
    if (savedLeft == NULL) {
        *prv = savedLeft;
    } else {
        *prv = *cur;
        *cur = savedLeft;
    }
}

void wTrav(struct _node *tree) {
    struct _node *prv;
    struct _node *cur = tree;
    if (tree == NULL)
        return;
    // traverse left subtree
    do {
        visit(cur);
        rotate(&prv,&cur);
    } while (cur != tree);
    // traverse right subtree
    do {
        visit(cur);
        rotate(&prv,&cur);
    } while (cur != tree);
    // final visit of root
    visit(cur);
    rotate(&prv,&cur);
}

The last rotatecall can visitno longer influence the effect of the calls. Nevertheless, it is needed, namely to rotate the pointers of the root node back to their original position.

Bulleted orders and visit actions

The algorithm visits each node exactly three times. In the form shown above, there is no way of determining how many visits are currently taking place at the current node. This means that pre-, in-or post-order traversal cannot be easily implemented; this requires an additional 2- bit wide visit counter in each node.

Alternatively, at least pre-order traversal can be implemented by overwriting the node data with an "invalid" value, provided they are no longer required after the traversal. For example, with the following implementation of visit, the traversal algorithm will pre-order (and destroy) the node values: 

#define INVALID (-999999999) /* never used as key value */
void visit(struct _node *tree) {
    if (tree->key != INVALID) {
        printf(" %d",tree->key);
        tree->key = INVALID;
    }
}

If the visitaction is idempotent , vertebral traversal can readily be used; so z. B. to initialize the data of all nodes with a given value. With large amounts of data per node, however, it must be remembered that the initialization effort is threefold.

If the desired action f can be represented as a triple iterated function f = g ∘ g ∘ g , an implementation of g can be visitused as. To z. B. incrementing all node values ​​of a subtree can be used tree->key++as the body of visitif the node values ​​are later divided by 3 before use.

literature

  1. ^ G. Lindstrom: Scanning list structures without stacks or tag bits . In: Information Processing Letters . tape 2 , 1973, p. 47-51 ( online ).
  2. ↑ Barry Dwyer: Simple algorithms for traversing a tree without an auxiliary stack . In: Information Processing Letters . tape 2 , no. 5 , 1974, p. 143-145 ( online ).
  3. ^ Herbert Schorr and William M. Waite: An Efficient Machine-Independent Procedure for Garbage Collection in Various List Structures . In: Communications of the ACM . tape 10 , no. 8 , August 1967, p. 501-506 ( online [PDF]).
  4. ↑ a b Prabhaker Mateti and Ravi Manghirmalani: Morris' tree traversal algorithm reconsidered . In: Science of Computer Programming . tape 11 , no. 1 , October 1988, p. 29–43 , here: p. 30 ( online ).
  5. ^ Morris, Joseph M .: Traversing binary trees simply and cheaply . In: Information Processing Letters . tape 9 , no. 5 , December 1979, pp. 197-200 , doi : 10.1016 / 0020-0190 (79) 90068-1 ( online [PDF]).
  6. ↑ Alexander Stepanov and Paul McJones: Elements of Programming . Semigroup Press, Palo Alto 2019, ISBN 978-0-578-22214-1 , here: p. 143 ( online [PDF]).
  7. ↑ The "Investigation" action only takes place on the first visit.
  8. ↑ only with the second
  9. ↑ Promotion only on the third visit
  10. ↑ Ernst Schröder: About iterated functions . In: Mathematical Annals . tape 3 , no. 2 , 1870, p. 296-322 (on- line ). See also : Iterated function .