|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--com.ibm.etools.mft.builder.internal.BinaryTree
A binary tree stored in an integer array
Intended use is as an index structure for storing ITable Row indices. This data-structure supports collisions (duplicate keys), unlike the java.util Collections classes.
It is expected (especially in the case of the reference table) that there may be very many rows that have the same reference symbol. So scalable performance in the presence of duplicates is very important.
The tree is accessed using handle
s, which are
integer values indicating the tree node in the array. The
actual value of the handle returned can be used to index into
the array, for the number of integers specified when allocating
the tree node. The sizeof(int handle)
method can
be used to determine the amount of space allocated in a
given tree node.
An example of a binary tree is depicted below.
The binary tree data structure is:
T
the left
Tl
and right Tr
the weight is:
1/2
, if T
is empty|Tl|/|T|
, otherwiseO(ln(N))
,
where N
is the number of nodes in the tree.A well-balanced tree maintains peak search performance. When inserting duplicates, a weight-balanced tree can choose to insert where it keeps the tree most balanced.
Implementer notes:
Constructor Summary | |
---|---|
BinaryTree()
Default constructor |
Method Summary | |
---|---|
int |
allocTreeNode(int size)
Allocate an empty, balanced tree node |
void |
clear()
|
int |
getTreeNodeCount(int index)
|
void |
insertTreeNode(int handle,
com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
Insert a node in the tree |
void |
removeTreeNode(int handle)
Remove an element from the tree |
int[] |
searchTree(com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
Search the tree for matches |
int |
sizeof(int handle)
Return the amount of user space allocated in a tree node |
Methods inherited from class java.lang.Object |
---|
equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
Constructor Detail |
public BinaryTree()
Method Detail |
public final void clear()
public final void removeTreeNode(int handle)
handle
- public final int[] searchTree(com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
First, search for the "lowest common parent" (LCP). In an in-order sorted tree, all the matching tree nodes will be children of this lowest common parent. Split the LCP subtree in 2 (the left and right subtrees of the LCP).
Second, count the number of matches for a search. Since the tree supports multiple nodes with the same value, any such duplicate nodes will be left or right children of the LCP. Further, there is a 'first' node on the left of the LCP such that all nodes in-order between it and the parent must also match, conversely, there is a 'last' node in the right of the LCP such that all nodes between the LCP and the last node are also matches.
Consider the left subtree. The tree being sorted in-order, no nodes will compare greater than the LCP. If any node TN compares equal to the search, all right branches must also compare equal; the first node must either be TN or in the left subtree of TN. If TN node compares less than the search, then TN and all its left children are less than the search and the first node, if it is a child of TN, must be in the right subtree. The converse is true for the right branch.
So the in-order property lets us count the number of matches by counting matching nodes and their right children (for the left subtree) or left children (for the right subtree) from the LCP.
public final void insertTreeNode(int handle, com.ibm.etools.mft.builder.engine.IndexMatcher matcher)
public final int sizeof(int handle)
This may actually be greater than the amount of space requested, depending on the size of the memory block allocated.
handle
-
public final int allocTreeNode(int size)
size
-
public final int getTreeNodeCount(int index)
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |