Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Encodement for Tree Restructuring

IP.com Disclosure Number: IPCOM000050039D
Original Publication Date: 1982-Aug-01
Included in the Prior Art Database: 2005-Feb-09
Document File: 3 page(s) / 42K

Publishing Venue

IBM

Related People

Kurtzberg, JM: AUTHOR

Abstract

An encodement scheme is described herein for representing tree structures by strings of numbers. The encodement has the property that trees may be modified, i.e., subtrees may be added to or deleted from the parent tree, by means of simple arithmetic operations upon the strings.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 53% of the total text.

Page 1 of 3

Encodement for Tree Restructuring

An encodement scheme is described herein for representing tree structures by strings of numbers. The encodement has the property that trees may be modified, i.e., subtrees may be added to or deleted from the parent tree, by means of simple arithmetic operations upon the strings.

Let T be a rooted tree. Consider the nodes of T to lie in tree levels given by the number of branches in the path between a node and the root of T. The first element in the string is the level of the terminal node on the "leftmost path". The next element in the string is the level of the node with multiple branches that is nearest the terminal node associated with the first string element. The level of the terminal node on the next leftmost path (the path that has not been used yet) forms the next element on the list. Then, the next element in the string is formed from the level of the node with multiple branches whose paths do not have their terminal nodes encoded into elements on the string, and so forth. This process continues until all paths have their terminal nodes encoded into string elements. An illustration of the encoding scheme is given in Fig. 1. This encodement is 1-to 1, assuming the ordering of branches from a node is to be preserved, that is, a tree has a unique string representation and a given string generates a unique tree.

The encodement described previously is only appropriate for representing the tree structure. It does not convey any information contained on the nodes. To carry this information it is necessary to define a new string, termed the P string, the elements of which are defined for only the odd positions of the string elements. Each element of P consists of a list of node names. It is possible that the node name also contains all node information, that is, the node names can be pointers to data sets. The nodes on each list designate the path from the tree root to the terminal node. For an illustration, see Fig. 2.

An abbreviated node information storage scheme may be adopted by considering the even elements of the tree encodement string. Namely, the list of nodes in the k/th/ element of the P string (which corresponds to the 2k-1 element of the encodement string) explicitly consists of a replication of the first j+1 nodes from the (K-1)/th/ element of the P string. The value j is given by the 2k-2 element in the encodement string. As a convenience, j+1 is entered at the top of the list of nodes in the k/th/ element of the P string, and the first j+1 nodes of the path from the tree root to the terminal node are suppressed (Fig. 3). An admixture of the two schemes can be adopted.

Decomposition and Reconstitution: With the encode...