[Date Prev][Date Next][Thread Prev][Thread Next][Author Index][Date Index][Thread Index]

*To*: udanax@xxxxxxxxxx*Subject*: [Fwd: SEP94: K-Tree Container Data Structures]*From*: John Dougan <jdougan@xxxxxxx>*Date*: Fri, 11 Jan 2002 23:52:16 -0800

--john dougan

---Begin Message---

To: John Dougan <jdougan@xxxxxxx>Subject: SEP94: K-Tree Container Data StructuresFrom: John Dougan <jdougan@xxxxxxxxxxxxx>Date: Mon, 07 Jan 2002 23:48:10 -0800

http://www.google.com/search?q=cache:E2zEjRTwgC0C:armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm+k-tree+dobbs&hl=en

--

John Dougan

jdougan@xxxxxxxxxxxxx

Title:SEP94: K-Tree Container Data Structures

This is G o o g l e's cache of http://armoire.cs.nwu.edu/Reading/Doctor%20Dobbs%20-%20Release%2010/articles/1994/9409/9409b/9409b.htm.

G o o g l e's cache is the snapshot that we took of the page as we crawled the web.

The page may have changed since that time. Click here for the current page without highlighting.Google is not affiliated with the authors of this page nor responsible for its content.These terms only appear in links pointing to this page:

These search terms have been highlighted: ktreedobbs

K-TreeContainer Data Structures## Fast subscripting, slicing, and concatenation of sequences

## Rodney Bates

Rod is an engineer with Boeing aircraft and can be contacted at bates@xxxxxxxxxxxxxxxxxx## The

K-treeData StructureFigure 1 shows a graphical notation for both kinds of nodes. The fields and array subscripts are labeled, showing how to interpret the nodes in the examples that follow.

There is a global maximum, N, for the number of array elements in any node of either kind. N must be at least 3. A leaf node with one element occurs only in the representation of a singleton sequence. Every other node always has at least two elements. Figure 2 shows some examples of small

K-trees and the sequences they represent. The elements of sequences are integers. Figures 2(b) and 2(c) are two differentK-trees which represent the same sequence. In general, there are manyK-treerepresentations for a given sequence. A givenK-treerepresents only one sequence, according to the following rules:

- A NIL pointer represents the empty sequence. A pointer to a leaf node represents just the elements of
LeafElems. A pointer to a nonleaf node represents the concatenation of the sequences represented by theChildReffields.- The value of
CumChildCtin theJth element of a nonleaf node is the sum of the lengths of the subsequences represented by theChildReffields ofNonleafElems[0..J]. This means thatNonleafElems[ElemCt --1].CumChildCtis the length of the sequence represented by this node.- From a given node, all paths to leaves have the same length. This value is stored in the
Heightfield.K-trees are always full in the sense that, althoughElemCtmay vary, there are no NIL pointers inChildReffields.- No node contains any information derived from its parent or siblings. Since the nodes are immutable, any subtree can be shared among many parents, each of which belongs to a different
K-tree.## Subscripted Fetching

## Subscripted Assignment

Figure 3 shows the result of assigning value 8 to element number 4 of the

K-treein Figure 2(d). The shaded nodes have identical contents and are the same nodes as before the assignment. The other nodes are new. The two new nonleaf nodes look the same as before, but have different values in one of theChildReffields. To illustrate this, pointer values which have changed are shown as dashed arrows.

## Concatenation

Figure 4 gives an example of

K-trees before and after concatenation, showing only the nodes along the seam. TheCumChildCtfields are omitted in this example. The small numbers in circles represent nodes to either side of the seam without showing their contents. All these nodes are reused.At height one, the two leaf nodes collectively have seven elements, which can't be repacked into one node. They are reused intact in the result. At height two, there are six elements altogether, so they are repacked into one new nonleaf node.

At height three, there are initially eight elements. Two point to nodes that are not reused in the result and whose replacement consists of only one node. This leaves a total of seven new elements needed along the seam. These are distributed into the two new nodes, three elements in one node and four in the other.

At height four, only the right-operand

K-treehas a node. The root pointer of the left operand is treated as a fictitious, one-element node, which must be repacked with the elements from the right side of the seam. This requires a total of seven elements: Two point to replacements for old nodes, and the rest point to reused nodes to the right of the seam.Finally, a new node at height five is needed to collect the two nodes of height four. Thus the height of the result

K-treeis one greater than the highest-operandK-tree.Implementing concatenation is somewhat more complex than the concept. A recursive procedure has to start at the top of the

K-trees, descend to the leaves, and then do its work on the way back up. The operandK-trees could have different heights. TheHeightfield allows the descent to synchronize itself so it is working on nodes of the same height on each side of the seam. Unequal heights also create some special cases for node construction during the return to the top.

## Slicing

Figure 5 gives an example of slice construction, showing only relevant nodes along the cuts. The notation is the same as in Figure 4, except that wavy lines through nodes are used to show the location of the left and right cuts.

At height one, the two cuts are independent. On the left, the node slice of the leftmost node shown in full contains one element whose value is 20. This is repacked with the three elements 19, 4, and 25 of the next rightward node. On the left, the entire node containing element values 16 and 10 is reused.

At height two, three nodes are involved in the slice. At the left end, two elements have been replaced by one new element, returned from below. All other elements involved are reused. This gives a total of seven elements, which are repacked into two new nodes.

At height three, only two nodes are involved. The two new pointers returned from the level below are packed into a single new node.

Finally, at height four, only one node is involved. Two of its elements are replaced by one new node. Since one pointer does not require a node at this level, it becomes the entire result

K-tree.

## The Implementation

## Figure 1 Notation for

K-treenodes.Figure 2

K-trees and their sequences; (a) 13; (b) 7, 25, 19, 47, 5; (c) 7, 25, 19, 47, 5; (d) 16, 0, 15, 23, 6, 14, 11, 7, 3, 19, 29.Figure 3 New

K-trees after assignment of value 8 to element number 4.

Figure 4:(a) Before concatenation; (b) after concatenation; N=6.

Figure 5:(a) Before slicing; (b) after slicing.Copyright © 1994,

Dr. Dobb's Journal

---End Message---

- Prev by Date:
**Error in Xanadu/Udanax article** - Next by Date:
**Udanax Mailing List Gated to Sunless-Sea Site** - Previous by thread:
**Error in Xanadu/Udanax article** - Next by thread:
**Udanax Mailing List Gated to Sunless-Sea Site** - Index(es):