Class TwoThreeTreeNode 

java.lang.Object
   |
   +----TwoThreeTreeNode
public class TwoThreeTreeNode
extends Object
Source File: TwoThreeTreeNode.java

Class for for a node of a TwoThreeTree. This is the non-threaded version. It uses a data member called parent for keeping track of the node's parent, for use during insertions and deletions. This version also differs from the example shown in the textbook in that it does not use the idea of setting unused data members to MAXKEY, where MAXKEY>key for all key. Instead, we use a data member called n which holds the number of data elements stored in the node (either 1 or 2).

Version:
1.0
Author:
John Webb

Variable Index

o lChild
This node's left child (if node is not a leaf node), or left thread (if node is a leaf node)
o lData
This node's left data element
o mChild
This node's middle child
o parent
This node's parent.
o rChild
This node's right child (if node is not a leaf node), or right thread (if node is a leaf node)
o rData
This node's right data element

Constructor Index

o TwoThreeTreeNode()

Method Index

o addData(NodeData, TwoThreeTreeNode)
Add a NodeData object to a two-node.
o isLeaf()
Determine whether this is a leaf node.
o isThreeNode()
Determine whether this is a three-node.
o isTwoNode()
Determine whether this is a two-node.
o numElements()
Get number of data elements in this node.
o TwoThreeTreeNode(NodeData)
Create a new TwoThreeTreeNode, and add a NodeData object to the node.

Variables

o lData 
 public NodeData lData
This node's left data element

o rData 
 public NodeData rData
This node's right data element

o lChild 
 public TwoThreeTreeNode lChild
This node's left child (if node is not a leaf node), or left thread (if node is a leaf node)

o mChild 
 public TwoThreeTreeNode mChild
This node's middle child

o rChild 
 public TwoThreeTreeNode rChild
This node's right child (if node is not a leaf node), or right thread (if node is a leaf node)

o parent 
 public TwoThreeTreeNode parent
This node's parent. Though not strictly necessary (we could follow the threads and/or child links to find the parent) it was included for efficiency and ease of coding.

Constructors

o TwoThreeTreeNode 
 public TwoThreeTreeNode()

Methods

o TwoThreeTreeNode 
 public void TwoThreeTreeNode(NodeData nd)
Create a new TwoThreeTreeNode, and add a NodeData object to the node. 
  Inputs:
    nd (NodeData): the NodeData object to add to the new node.
  Outputs:
    none
  Preconditions:
    true
  Postconditions:
    a new TwoThreeTreeNode x exists such that x is a 2-node and
    x contains nd as it's only data element

o isTwoNode 
 public boolean isTwoNode()
Determine whether this is a two-node. 
  Inputs:
    none
  Outputs:
    isTwoNode (boolean): true if this node is a 2-node, false otherwise
  Preconditions:
    no two-nodes have non-null right data references
  Postconditions:
    true has been returned if this is a 2-node, false otherwise

o numElements 
 public int numElements()
Get number of data elements in this node. 
  Inputs:
    none
  Outputs:
    numElements (int): 2 if this is a 3-node, otherwise 1
  Preconditions:
    this node is either a 2-node or a 3-node
  Postconditions:
    numElements has been returned

o isThreeNode 
 public boolean isThreeNode()
Determine whether this is a three-node. 
  Inputs:
    none
  Outputs:
    isThreeNode (boolean): true if this node is a 3-node, false otherwise
  Preconditions:
    true
  Postconditions:
    true has been returned if this is a 3-node, false otherwise

o isLeaf 
 public boolean isLeaf()
Determine whether this is a leaf node. 
  Inputs:
    none
  Outputs:
    isLeaf (boolean): true if this node is a leaf node, false otherwise
  Preconditions:
    no leaf nodes have non-null middle children
  Postconditions:
    isLeaf is true if this is a leaf node, false otherwise

o addData 
 public void addData(NodeData data,
                     TwoThreeTreeNode subtree)
Add a NodeData object to a two-node. 
  Inputs:
    data (NodeData): the NodeData object to add to the node
    subtree (TwoThreeTreeNode): the subtree that will be added to the
      right right of the new data element.
  Outputs:
    none
  Preconditions:
    this node is a 2-node
  Postconditions:
    this node is a three-node containing data