## References

Design Patterns: Elements of Resuable Object-Oriented Software , Gamma, Helm, Johnson, Vlissides, Addison-Wesley, 1995, Singleton Pattern

CS 635 Online lecture Notes on Singleton at: http://www.eli.sdsu.edu/courses/spring98/cs635/notes/singleton/singleton.html

"Null Object", Woolf, in Pattern Languages of Program Design 3 , Edited by Martin, Riehle, Buschmmann, Addison-Wesley, 1998, pp 5-18

CS 635 Online lecture Notes on Null Object at: http://www.eli.sdsu.edu/courses/spring98/cs635/notes/strategy/strategy.html

`Doc B, Ternary Tree Solutions Slide # 2`

## Ternary Tree Solution

There are a number of ways to implement the Ternary tree assignment. The ternary tree presents a number of issues that need to be addressed. Each issue can be solved in a number of ways. Some solutions to an issue may be better than other solutions. However, there are times when which solution is better depends on the details of the problem and the context of the problem. I will not have the time for a full discussion of the pros and cons of each solution presented here. CS 535 and CS635 will do that.

Issues
There are a number of basic issues (like how to create a tree structure, how to create a package, a class, an object) that will not be discussed here. The issues covered here are:

1. How to handle a node with one key
2. Dealing with the multiple special cases
3. Use a Tree and Node class or just a Node class
4. Iterative verse Recursive traversal of tree

### 1. Handling with a Node with one Key

There are a number approaches to deal the this situation: use a boolean flag to indicate that a key has not been set, use a special value for a key to indicate it has not been set, use objects to hold key-values, or use polymorphism. The first solution will not be shown. TernaryNodeB can be easily modified to use that solution.

`Doc B, Ternary Tree Solutions Slide # 3`

#### Special Value for a Key

Since keys can not be duplicated, we can set both keys to the same value to indicate that only one has been set. In solution A, TernaryNodeA does this in its constructor.

```public TernaryNodeA( int key, Object value )
{
smallKey = key;
smallValue = value;
largeKey = smallKey;
}
```

The test to determine if the node has one or two keys is just:

```if ( smallKey == largekey )
```

Solution A implements a recursive solution using a Node class with little decomposition. The source code for Solution A can be found on slide 13.
```
Doc B, Ternary Tree Solutions Slide # 4
```
Better Code
TernaryNodeA of solution A was hard to write. It took a lot longer to write and debug than TernaryNodeB of solution B, which was written first. Which do you find easier to read? Solution B still sets both keys to the same value to indicate that only one has been set. However, there is a method called hasTwoKeys(), which returns true if the node has two different keys. This the test to determine if the node has one or to keys is now:

```if ( hasTwoKeys() )
```

Solution B implements a recursive solution using a Node class with extra methods to improve readability. The source code for Solution B can be found on slide 17.

`Doc B, Ternary Tree Solutions Slide # 5`
A Style Question
In TernaryTreeB's put() method only one "if" statement can be true. Therefore, we can remove one level of if statements by using return statements. Is the following an improvement over the put method on TernaryTreeB?

```   public void put( int key, Object value ) {
if ( ! hasTwoKeys() )   {
return;
}
if ( key < smallKey ) {
return;
}

if (  smallKey == key  ) {
smallValue = value;
return;
}

if (  key < largeKey ) {
return;
}

if ( largeKey ==  key  ) {
largeValue = value;
return;
}

if ( largeKey < key )
}
Doc B, Ternary Tree Solutions Slide # 6
```

### Use Objects to hold key-values

If we use an object to hold the key-value pair then the test for determining if we have one or two keys is easy: check for null. TernaryNodeC of solution C shows this. The only difference between solution B and solution C is the use of the NodeData class to hold the key-value pair. Is this better than solution B? Can the NodeData be used better? Are there more methods that NodeData should have? Was the check for hasTwoKeys() that hard in solution B?

Solution C implements a recursive solution using a Node class with extra methods to improve readability and uses a NodeData class to hold key-value pairs. The source code for Solution C can be found on slide 24.
`Doc B, Ternary Tree Solutions Slide # 7`

### 2. Dealing with the Multiple Special Cases

One of the annoying things about this assignment is dealing with all the special cases: one or two keys, are each of the subtrees null or not. The reason that solutions A, B, and C do not fully implement the assignment is that I got tired of dealing with all the special cases! If we handle the recursion differently, we can reduce the checks for special cases. The following toString() method works in TernaryNodeB. This is much shorter than the toString() method in TernaryNodeB. Unfortunately, this method does not work well to reduce the checks for empty subtrees in put, get or contains. (Why?) Thus, it does not gain us much.

