CSSE 230
Editor Trees Programming Assignment

Milestones

Overview

You'll complete this assignment in teams of three (or two, depending on the number of students in the class).

In this project you will write methods of a class that could be the "behind the scenes" data structure used by a text editor. Each piece of text will be represented as a height-balanced tree with rank (and possibly some other features, for example, parent pointers and/or threads). Each node contains a single character. Note that an EditTree is not an AVL tree in the traditional sense, since the order of nodes reflects their position within the tree's text rather than an alphabetical ordering of the characters in the tree. To repeat, this is not a Binary Search Tree. For example, the text "SLIPPERY" could be represented by the height-balanced tree at the right.

You will focus on data structures and algorithms, rather than user interface. You are welcome to create a user interface as a front end to the EditTree class that you will build, but this is not required (and there will be no extra credit for doing so).

Learning Objectives

Implement a complex data structure and associated algorithms.

Read algorithm descriptions in a language other than Java, and use them as a basis for your your Java code.

Gain additional practice with team skills.

Requirements

You must implement all of the methods whose stubs are in the provided EditTree code.  Each method that creates or modifies a tree must leave all trees height-balanced. Most of the requirements (including big-oh bounds on worst-case runtime) are presented to you as comments in that code, because context should make them clearer. 

By Milestone 2, the following methods must run in O(log N) time, where N is the size (number of nodes) in the largest tree involved in the operation.

• add(char c)
• add(char c, int pos)
• delete(int pos)
• concatenate(EditTree other): see note
• split(int pos): see note
• delete(int start, int length)
• get(int pos)
• height( )

Note: details on how to do concatenate and split in O(log N) time can be found here. The excerpt is from Reingold and Hansen, Data Structures In Pascal, pages 334-368.

The following methods must run in O(N) time, where N is the size (number of nodes) in the tree involved in the operation.

• size( )
• toString( )
• EditTree(String s)
• EditTree(EditTree e)

There are no running time requirements on the other methods you are to write, unless specified in the javadoc on the stubs.

The following required method is for grading purposes only:  int totalRotationCount(), which returns the total number of rotations done in this tree since the tree was first created. A single rotation adds 1 to this count, a double rotation adds two.

Be sure to commit your versions often as you go, and mark your Milestone 1 submission clearly in your commit log!

Design Considerations

Certain operations would be really easy to implement if you didn't care about efficiency.

In order to do certain operations efficiently, like add() and get(), you already know that you need extra data in your nodes, like balance code and rank. However, you should consider whether or not you want to add yet more data:

• Each node could store a pointer to its parent.
• Leaf nodes could have NULL_NODEs as children
• Leaf nodes could have threads to other nodes (as in the written assignment)
• The tree could have a dummy node that points to the root

These might work well for you if you are willing to make some tradeoffs. For example, the drawback with adding more data is that you need to keep it up to date when you make changes to the tree.

Another decision you'll need to make is how to how to traverse your tree. For instance, when adding a node, you'll need to walk down the tree to figure out where to insert it, and back up to figure out if it needs to be rotated. How will you do this traversal? It may depend on the method. Some options:

• Use recursion (return from recursion to move back up the tree)
• Loop, and maintain your own stack of nodes traversed
• Add a parent pointer to each node
• Add inorder threads

A Quick and Dirty Visualization program

This should give you a visual way to check whether your rotations are working and whether they are correctly setting balance codes and ranks.

It does not produce pretty trees, and the trees sometimes extend outside the windows, but you are likely to find it helpful. If you want "pretty" you can adapt your Diaplayable code to show the extra information. You may have to adapt the given code a little bit, depending on how you named your fields, whether you use a NULL_NODE, etc. The Java codefor this class is here.  Also see http://en.wikipedia.org/wiki/Q%26D 

Final notes

More test cases may be added:  This is a relatively new assignment. It is highly likely that some revised and new test cases will be added as we go along. In particular, none of the current testCases use totalRotationCount.