CS683: Assignment 2

	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 12-Feb-03

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 pre-order or post-order. 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 pre-order traversal. Implement an aspect that uses the post-order 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 92182-7700 USA.
OpenContent license defines the copyright on this document.

visitors since 04-Feb-03