Class treeN.TreeN


public class TreeN
extends Object
Tree structure whose root node can contains an arbitrary number n data elements amd a a corresponding n+1 children subtrees.

Author:
DXN, SBW

Variable Index

 o _children
 o _data

Constructor Index

 o TreeN ()
Initializes this TreeN to an empty tree
 o TreeN (Integer)
Initializes this TreeN to a tree with one (Integer) element
 o TreeN (Vector, Vector)
Private initialization of the _data and _children arrays
 o TreeN (TreeN, Object, TreeN)
Private iniitalization to a tree with one element at the root and

Method Index

 o execute (ITreeNAlgo, Object[])
Hook method for the visitor pattern
 o getChild (int)
Returns the child subtree at a given index
 o getDat (int)
Returns the data at a given index
 o setDat (int, Object)
Replace the data at idx with a new data object and return the old data
 o spliceAt (int, TreeN)
Joins the supplied source tree t to the receiver at index i: the ith child
 o splitDownAt (int)
Removes the ith element from the root of the receiver including its corresponding
 o splitUpAt (int)
Mutates the receiver, in state s, into a 2-node tree (state = 1),

Variables

 o _children
private Vector _children = new Vector()
 o _data
private Vector _data = new Vector()

Constructors

 o TreeN
public  TreeN()
Initializes this TreeN to an empty tree.

 o TreeN
public  TreeN(Integer n)
Initializes this TreeN to a tree with one (Integer) element.

 o TreeN
private  TreeN(Vector data, Vector children)
Private initialization of the _data and _children arrays.

 o TreeN
private  TreeN(TreeN lTree, Object n, TreeN rTree)
Private iniitalization to a tree with one element at the root and a (left) subtree at index 0 and a (right) subtree at index 1.

Methods

 o getDat
public Object getDat(int idx)
Returns the data at a given index. The left-most data is at index 0. The right-most data is at index _data.size()-1.

 o getChild
public TreeN getChild(int idx)
Returns the child subtree at a given index. The left-most child is at index 0. The right-most child is at index _children.size()-1.

 o setDat
public Object setDat(int idx, Object e)
Replace the data at idx with a new data object and return the old data. This is added for convenience (and improved performance).

 o spliceAt
public TreeN spliceAt(int idx, TreeN tree)
Joins the supplied source tree t to the receiver at index i: the ith child of the receiver is deleted and the root node of t is “spliced” between the ith and i+1th elements of the receiver. The children of t remain in their respective places with regards to the original elements of t. Splicing an empty source tree into a non-empty tree is a no-operation. Splicing a non-empty source tree into an empty tree will mutate the empty receiver tree into a shallow copy of the source tree. See Figure 2 of DP4SBT paper.

Parameters:
idx - -- 0 <= idx <= state of the tree+1, unless state = 0 then idx must equal 0.
tree - -- tree to be spliced in. If the state of this tree = 0, then nothing is done.
Returns:
this.
 o splitUpAt
public TreeN splitUpAt(int idx)
Mutates the receiver, in state s, into a 2-node tree (state = 1), where the ith element becomes the root data and the left child’s root contains the 0 through i-1 elements of the original root and the right child’s root contains the i+1 through s elements of the original root. Splitting up on an empty tree is a no-operation. See Figure 2 of DP4SBT paper.

Parameters:
idx - 0 <= idx <= state of tree - 1.
Returns:
this.
 o splitDownAt
public TreeN splitDownAt(int idx)
Removes the ith element from the root of the receiver including its corresponding left and right child trees. The resultant new child tree is a 2-node tree where i ts root data is the original ith element and where its left and right children are the original ith element’s left and right children respectively. Splitting down a 2-node tree results in an empty tree and is equivalent to a deletion of a single data element. Splitting down an empty tree is a no-operation. See Figure 2 of DP4BST paper.

Parameters:
idx - 0 <= idx <= state of tree - 1.
Returns:
this.
 o execute
public Object execute(ITreeNAlgo algo, Object[] param)
Hook method for the visitor pattern.