org.ai_heuristic.tree

Class KD_Tree

java.lang.Object

org.ai_heuristic.tree.TreeNode

org.ai_heuristic.tree.KD_TreeNode

org.ai_heuristic.tree.KD_Tree

public class KD_Tree
extends KD_TreeNode

This uses the KD_TreeNode for inserting and searching over tree values. This class can be used to build a tree-like structure, representing arbitrary information. Use this as the base node of any k-dimensional tree structure, to store child node, but without any value itself. TreeNode values are compared using SimpleMathCompare by default, but you can change that through the setMetricEvaluator method.

Author:

Kieran Greer

Field Summary

Fields inherited from class org.ai_heuristic.tree.KD_TreeNode

bucketSize, evaluator, mathCompare, nodeStats

Fields inherited from class org.ai_heuristic.tree.TreeNode

childNodeKeys, childNodes, count, name, parent, value, valueType

Constructor Summary

Constructors

Constructor and Description
KD_Tree(int theBucketSize, java.lang.String theValueType, FunctionMetric metricEval, EvaluateMathDef mathEval) Create a new instance of KD_Tree.
KD_Tree(java.lang.String theName, int theBucketSize, java.lang.String theValueType, FunctionMetric metricEval, EvaluateMathDef mathEval) Create a new instance of KD_Tree.

Method Summary

Modifier and Type	Method and Description
boolean	add(KD_TreeNode treeNode) Add the node to the tree.
void	clearTree() Clear the whole tree by removing all child nodes.
java.lang.Object	clone() Clone and return a copy of this object.
java.util.ArrayList<KD_TreeNode>	search(java.lang.String dsNode, MetricDataset dataset, int k) Search the tree and return the k closest matches to the dataset.
java.lang.String	toString() Return a string-based description of the node branch.

Methods inherited from class org.ai_heuristic.tree.KD_TreeNode

addToTree, getBestMatchIndex, getBestMatchNode, getBucketSize, getMathEvaluatorClass, getMetricEvaluatorClass, getNodeStats, search, setBucketSize, setMathEvaluator, setMetricEvaluator, setNodeStats, updateNodeStats

Methods inherited from class org.ai_heuristic.tree.TreeNode

addChildNode, addChildNode, clearChildNodes, getChildNode, getChildNodeDeep, getChildNodeKeys, getChildNodes, getChildNodeValue, getChildNodeValueDeep, getCount, getName, getParent, getValue, getValueType, getValueTypeMD, hasChildNode, hasChildNodeDeep, hasChildNodes, hasChildNodeValue, hasChildNodeValueDeep, hasValue, isLeaf, maxDepth, nodesAtLevel, removeChildNode, setChildNodes, setChildNodes, setCount, setParent, setValue, toString, treeValueDeep

Methods inherited from class java.lang.Object

equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Constructor Detail

KD_Tree

public KD_Tree(int theBucketSize,
               java.lang.String theValueType,
               FunctionMetric metricEval,
               EvaluateMathDef mathEval)
        throws java.lang.Exception

Create a new instance of KD_Tree. The name is assigned a unique value.

Parameters:

theBucketSize - the tree node capacity.

theValueType - the type of value that this node supports.

metricEval - the evaluation function.

mathEval - for simple math comparisons.

Throws:

java.lang.Exception - any error.

KD_Tree

public KD_Tree(java.lang.String theName,
               int theBucketSize,
               java.lang.String theValueType,
               FunctionMetric metricEval,
               EvaluateMathDef mathEval)
        throws java.lang.Exception

Create a new instance of KD_Tree.

Parameters:

theName - a unique name or ID for the tree.

theBucketSize - the tree node capacity.

theValueType - the tree value type.

metricEval - the evaluation function.

mathEval - for simple math comparisons.

Throws:

java.lang.Exception - any error.

Method Detail

search

public java.util.ArrayList<KD_TreeNode> search(java.lang.String dsNode,
                                               MetricDataset dataset,
                                               int k)
                                        throws java.lang.Exception

Search the tree and return the k closest matches to the dataset.

Parameters:

dsNode - name of the node the data belongs to, if already in the tree. This node is not then considered during the search,

dataset - the dataset to compare with, probably from the dataset node.

k - the number of matches to return.

Returns:

a list of KD_TreeNode nodes that are closest to the dataset parameter.

Throws:

java.lang.Exception - any error.

add

public boolean add(KD_TreeNode treeNode)
            throws java.lang.Exception

Add the node to the tree.

Parameters:

treeNode - the node with a list of values of size dimSize.

Returns:

true if added OK, false if not.

Throws:

java.lang.Exception - any error.

clearTree

public void clearTree()

Clear the whole tree by removing all child nodes.

toString

public java.lang.String toString()

Return a string-based description of the node branch.

Overrides:

toString in class TreeNode

Returns:

a description of this node and its child nodes.

clone

public java.lang.Object clone()

Clone and return a copy of this object. Child nodes are not cloned.

Overrides:

clone in class KD_TreeNode

Returns:

a light copy of this node.