```public String toString()
{
}

private String toString( TernaryNodeB aNode )
{
if ( aNode == null )
return "";

if ( ! aNode.hasTwoKeys() )
return "( " + aNode.smallKey + " )";

return    "( " +
toString( aNode.leftSubtree ) + " " +  aNode.smallKey + " " +
toString( aNode.middleSubtree ) + " " + aNode.largeKey +
" " +    toString( aNode.rightSubtree ) + " )";
}
Doc B, Ternary Tree Solutions Slide # 8
```

#### Use a Leaf Node Class

Note, solution D contains advanced material. I did not expect you to think of this on you own. You may skip if it if you wish.

We can remove all the checks for subtrees that are null by making a special leaf node. The leaf node will handle the special case of reaching the end of the tree for the toString(), put(), contains() and get() methods. Note in TernaryNodeD the subtrees start with objects of type LeafNodeD.

```NodeD leftSubtree = new LeafNodeD( this );
NodeD middleSubtree  = new LeafNodeD( this );
NodeD rightSubtree  = new LeafNodeD( this );
```

Look closely at the toString() method. The toString() method in TernaryNodeD does not have to check for null subtrees. This is because the subtrees are never null. The methods in class LeafNodeD must act as if they are in a null subtree. The toString() method is easy, just do nothing. The put() method is more complex. The LeafNodeD needs to replace itself with a TernaryNodeD. The only way to do this is to have its parent change its subtree reference.

I used the interface NodeD rather than inheritance for two reasons. First, LeafNodeD and TernaryNodeD do not share any implementation. Second, it does not make much sense to make TernaryNodeD a child of LeafNodeD nor to make LeafNodeD a child of TernaryNodeD. Note that LeafNodeD requires a parent reference for the method put. I implemented the contains() method here. I leave the get method for you to work out .
```
```
Solution D implements a recursive solution using a Node class with extra methods to improve readability and a LeafNode to act like a null subtree. The source code for Solution D can be found on slide 30.
`Doc B, Ternary Tree Solutions Slide # 9`

#### Use Singleton Leaf Node Class

This section contains advanced material. You may skip if it if you wish.

One problem with solution D is the number of leaf nodes. In a tree than contains N normal nodes, there will be 2*N + 1 leaf nodes. This requires more memory and replaces null checks with method calls. We can use just one leaf node. Solution E differs from solution D only in that there is only one leaf node in the entire tree. This requires removing the parent pointer and adding a parameter to the put method. I used an abstract class (NodeE) to declare a package level access put with the new parameter.

Solution E implements a recursive solution using a Node class with extra methods to improve readability and a LeafNode to act like a null subtree. The tree only uses one LeafNode object. The source code for Solution E can be found on slide 38.
`Doc B, Ternary Tree Solutions Slide # 10`

#### Use SingleKey Nodes

This section contains advanced material. You may skip if it if you wish.

Solution F modifies solution D by using single key nodes. . The source code for Solution E can be found on slide 45. Now instead of having a number of cases that have to be addressed in one Node class, there is a separate Node class for each "case". Once you understand the concept, this makes it easier to write the code. Each class deals with just one situation: two keys, one key, no keys. The hard part becomes changing a node in the tree to a different type.

Interestingly using the separate classes tends to make the tree perform better. I timed solutions B, E, and F on a PowerMac with 266 MHz PPC processor. The code was compiled with Metrowerks Java compile Pro 4. I added 500 keys into a tree. The keys were added in order (1, 2, 3, ..., 500) to get some worst case performance. The following tables show the total time to perform all 500 puts. They also show the total time required to access each key with a get in the tree once. The code was timed using a non-JIT VM and a JIT VM. All times are in milliseconds. Wall time was measured.

 Metrowerks Non-JIT Pro 4 Solution Put Time Get Time B 376 349 E 321 314 F 260 239

 Apples MRJ JIT VM 2.1 Solution Put Time Get Time B 26 14 E 15 14 F 16 13

`Doc B, Ternary Tree Solutions Slide # 11`

### 3. Use a Tree and Node class or just a Node class

The task in assignment three seems small enough that we can get away with using a Node class without a separate Tree class, which would hold the node objects. See the next section.
`Doc B, Ternary Tree Solutions Slide # 12`

### 4. Iterative verses Recursive traversal of tree

All the solutions presented so far have been recursive. Once one understands recursion, it can make the code more compact, and even easier to write. The recursive version of toString() in solution F is:

```public String toString()
{
return "( " + leftSubtree.toString() + " " +
smallKey + " " + middleSubtree.toString() + " " +
largeKey + " " + rightSubtree.toString() + " )";
}
```

The source code for solution I, the iterative solution, starts on slide 51.

