public class ThreeFourTree
extends java.lang.Object
Constructor and Description |
---|
ThreeFourTree(java.lang.String keyType)
Base constructor.
|
Modifier and Type | Method and Description |
---|---|
protected ThreeFourNode |
CreateNode()
Creates new empty node.
|
protected ThreeFourNode |
CreateNode(java.lang.String ascii,
int dec,
java.lang.String hex,
int oct)
Creates a new node with data.
|
protected void |
ExpandTree(ThreeFourNode currentNode,
ThreeFourNode newSubTree)
Called if the insertion location is full.
|
protected ThreeFourNode |
FindInsertLocation(ThreeFourNode currentNode,
ThreeFourNode newNode)
Finds proper location for insertion of new node.
|
NodeData |
FindValue(ThreeFourNode node,
NodeData searchKey)
Traverses tree to find node with matching key.
|
int |
GetTreeHeight(ThreeFourNode node,
int level)
Gets height of tree.
|
void |
Insert(java.lang.String ascii,
int dec,
java.lang.String hex,
int oct)
Inserts new node at appropriate location.
|
protected void |
InsertNode(ThreeFourNode root,
ThreeFourNode newLeaf)
Handles more complicated cases of inserting into the tree.
|
protected void |
PrintKeys(ThreeFourNode node)
Prints all key values for node.
|
ThreeFourNode |
RootNode()
Getter for tree's root node.
|
void |
RootNode(ThreeFourNode rootNode)
Setter for tree's root node.
|
protected void |
SetChildKeys(ThreeFourNode currentNode)
Appropriately sets keys for node.
|
protected void |
SetOrdering(ThreeFourNode parentNode)
Ensures that child nodes are in proper ordering.
|
boolean |
SetOrderingOfParent(ThreeFourNode currentNode)
Compares parent's smallest value with the largest value of parent's previous sibling (if exists).
|
void |
TraverseAndPrintLeaves(ThreeFourNode root)
Traverses tree and prints all root nodes.
|
void |
TraverseAndPrintLevels(ThreeFourNode root)
Traverses tree and prints values for all nodes, in breadth-first fasion.
|
public ThreeFourTree(java.lang.String keyType)
keyType
- Defines key type for tree nodes.public ThreeFourNode RootNode()
public void RootNode(ThreeFourNode rootNode)
rootNode
- Root node of tree.protected ThreeFourNode CreateNode()
protected ThreeFourNode CreateNode(java.lang.String ascii, int dec, java.lang.String hex, int oct)
ascii
- dec
- hex
- oct
- public void Insert(java.lang.String ascii, int dec, java.lang.String hex, int oct)
ascii
- dec
- hex
- oct
- public int GetTreeHeight(ThreeFourNode node, int level)
node
- Root node.level
- Current level (should pass 0 to start).public NodeData FindValue(ThreeFourNode node, NodeData searchKey)
node
- Current node in tree to search.searchKey
- Keys to compare against.public void TraverseAndPrintLevels(ThreeFourNode root)
root
- Root node of tree.protected void PrintKeys(ThreeFourNode node)
node
- Node to print keys of.public void TraverseAndPrintLeaves(ThreeFourNode root)
root
- Root node.protected void InsertNode(ThreeFourNode root, ThreeFourNode newLeaf)
root
- "Ideal" location of tree to insert into. Note: If this location is full, obviously it cannot insert
and has to manipulate tree accordingly.newLeaf
- New leaf to insert into.protected ThreeFourNode FindInsertLocation(ThreeFourNode currentNode, ThreeFourNode newNode)
currentNode
- Current location to check.newNode
- Node to locate spot for.protected void ExpandTree(ThreeFourNode currentNode, ThreeFourNode newSubTree)
currentNode
- Current location within tree.newSubTree
- New section to add onto tree.protected void SetOrdering(ThreeFourNode parentNode)
parentNode
- Node to sort children of.public boolean SetOrderingOfParent(ThreeFourNode currentNode)
currentNode
- Node to compare.protected void SetChildKeys(ThreeFourNode currentNode)
currentNode
- Current node to set keys for.