
CS 683 Emerging Technologies
Spring Semester, 2003
Assignment 2



Assignment Index
© 2003, All Rights Reserved, SDSU & Roger Whitney
San Diego State University  This page last updated 12Feb03


Binary
Search Trees
We
will use binary search trees to explore some features of aspects.
You
will implement a binary search tree that contains a key and a value. The tree
is ordered by the key. It does not have to be a balanced tree. The keys can be
integers. The method add(key, value) should be used to add elements to the
tree. The method get(key) should return the value stored in the node that
contains the given key. There is no need to handle duplicate keys in the tree.
(Modified Feb 12) Have two add methods in your Tree (or node or what ever names(s) you are using in your code). The first add method is:
void add(int key, int value) { /* no code in the this method */ }
The second is:
void add(int key, Object value) {
/* put code here to do the add*/
}
The first add method does nothing. The second actually does the work of adding. You are to write an aspect using advise to trap all add(int, int) calls and use the add(int, Object) method to perform the add into the tree. This is intended only as an exercise is using aspects. This does not mean to imply that is how one should actually do this in a binary tree. (End modification)
The
second issue is multiple traversal algorithms. One can traverse a binary search
tree in several different ways, for example in preorder or postorder. One
could have a preOrderTraversal and a postOrderTraveral method on the tree. We
want just one method called traverse() on the tree. It will return a collection
(Vector, ArrayList or an array  your choice) of the elements in the tree in
the order visited by the traversal algorithm. Implement traverse() in the tree
classes to do preorder traversal. Implement an aspect that uses the postorder
algorithm when traverse() is used on a tree.
The
third issue is the use of the nil nodes in the tree. In typical binary search
tree implementation boundary conditions make the code messy: one continually
checks to see if the subtrees exist or not. For example on gets something like:
public class BinaryNode extends Node {
Node left;
Node right;
int key;
public boolean includes( int value ) {
if (key == value)
return true;
else if value < key ){
if (left == null)
return false;
else
return left.includes( value );
}
else {
if (right == null)
return false;
else
return right.includes( value );
}
}
Using
a NullNode that represents an empty leaf node in the tree we get:
public class BinaryNode extends Node {
Node left = new NullNode();
Node right = new NullNode();
int key;
public boolean includes( int value ) {
if (key == value)
return true;
else if (value < key )
return left.includes( value );
else
return right.includes(value);
}
}
public class NullNode extends Node {
public boolean includes( int value ) {
return false;
}
}
That
is we use polymorphism to a message to a node. The node does the correct thing
for its type. There are several problems. First is that we may end up creating
a lot of NullNodes (you should be able to compute how many). Since a NullNode
is an empty leaf node it does not have any data so we can use just one NullNode
object for the entire tree (singleton pattern for those that know the term).
The other problem is adding a new element to the tree. This requires replacing
a NullNode with a regular node. We can do something like:
public class BinaryNode extends Node {
Node left = new NullNode( this);
Node right = new NullNode( this);
int key;
public void addKey( int newKey ) {
if (key == newKey )
return;
else if (newKey < key )
return left.addKey( newKey );
else
return right.includes(newKey );
}
viod addNode( BinaryNode newChild) {
code to add the new child
}
}
public class NullNode extends Node {
BinaryNode parent;
public NullNode(BinaryNode parent) {
this.parent = parent;
}
public void addKey( int newKey ) {
parent.addNode( new BinaryNode( newKey));
}
}
However
this requires the NullNode to know its parent. We cannot use this solution if
we wish to use one NullNode for the entire tree. It is possible to use the
NullNode that does not know it parent, is not passed any reference to the
parent and when (in the above example) addKey is sent to the NullNode object an
aspect is used to add the new child node to the correct Binary node. The third
part of your assignment is to do this.
See
http://www.eli.sdsu.edu/courses/spring02/cs635/notes/null/null.html
for more on the Null node in a binary search tree.
Copyright ©, All rights reserved.
2003 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 921827700 USA.
OpenContent license defines the copyright on this document.
_{
} visitors since 04Feb03