CSSE 230
Editor Trees Programming Assignment (For Face-face classes!)

Milestones

1 (55 pts) Implement and test: add(char c, int pos) and add(char c) plus (for testing purposes) EditTree(), EditTree(char), get(int pos), height(), totalRotationCount(), toDebugString() and toString(). Tree must be kept height-balanced.
2 (55 pts) All of the above, plus: delete(int pos), size(), and EditTree(EditTree e). Tree must be kept height-balanced.
3 (150 pts) Final submission of all code: all of the above, plus EditTree(String s), split(int pos), concatenate(EditTree other), find(String s), find(String s, int pos), and get(int pos, int length). Includes correctness, efficiency constraints (see below), and style.

Overview

EditorTrees is the major team project, as described in the syllabus.

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). 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. You will not write an interface with this. (Of course, we could always have you build a text editor interface as a later project.)

Learning Objectives

Implement a complex data structure and associated algorithms. 

    More than any other in this course, this project will require you to design your algorithm ahead of time and to use your debugger.

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. 

These 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). It is particularly important to get this one right, as later unit tests build on it. 
  • delete(int pos)
  • concatenate(EditTree other): see note
  • split(int pos): see note. This one can run in O((log n)2) time.
  • delete(int start, int length)
  • get(int pos)
  • height( )
  • size( ): If you take advantage of rank, this is easy. 

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

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

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

Finally, get(pos, length)  must be O(length * log N). There are no running time requirements on the other methods you are to write.

 

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 and Milestone 2 submissions clearly in your commit log, so that we will know which one to grade!

 EditTree class
Node class
Code enum

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, a balance code. Here is another data member that is needed to implement the List interface efficiently: rank. First, some background. To access a node by index, that each node needs some way of figuring out that index it is in the tree. It would be nice if each node stored its index, but there is one problem: if you do an add(), then the index of every node after the added node would have to be incremented, and this takes longer than O(log n) time. Instead, we'll have each node store its own rank. Rank is defined as the 0-based index of the node within its own subtree (the one rooted at that node). If you check this, you'll see that it also happens to be the size of the node's left subtree. Ranks can be used to compute indices as you move down the tree, and can be updated after an add or delete in O(log n) time. Your code will need to:

  1. Use rank to efficiently determine whether to go left or right to find an index.
  2. Increment the ranks of certain nodes as you go down the tree in .add().
  3. Update the ranks of 1-2 nodes when certain rotations are done.

You should also consider whether or not you want to add yet more data beyond balance code and rank:

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 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:

Finally, you'll notice that Node isn't an inner class of EditTree, because both classes are fairly large. Many methods like add() require access to the root of the tree, which may need to be updated during a rotation. To account for this, I chose to do much of my work in the EditTree class instead of the Node class.
 

A Quick and Dirty Visualization program

Your repository contains a package called debughelp. In that package are two classes, developed by CSSE230 student Philip Ross, that display the tree nicely in a window, complete with rank and balance code. You may use them if you like. The package also contains a sample of the output from the program, and a README with instructions about what extra fields and methods you'll need to add if you choose to use it.

Grading

Correctness is still king. Unit tests will be a large part of the points.

Efficiency is still important. As stated above, some of these operations could be implemented very easily if we didn't care about efficiency. The purpose of this assignment is for you to learn how to implement efficient algorithms for maintaining balanced trees. So correctness is only part of the assignment. Solutions that pass all the unit tests but are inefficient will only earn a small fraction of the points.

Documentation and style do count for something. As you go, please add internal comments to small blocks of code to capture WHY you are writing the code that way. If you put comments later, the temptation is just to say WHAT you did for each line (which can just be determined from the code and is pretty useless, like: node = node.right // move to the right 

How do you check if your code is O(log n)? Unless you need to traverse the tree, then at every node navigate either to the left or to the right child. A traversal is when you have to pass down both sides, this type of operation will be O(n). And when you are re-balancing the tree, you should only take one path up the tree, rebalancing as you go and stopping as soon as you can - DON'T create a rebalance() method that traverses the entire tree!

The test files for Milestones 2 and 3 may be updated.