Fall Semester, 1998
Ternary Tree Solutions
© 1998, All Rights Reserved, SDSU & Roger Whitney
San Diego State University -- This page last updated 19-Oct-98
|
|
CS 596 Java Programming Fall Semester, 1998 Ternary Tree Solutions |
|
|---|---|---|
|
© 1998, All Rights Reserved, SDSU & Roger Whitney San Diego State University -- This page last updated 19-Oct-98 |
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.
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.
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() ) { addSecondKey( key, value ); return; } if ( key < smallKey ) { addLeft( key, value); return; } if ( smallKey == key ) { smallValue = value; return; } if ( key < largeKey ) { addMiddle( key, value); return; } if ( largeKey == key ) { largeValue = value; return; } if ( largeKey < key ) addRight( key, value ); }
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.
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() { return toString( this ); } 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 ) + " )"; }
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.
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.
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.
Solution
Put Time
Get Time
B
376
349
E
321
314
F
260
239
Solution
Put Time
Get Time
B
26
14
E
15
14
F
16
13
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.
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.
Solution
Put Time
Get Time
F (recursive)
15
12
I (iterative)
33
41
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; }
/** * 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 ); } }
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 + ")"; } }
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; }
/** * 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 }
/** * 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 ) addLeft( key, value); else if ( smallKey == key ) smallValue = value; else if ( key < largeKey ) addMiddle( key, value); else if ( largeKey == key ) largeValue = value; else if ( largeKey < key ) addRight( key, value ); } else // only have one key { addSecondKey( key, value ); } }
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; }
/** * 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 ); }
/** * 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 ); }
/** * 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; } } }
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 ); }
public void put( int key, Object value ) { if ( hasTwoKeys() ) { if ( smallKey.greaterThan( key ) ) addLeft( key, value); else if ( smallKey.equals( key ) ) smallKey.setValue( value); else if ( largeKey.greaterThan( key ) ) addMiddle( key, value); else if ( largeKey.equals( key ) ) largeKey.setValue( value); else if ( largeKey.lessThan( key ) ) addRight( key, value ); } else // only have one key { addSecondKey( key, value ); } }
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; }
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 ); }
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 ); }
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; } }
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; }
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 parent.addSubtree( key, value ); } /** * 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 ""; } }
/** * 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; }
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; }
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 { addSecondKey( key, value ); } }
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; }
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; }
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; } } }
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() {}
/** * 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 ) { ((TernaryNodeE) parent).addSubtree( key, value ); } public Object get( int key ) { return null; } public String toString() { return ""; } }
/** * 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 ); }
/** * 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 { addSecondKey( key, value ); } }
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; }
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; }
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; } } }
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; }
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 ); ((TernaryNodeF) parent).addSubtree( replacement ); } public Object get( int key ) { return null; } boolean keysLessThan( int aKey ) { return false; } public String toString() { return ""; } }
/** * 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 ); ((TernaryNodeF) parent).addSubtree( replacement ); } public Object get( int key ) { if ( key == smallKey) return smallValue; else return null; }
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; }
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 ); }
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; }
protected void addSubtree( NodeF subtree ) { if ( subtree.keysLessThan( smallKey) ) leftSubtree = subtree; else if ( subtree.keysLessThan( largeKey) ) middleSubtree = subtree; else rightSubtree = subtree; } }
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 ); parent.add( key, value ); } } public Object get( int key ) { if ( root == null ) return null; else { TernaryNodeI keysNode = find( key ); return keysNode.get( key ); } }
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; }
/** *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; }
/** * 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; }
/** * 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; }
public void add( int key, Object value ) { if ( ! hasTwoKeys() ) addSecondKey( key, value ); 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; } }
/** * 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.
All rights reserved.
visitors since 19-Oct-98