Browse Prior Art Database

Stack Algorithm for Extracting Subtree from Serialized Tree

IP.com Disclosure Number: IPCOM000111528D
Original Publication Date: 1994-Mar-01
Included in the Prior Art Database: 2005-Mar-26
Document File: 4 page(s) / 89K

Publishing Venue

IBM

Related People

Stucka, JE: AUTHOR [+2]

Abstract

Disclosed is an efficient algorithm for tree processing in dynamic environments; it can be used to identify subtree members within a serialized tree or to construct an entire hierarchical tree from a serialized tree.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Stack Algorithm for Extracting Subtree from Serialized Tree

      Disclosed is an efficient algorithm for tree processing in
dynamic environments; it can be used to identify subtree members
within a serialized tree or to construct an entire hierarchical tree
from a serialized tree.

      A subtree is a sub-hierarchy of tree nodes consisting of a node
and all of its children, including the children's children, etc.
Some applications require only a subtree instead of the entire tree,
for instance, isolating a subtree for processing due to size of
entire tree.

      This invention uses a stack-based algorithm to maintain a list
of potential parent nodes, from a tree serialized using preorder
traversal.  The stack is transitory, with tree nodes being pushed on
and popped off, thus minimizing the number of comparisons to find a
given parent node.

      When the algorithm is used to identify a subtree, the stack
contains subtree nodes that are potential parents.  If the parent for
the current node is not found on the stack, then the current node is
not in the subtree.  The runtime hierarchy for the subtree could be
constructed as the algorithm identifies each subtree node, or later
after the entire set of nodes has been identified.  An example of the
algorithm is shown in the Figure.  The basic operation of the
algorithm follows:

1.  Define variables to hold pointers to head node and tail node.

2.  Using linear search, locate head node of the subtree in the
    serialized tree; set head node pointer and tail node pointer
    variables to this node.

3.  Place head node on stack.

4.  For each remaining node in serialized tree, until stack is empty
    or serialized tree exhausted:

    a.  If node on top of stack is parent of node in serialized tree,
        push node in serialized tree onto stack; update tail node
        pointer to point to this node in serialized tree.

    b.  Else, pop top of stack.

    (After this "for" loop completes, the head and tail pointer
    variables point to the nodes of the serialized tree that are the
    first and last nodes of the subtree.  All nod...