• Implement a basic binary search tree methods.
• Gain familiarity with issues of search times and balance in binary search trees.
• Work with applets and visualizations of data structures.

1. Download the starter code for this assignment and get a project set up in Eclipse for it. Try running the starter code. It should display a 3-node binary tree.

   The starter code contains a file VisualBSTApplet.java which gives you a framework in which to implement your insert, find, and delete methods for binary search trees.

   (You should also implement the isEmpty, contains, predecessor, successor, and other methods as necessary to handle the following commands.)

2. Create a new project with a name such as BinarySearchTree, and make sure that the Visible Data Structure files are included in it.
3. Provide an implementation of a binary search tree abstract data type that supports the following methods:
   • INSERT (name). If name is not already in the tree, it is inserted, maintaining the binary search tree ordering property. (no return value)
   • DELETE (name). Removes the name if it is in the tree. Otherwise, does nothing. (no return value).
   • IS_EMPTY () -- returns true iff the tree is empty.
   • CONTAINS (name) -- returns true iff the tree contains the name.
   • PREDECESSOR (name) -- returns the name alphabetically immediately before this name, or NULL if name is the first element in the tree.
   • SUCCESSOR (name) -- returns the name alphabetically immediately after this name, or NULL if name is the last element in the tree.
   • DEPTH (name) -- returns the depth of name in the tree, or -1 if it's not in the tree.
   • HEIGHT (name) -- returns the height of name in the tree, or -1 if it's not in the tree.
   • INORDER_NUMBER (name) -- if name is the ith name in the tree (alphabetically), then returns i. Otherwise, returns -1.
   Note that the returned information should be shown in two places in your program: (1) the status line, and (2) the history window. You can easily do this by calling the following methods. Note that the string argument for the history window should end with a newline character. It starts with a semicolon so that the user can paste history window contents back into the command input area and the messages will be treated as comments.

   statusLine.setText("Message in status line");
   history.append("; Message in history window\n");
   

4. Modify the renderDS, drawTree, and drawNode methods so that your tree still appears clear but has a unique combination of visual attributes, such as color of the nodes and labels, fonts, possible borders on nodes, etc.
   Next to each node should be shown the following. They can be in a small font in order to save screen space (but they should scale, like the rest of the displayed data structure).
   • name
   • depth (e.g., "d=3")
   • height (e.g., "h=2")
   • inorder number (e.g., "i=12")

1. (10 points) Implement the storage and display of "data", in this case photographs that go with the keys (names). The new operations for the ADT are the following:
   • ASSOCIATE (name, photo) -- the photo should be specified by a filename (string), and should be in a folder within the project called "photos". If name has not already been inserted into the tree, this operation will also insert it. If there is already a photo for this key (name), the new photo will replace it.
   • UNASSOCIATE (name) -- any photo associated with this name is removed. But the name remains in the tree.
   The photo for each node that has a photo should be displayed (in a reduced size that depends on the viewing scale of the applet) on or next to the node. The other displayed properties (depth, height, inorder number) should still be visible.
2. (10 points) Implement AVL-tree rebalancing. The following new methods should be defined:
   • SINGLE_ROTATE (name). Perform a single rotation at the node corresponding to name, provided that a single-rotation is an appropriate way to improve the balance. The rotation should go in the direction that reduces the imbalance. If there is no imbalance at that node, or single rotation is not appropriate, the operation does nothing.
   • DOUBLE_ROTATE (name). Like SINGLE_ROTATE, but does a double rotation.
   • TURN_ON_AVL (). Subsequent INSERT and DELETE operations will be accompanied by processing for AVL rebalancing. Note: if this command is used at the beginning of a session, then the tree built by subsequent INSERT and DELETE commands will be an AVL tree. If, on the other hand, it is turned on after an arbitrary BST has been constructed, it does NOT automatically convert it to an AVL tree.
   • TURN_OFF_AVL (). Disables AVL-style rebalancing during INSERT and DELETE operations.

• [Oct. 15: See the implementation suggestions posted on GoPost. The following description of displaying a binary tree is no longer needed for this assignment, but might be interesting anyway.] Displaying a binary tree might seem at first to be a difficult challenge. However, the following strategy is simple, and it produces reasonably attractive results. (1) We'll imagine a grid of lines, spaced evenly -- maybe every 100 pixels (about every 2 cm). (2) For each node of the tree, we'll compute its inorder traversal number. The leftmost node gets 0, its successor to the right gets 1, etc. These numbers tell which vertical grid line (i.e., the x coordinate) the node goes on. (3) For each node, we'll compute its depth from the root. We'll use this number to tell which horizontal line (i.e., the y coordinate) the node goes on. (4) We'll store the coordinates as node instance attributes. (5) Before we paint the nodes on the screen, we paint the tree edges, using the coordinates of the nodes as the endpoints of the segments. (6) Finally, we paint the nodes of the tree at their appropriate coordinate locations. The node displays go nicely on top of the ends of the edges. If we had painted the nodes before the edges, then there would be some messy graphics where they overlapped.

INSERT penguin
INSERT aardvark
WAIT
IS_EMPTY
CONTAINS aardvark
INSERT bear
INSERT canary
WAIT
DELETE penguin
INSERT leopard
SUCCESSOR aardvark
SUCCESSOR penguin
PREDECESSOR aardvark
PREDECESSOR penguin
WAIT
INORDER_NUMBER aardvark
INORDER_NUMBER zebra
HEIGHT aardvark
DEPTH canary