Recursive solutions have a major problem. If we add keys in order, say 1, 2, 3, ..., 500. Then the ternary tree degenerates into a linked list. Each node in the tree will have only one non-empty subtree. Thus, the toString method above will result in 250 method calls that will all be on the stack at the same time! One JVM had a stack overflow when adding the keys 1, 2, ..., 1349 into a tree. This is rather restrictive for a search tree. We could increase the stack space, but using an iterative implementation would be better. In general an iterative solution will be faster (one replaces method calls with a loop iteration) and does not require much stack space. Solution I gives an iterative implementation.

Interestingly, the recursive solution F seems faster than the iterative solution I. I timed solutions F and I on a PowerMac with 266 MHz PPC processor. The code was compiled with Metrowerks Java compile Pro 4. I added 500 keys into a tree. The keys were added in order (1, 2, 3, ..., 500) to get some worst case performance. The following tables show the total time to perform all 500 puts. They also show the total time required to access each key with a get in the tree once. The code was timed using a JIT VM. All times are in milliseconds. Wall time was measured.

 Apples MRJ JIT VM 2.1 Solution Put Time Get Time F (recursive) 15 12 I (iterative) 33 41

`Doc B, Ternary Tree Solutions Slide # 13`

## Solution A - Recursive, inline

```/**
* Solution A - an inline recursive Node solution to
* Ternary tree Assignment
*/
public class TernaryNodeA
{
private int smallKey;
private Object smallValue;

private int largeKey;
private Object largeValue;

private  TernaryNodeA leftsubtree;
private TernaryNodeA middlesubtree;
private TernaryNodeA rightsubtree;

public TernaryNodeA( int key, Object value )
{
smallKey = key;
smallValue = value;
largeKey = smallKey;
}

Doc B, Ternary Tree Solutions Slide # 14
/**
* Puts a key-value pair into the tree
* Can you follow the logic of this method?
* Compare it to the same method in solution B.
*/
public void put( int key, Object value )
{
if ( smallKey == largeKey )
{
if ( smallKey == key )
{
smallValue = value;
}
else if ( smallKey <  key )
{
largeKey = key;
largeValue = value;
}
else
{
largeKey = smallKey;
largeValue = smallValue;
smallKey = key;
smallValue = value;
}
return;
}
else if ( smallKey > key )
{
if ( leftsubtree == null )
leftsubtree = new TernaryNodeA( key, value );
else
leftsubtree.put( key, value );
}
else if (  smallKey == key  )
{
smallValue = value;
}
else if ( largeKey > key  )
{
if ( middlesubtree == null )
middlesubtree = new TernaryNodeA( key, value );
else
middlesubtree.put( key, value );
}
else if ( largeKey ==  key  )
{
largeValue = value;
}
else
{
if ( rightsubtree == null )
rightsubtree = new TernaryNodeA( key, value );
else
rightsubtree.put( key, value );
}
}

Doc B, Ternary Tree Solutions Slide # 15
public String toString()
{
String theTree = "(";

if ( leftsubtree != null )
theTree = theTree + leftsubtree;
theTree = theTree +  " " + smallKey + " " ;
if ( middlesubtree != null )
theTree = theTree + middlesubtree;

if ( largeKey != smallKey )
{
theTree = theTree + " " + largeKey + " ";
if ( rightsubtree != null )
theTree = theTree + rightsubtree;
}

return theTree + ")";
}
}
Doc B, Ternary Tree Solutions Slide # 16

Solution
B - Recursive, Modular

/**
* Solution B - a modular recursive Node solution to
* the Ternary tree Assignment
*/
public class TernaryNodeB
{
private int smallKey;
private  Object smallValue;

private int largeKey;
private Object largeValue;

private TernaryNodeB leftSubtree;
private TernaryNodeB middleSubtree;
private TernaryNodeB rightSubtree;

public TernaryNodeB( int key, Object value )
{
smallKey = key;
smallValue = value;
largeKey = smallKey;
}
Doc B, Ternary Tree Solutions Slide # 17
/**
* Reterns a value pair associated with the given key
*/
public Object get( int key )
{
// this method just selects which case we are in,
//calls other methods to actual perform the work

if ( hasTwoKeys() )
{
if ( key < smallKey )
return getLeft( key);

else if (  smallKey == key  )
return smallValue;

else if (  key < largeKey )
return getMiddle( key );

else if ( largeKey ==  key  )
return largeValue;

else if ( largeKey < key )
return getRight( key );
}
else if ( key == smallKey )
return smallValue;

return null; // key not in tree
}

Doc B, Ternary Tree Solutions Slide # 18
/**
* Puts a key-value pair into the tree
* Can you follow the logic of this method?
* Compare it to the same method in solution A.
*/
public void put( int key, Object value )
{
if ( hasTwoKeys() )
{
if ( key < smallKey )

else if (  smallKey == key  )
smallValue = value;

else if (  key < largeKey )

else if ( largeKey ==  key  )
largeValue = value;

else if ( largeKey < key )
}
else // only have one key
{
}
}

Doc B, Ternary Tree Solutions Slide # 19
public String toString()
{
if ( hasTwoKeys() )
{
String theTree = "(";

if ( leftSubtree != null )
theTree = theTree + leftSubtree;
theTree = theTree +  " " + smallKey + " " ;
if ( middleSubtree != null )
theTree = theTree + middleSubtree;

theTree = theTree + " " + largeKey + " ";
if ( rightSubtree != null )
theTree = theTree + rightSubtree;

return theTree + ")";
}

else //one key case
return "( " + smallKey + " )";
}
/**
* Returns true if two keys have been added to
* the node
*/
private boolean hasTwoKeys()
{
return smallKey != largeKey;
}

Doc B, Ternary Tree Solutions Slide # 20
/**
* Add the key-value pair to the leftsubtree
*/
private void addLeft( int key, Object value )
{
if ( leftSubtree == null )
leftSubtree = new TernaryNodeB( key, value );
else
leftSubtree.put( key, value );
}
private void addMiddle(  int key, Object value )
{
if ( middleSubtree == null )
middleSubtree = new TernaryNodeB( key, value );
else
middleSubtree.put( key, value );
}
private void addRight(  int key, Object value )
{
if ( rightSubtree == null )
rightSubtree = new TernaryNodeB( key, value );
else
rightSubtree.put( key, value );
}
Doc B, Ternary Tree Solutions Slide # 21
/**
* Get from the left subtee the value associated with the
* given key
*/
private Object getLeft( int key  )
{
if ( leftSubtree == null ) // no left subtree
return null;
else
return leftSubtree.get( key );
}
private Object getMiddle(  int key)
{
if ( middleSubtree == null )
return null;
else
return middleSubtree.get( key );
}
private Object getRight(  int key )
{
if ( rightSubtree == null )
return null;
else
return rightSubtree.get( key );
}

Doc B, Ternary Tree Solutions Slide # 22
/**
* Add the second key-value pair to the Node
*/
private void addSecondKey( int newKey, Object newValue )
{
if ( smallKey == newKey  )
{
smallValue = newValue;
}

else if ( smallKey <  newKey )
{
largeKey = newKey;
largeValue = newValue;
}

else
{
largeKey = smallKey;
largeValue = smallValue;
smallKey = newKey;
smallValue = newValue;
}
}
}
Doc B, Ternary Tree Solutions Slide # 23

Solution
C - Recursive, Modular, NodeData

/**
* Solution C - uses a modular recursive Node with
*  a NodeData object used to hold a key-value pair.
* The NodeData is the only difference from solution B
*/
public class TernaryNodeC
{
private NodeDataC smallKey;
private NodeDataC largeKey;

private TernaryNodeC leftSubtree;
private TernaryNodeC middleSubtree;
private TernaryNodeC rightSubtree;

public TernaryNodeC( int key, Object value )
{
smallKey = new NodeDataC( key, value );
}

Doc B, Ternary Tree Solutions Slide # 24
public void put( int key, Object value )
{
if ( hasTwoKeys() )
{
if ( smallKey.greaterThan( key ) )

else if (  smallKey.equals( key )  )
smallKey.setValue(  value);

else if (  largeKey.greaterThan( key ) )

else if ( largeKey.equals( key )  )
largeKey.setValue(  value);

else if ( largeKey.lessThan( key ) )
}
else // only have one key
{
}
}

Doc B, Ternary Tree Solutions Slide # 25
public String toString()
{
if ( hasTwoKeys() )
{
String theTree = "(";

if ( leftSubtree != null )
theTree = theTree + leftSubtree;
theTree = theTree +  " " + smallKey + " " ;
if ( middleSubtree != null )
theTree = theTree + middleSubtree;

theTree = theTree + " " + largeKey + " ";
if ( rightSubtree != null )
theTree = theTree + rightSubtree;

return theTree + ")";
}

else //one key case
return "( " + smallKey + " )";
}
private boolean hasTwoKeys()
{
return largeKey != null;
}

Doc B, Ternary Tree Solutions Slide # 26
private void addLeft( int key, Object value )
{
if ( leftSubtree == null )
leftSubtree = new TernaryNodeC( key, value );
else
leftSubtree.put( key, value );
}
private void addMiddle(  int key, Object value )
{
if ( middleSubtree == null )
middleSubtree = new TernaryNodeC( key, value );
else
middleSubtree.put( key, value );
}
private void addRight(  int key, Object value )
{
if ( rightSubtree == null )
rightSubtree = new TernaryNodeC( key, value );
else
rightSubtree.put( key, value );
}

Doc B, Ternary Tree Solutions Slide # 27
private void addSecondKey( int newKey, Object newValue )
{
if ( smallKey.equals( newKey ) )
smallKey.setValue(  newValue );

else if ( smallKey.lessThan( newKey ) )
largeKey = new NodeDataC( newKey, newValue );

else
{
largeKey = smallKey;
smallKey =  new NodeDataC( newKey, newValue );
}
}
}
/**
* Used to hold key-value pairs in the TernaryNode
*/
class NodeDataC
{
private int key;
private Object value;

public NodeDataC( int initialKey, Object initialValue)
{
key = initialKey;
value = initialValue;
}

public String toString()
{
return String.valueOf( key );
}

Doc B, Ternary Tree Solutions Slide # 28
public void setValue( Object newValue )
{
value = newValue;
}

public boolean equals( int aKeyValue )
{
return key == aKeyValue;
}
public boolean lessThan( int aKeyValue )
{
return key < aKeyValue;
}
public boolean greaterThan( int aKeyValue )
{
return key > aKeyValue;
}
}
Doc B, Ternary Tree Solutions Slide # 29

Solution
D - Recursive, Modular, LeafNodes

/**
* Solution D - uses a modular recursive Node and multiple
* leafNodes. The leaf nodes act like null (or empty) tree nodes
*/
/**
* Interface for different type of Nodes in the tree
*/
interface NodeD
{
public void put( int key, Object value );
public String toString();
public boolean contains( int key );
public Object get( int key );
}
/**
* LeafNodeD acts like an empty node in the subtree.
* Its methods perform the action required of an empty node.
*/
class LeafNodeD implements NodeD
{
//reference to the parent node of this node
TernaryNodeD parent;

public LeafNodeD( TernaryNodeD myParent )
{
parent = myParent;
}

Doc B, Ternary Tree Solutions Slide # 30
public void put( int key, Object value )
{
// Tell parent node to replace the current empty LeafNode
// with a regular TernaryNode with given key-value pair
}
/**
* Empty nodes do not have any key-value pairs or
* subtrees, so return null
*/
public Object get( int key )
{
return null;
}

public boolean contains( int key )
{
return false;
}

public String toString()
{
return "";
}
}
Doc B, Ternary Tree Solutions Slide # 31
/**
* Uses LeafNodes instead of null for empty subtrees. Note
* in the methods put(), get(), contains(), toString() there is no
* need to check of the subtrees are null, since they are never null.
*/
public class TernaryNodeD implements NodeD
{
private int smallKey;
private  Object smallValue;

private int largeKey;
private Object largeValue;

// Initialize subtrees to the empty LeafNodes
private NodeD leftSubtree = new LeafNodeD( this );
private NodeD middleSubtree  = new LeafNodeD( this );
private NodeD rightSubtree  = new LeafNodeD( this );

public TernaryNodeD( int key, Object value )
{
smallKey = key;
smallValue = value;
largeKey = smallKey;
}

Doc B, Ternary Tree Solutions Slide # 32
public boolean contains( int key )
{
if ( hasTwoKeys() )
{
if  (( key ==smallKey ) || ( key == largeKey ) )
return true;

else if (  key < smallKey  )
return leftSubtree.contains( key );

else if (  key < largeKey )
return middleSubtree.contains( key );

else if ( largeKey < key )
return rightSubtree.contains( key );
}
else // only have one key
{
return key == smallKey;
}
return false;
}

Doc B, Ternary Tree Solutions Slide # 33
public void put( int key, Object value )
{
if ( hasTwoKeys() )
{
if ( key < smallKey )
leftSubtree.put( key, value);

else if (  smallKey == key  )
smallValue = value;

else if (  key < largeKey )
middleSubtree.put( key, value);

else if ( largeKey ==  key  )
largeValue = value;

else if ( largeKey < key )
rightSubtree.put( key, value);
}
else // only have one key
{
}
}
Doc B, Ternary Tree Solutions Slide # 34
public Object get( int key )
{
if ( hasTwoKeys() )
{
if ( key < smallKey )
return leftSubtree.get( key);

else if (  smallKey == key  )
return smallValue;

else if (  key < largeKey )
return middleSubtree.get( key);

else if ( largeKey ==  key  )
return largeValue;

else if ( largeKey < key )
return rightSubtree.get( key);
}
else // only have one key
{
if ( key == smallKey)
return smallValue;
}
return null;
}

Doc B, Ternary Tree Solutions Slide # 35
public String toString()
{
if ( hasTwoKeys() )
return "( " + leftSubtree + " " +    smallKey + " " +
middleSubtree + " " + largeKey + " " +
rightSubtree + " )";

else //one key case
return "( " + smallKey + " )";
}
protected void addSubtree( int key, Object value )
{
if ( key < smallKey )
leftSubtree = new TernaryNodeD( key, value );
else if ( key < largeKey )
middleSubtree = new TernaryNodeD( key, value );
else if ( largeKey < key )
rightSubtree = new TernaryNodeD( key, value );
}

private boolean hasTwoKeys()
{
return smallKey != largeKey;
}

Doc B, Ternary Tree Solutions Slide # 36
private void addSecondKey( int newKey, Object newValue )
{
if ( smallKey == newKey  )
{
smallValue = newValue;
}

else if ( smallKey <  newKey )
{
largeKey = newKey;
largeValue = newValue;
}

else
{
largeKey = smallKey;
largeValue = smallValue;
smallKey = newKey;
smallValue = newValue;
}
}
}
Doc B, Ternary Tree Solutions Slide # 37

Solution
E - Recursive, Modular, Single LeafNode

/**
* Solution E - uses a modular recursive Node and only one
* leafNodes. The difference from solution D is the use of only
* one LeafNode in the entire tree.
*/
/**
* Use abstract class so could declare a package level method
* that the nodes must implement.
*/
abstract class NodeE
{
abstract public String toString();
abstract void put( int key, Object value, NodeE parent);
abstract public Object get( int key );
}
/**
* Singleton LeafNode. Since there is only one leaf node in the
* tree, it can not have a parent reference. The one node acts like
* the empty subtree for many TernaryNodes in the tree. This
* requires a parent reference be passed in the put method
*/
class LeafNodeE extends NodeE
{
private static final LeafNodeE singleton = new LeafNodeE();

// Hide constructor to insure no one makes multiple objects
// from this class
private LeafNodeE() {}

Doc B, Ternary Tree Solutions Slide # 38
/**
* Return a LeafNode object
*/
public static  LeafNodeE getInstance()
{
return singleton;
}

/**
* @param parent the Ternary node that sent the message to
*       this node
*/
void put( int key, Object value, NodeE parent )
{
}
public Object get( int key )
{
return null;
}
public String toString()
{
return "";
}
}
Doc B, Ternary Tree Solutions Slide # 39
/**
* The only difference from TernaryNodeD is the need to use
* LeafNodeE.getInstance() to get a LeafNode.
*/
public class TernaryNodeE extends NodeE
{
private int smallKey;
private  Object smallValue;

private int largeKey;
private Object largeValue;

NodeE leftSubtree = LeafNodeE.getInstance();
NodeE middleSubtree  = LeafNodeE.getInstance();
NodeE rightSubtree  = LeafNodeE.getInstance();

public TernaryNodeE( int key, Object value )
{
smallKey = key;
smallValue = value;
largeKey = smallKey;
}

public void put( int key, Object value )
{
put( key, value, null );
}
Doc B, Ternary Tree Solutions Slide # 40
/**
* Note that following method does not use the parameter
* parent.  The similar method in LeafNode needs the parameter. Since the sender
* of this method does not know which object it is sending the message to, the
* parameter is needed here. The whole point of LeafNode class is to avoid
* checking for what type object we are dealing with
*/
void put( int key, Object value, NodeE parent )
{
if ( hasTwoKeys() )
{
if ( key < smallKey )
leftSubtree.put( key, value, this);

else if (  smallKey == key  )
smallValue = value;

else if (  key < largeKey )
middleSubtree.put( key, value, this);

else if ( largeKey ==  key  )
largeValue = value;

else if ( largeKey < key )
rightSubtree.put( key, value, this );
}
else // only have one key
{
}
}

Doc B, Ternary Tree Solutions Slide # 41
public Object get( int key )
{
if ( hasTwoKeys() )
{
if ( key < smallKey )
return leftSubtree.get( key);

else if (  smallKey == key  )
return smallValue;

else if (  key < largeKey )
return middleSubtree.get( key);

else if ( largeKey ==  key  )
return largeValue;

else if ( largeKey < key )
return rightSubtree.get( key);
}
else // only have one key
{
if ( key == smallKey)
return smallValue;
}
return null;
}

Doc B, Ternary Tree Solutions Slide # 42
public String toString()
{
if ( hasTwoKeys() )
return "( " + leftSubtree + " " +    smallKey + " " +
middleSubtree + " " + largeKey + " " +
rightSubtree + " )";

else //one key case
return "( " + smallKey + " )";
}
protected void addSubtree( int key, Object value )
{
if ( key < smallKey )
leftSubtree = new TernaryNodeE( key, value );
else if ( key < largeKey )
middleSubtree = new TernaryNodeE( key, value );
else if ( largeKey < key )
rightSubtree = new TernaryNodeE( key, value );
}

private boolean hasTwoKeys()
{
return smallKey != largeKey;
}

Doc B, Ternary Tree Solutions Slide # 43
private void addSecondKey( int newKey, Object newValue )
{
if ( smallKey == newKey  )
{
smallValue = newValue;
}

else if ( smallKey <  newKey )
{
largeKey = newKey;
largeValue = newValue;
}

else
{
largeKey = smallKey;
largeValue = smallValue;
smallKey = newKey;
smallValue = newValue;
}
}
}
Doc B, Ternary Tree Solutions Slide # 44

Solution
F - Recursive, Three Node Types

/**
* Solution F - uses a modular recursive Node and three different
* types of Nodes. A singleton LeafNode for empty subtrees,
* SingleKeyNode for nodes with just one key, and TernayNode for
* nodes with two keys. So there is a class for each different case.
*/
abstract class NodeF
{
abstract public String toString();
abstract void put( int key, Object value, NodeF parent);
abstract boolean keysLessThan( int aKey);
abstract public Object get( int key );
}
class LeafNodeF extends NodeF
{
private static final LeafNodeF singleton = new LeafNodeF();

private LeafNodeF() {}

public static  LeafNodeF getInstance()
{
return singleton;
}

Doc B, Ternary Tree Solutions Slide # 45
void put( int key, Object value, NodeF parent )
{
// Create the replacement node for this node
// after the add. Have parent replace this node with
// the replacement. Creating the replacement here
// protects the parent node from having to know what type of
// node to use for the replacement

SingleKeyNodeF replacement =
new SingleKeyNodeF( key, value );
}
public Object get( int key )
{
return null;
}
boolean keysLessThan( int aKey )
{
return false;
}
public String toString()
{
return "";
}
}
Doc B, Ternary Tree Solutions Slide # 46
/**
* This class represents a node in the tree that contains only one
* key.
*/
class SingleKeyNodeF extends NodeF
{
private int smallKey;
private Object smallValue;

public SingleKeyNodeF(int key, Object value )
{
smallKey = key;
smallValue = value;
}

void put( int key, Object value, NodeF parent )
{
// See note in LeafNodeF.put()
TernaryNodeF replacement;
if (smallKey < key )
replacement= new TernaryNodeF( smallKey, smallValue, key, value );
else
replacement= new TernaryNodeF( key, value, smallKey, smallValue );
}
public Object get( int key )
{
if ( key == smallKey)
return smallValue;
else
return null;
}
Doc B, Ternary Tree Solutions Slide # 47
public String toString()
{
return "( " + smallKey + " )";
}
boolean keysLessThan( int aKey )
{
return smallKey < aKey;
}
}

/**
* Note that in this class there is no need to check for
* null subtrees or if the Node has two keys!
*/
public class TernaryNodeF extends NodeF
{
private int smallKey;
private  Object smallValue;

private int largeKey;
private Object largeValue;

private NodeF leftSubtree = LeafNodeF.getInstance();
private NodeF middleSubtree  = LeafNodeF.getInstance();
private NodeF rightSubtree  = LeafNodeF.getInstance();

public TernaryNodeF( int leftKey, Object leftValue, int rightKey,
Object rightValue  )
{
smallKey = leftKey;
smallValue = leftValue;
largeKey = rightKey;
largeValue = rightValue;
}
Doc B, Ternary Tree Solutions Slide # 48
public void put( int key, Object value )
{
put( key, value, null );
}
void put( int key, Object value, NodeF parent )
{
if ( key < smallKey )
leftSubtree.put( key, value, this);

else if (  smallKey == key  )
smallValue = value;

else if (  key < largeKey )
middleSubtree.put( key, value, this);

else if ( largeKey ==  key  )
largeValue = value;

else if ( largeKey < key )
rightSubtree.put( key, value, this );
}

Doc B, Ternary Tree Solutions Slide # 49
public Object get( int key )
{
if ( key < smallKey )
return leftSubtree.get( key);

else if (  smallKey == key  )
return smallValue;

else if (  key < largeKey )
return middleSubtree.get( key);

else if ( largeKey ==  key  )
return largeValue;

else if ( largeKey < key )
return rightSubtree.get( key);
return null;
}

public String toString()
{
return "( " + leftSubtree + " " +    smallKey + " " +
middleSubtree + " " + largeKey + " " +
rightSubtree + " )";
}
boolean keysLessThan( int aKey )
{
return largeKey < aKey;
}
Doc B, Ternary Tree Solutions Slide # 50
protected void addSubtree( NodeF subtree )
{
if ( subtree.keysLessThan( smallKey) )
leftSubtree = subtree;
else if ( subtree.keysLessThan( largeKey)   )
middleSubtree = subtree;
else
rightSubtree = subtree;
}
}
Doc B, Ternary Tree Solutions Slide # 51

Solution
I - Iterative

/**
* Solution I - uses a modular Tree class, which uses iteration to
* traverse through its Node objects. Only use one Node class.
*/
public class TreeI
{
TernaryNodeI root;

public void put( int key, Object value)
{
if ( root == null )
root = new TernaryNodeI( key, value);
else
{
TernaryNodeI parent = find( key );
}
}

public Object get( int key )
{
if ( root == null )
return null;
else
{
TernaryNodeI keysNode = find( key );
return keysNode.get( key );
}
}
Doc B, Ternary Tree Solutions Slide # 52
public boolean contains( int key )
{
if ( root == null )
return false;
else
{
TernaryNodeI keysNode = find( key );
return keysNode.containsKey( key );
}
}

/**
* If key is in tree return node containing the key.
* If key is not in tree return the node to which the key
* should be added, which is either a Node with one key or
* a parent Node with two keys and an empty subtree where
* the key belongs. This allows this one method to be used by the
* put(), get() and contains() methods.
*/
private TernaryNodeI find( int key )
{
TernaryNodeI current = root;
TernaryNodeI previous = null;

while ( (current != null) && ( ! current.containsKey( key )))
{
previous = current;
current = current.find( key );
}
if ( current == null )
return previous;
else
return current;
}
Doc B, Ternary Tree Solutions Slide # 53
/**
*Ran out of time to make the toString() iterative.
*/
public String toString()
{
return root.toString();
}
}
class TernaryNodeI
{
private int smallKey;
private  Object smallValue;

private int largeKey;
private Object largeValue;

private TernaryNodeI leftSubtree;
private TernaryNodeI middleSubtree;
private TernaryNodeI rightSubtree;

public TernaryNodeI( int key, Object value )
{
smallKey = key;
smallValue = value;
largeKey = smallKey;
}

Doc B, Ternary Tree Solutions Slide # 54
/**
* Return value associated with the given key if
* this Node contains the key. Otherwise return null
*/
public Object get( int key )
{
if ( key == smallKey )
return smallValue;
else if ( key == largeKey )
return largeValue;
else
return null;
}

public boolean containsKey( int key )
{
if ( smallKey == key || largeKey == key )
return true;
else
return false;
}

Doc B, Ternary Tree Solutions Slide # 55
/**
* If key is in this node return  this node
* If key is not in this node to return the subtree to
*  which the key belongs.
* If that subtree is null return this node.
*/
public TernaryNodeI find( int key )
{
if ( hasTwoKeys() )
{
if ( key < smallKey )
return leftSubtree;

else if ( key == smallKey )
return this;

else if ( key < largeKey )
return middleSubtree;

else if ( key == largeKey )
return this;

else if ( key > largeKey)
return rightSubtree;
}
else if ( key == smallKey )
return this;
return null;
}

public boolean hasTwoKeys()
{
return smallKey != largeKey;
}
Doc B, Ternary Tree Solutions Slide # 56
public void add( int key, Object value )
{
if ( ! hasTwoKeys() )
else if ( key < smallKey )
leftSubtree = new TernaryNodeI( key, value );
else if ( key == smallKey )
smallValue = value;
else if ( key < largeKey )
middleSubtree = new TernaryNodeI( key, value );
else if ( key == largeKey )
largeValue = value;
else if ( largeKey < key )
rightSubtree = new TernaryNodeI( key, value );
}

void addSecondKey( int newKey, Object newValue )
{
if ( smallKey == newKey  )
{
smallValue = newValue;
}
else if ( smallKey <  newKey )
{
largeKey = newKey;
largeValue = newValue;
}
else
{
largeKey = smallKey;
largeValue = smallValue;
smallKey = newKey;
smallValue = newValue;
}
}
Doc B, Ternary Tree Solutions Slide # 57
/**
* Ran out of time to make toString() iterative
*/
public String toString()
{
if ( hasTwoKeys() )
{
String theTree = "(";

if ( leftSubtree != null )
theTree = theTree + leftSubtree;
theTree = theTree +  " " + smallKey + " " ;
if ( middleSubtree != null )
theTree = theTree + middleSubtree;

theTree = theTree + " " + largeKey + " ";
if ( rightSubtree != null )
theTree = theTree + rightSubtree;

return theTree + ")";
}

else //one key case
return "( " + smallKey + " )";
}
}

Copyright © 1998 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.