/ Published in: Java
Data Structures & Algorithm Analysis Project
Expand |
Embed | Plain Text
Copy this code and paste it in your HTML
package editortrees; // A height-balanced binary tree with rank that could be the basis for a text editor. public class EditTree { public Node root; private int size; int totalRotationCount; /** * Construct an empty tree */ public EditTree() { this.root = Node.NULL_NODE; this.size = 0; this.totalRotationCount = 0; } /** * Construct a single-node tree whose element is c * * @param c */ public EditTree(char c) { this.root = new Node(c); this.size = 1; this.totalRotationCount = 0; } /** * Create an EditTree whose toString is s. This can be done in O(N) time, * where N is the length of the tree (repeatedly calling insert() would be * O(N log N), so you need to find a more efficient way to do this. * * @param s */ this.root = new Node('x'); this.root.buildStringTree(s); this.size = this.root.size; this.totalRotationCount = 0; } /** * Make this tree be a copy of e, with all new nodes, but the same shape and * contents. * * @param e */ public EditTree(EditTree e) { if (e.root != Node.NULL_NODE) { this.root = new Node(); this.root.editTreeCopy(e.root); this.size = e.size; this.totalRotationCount = e.totalRotationCount; } else { this.root = Node.NULL_NODE; this.size = 0; this.totalRotationCount = 0; } } /** * * @return the height of this tree */ public int height() { return this.root.height; } /** * * returns the total number of rotations done in this tree since it was * created. A double rotation counts as two. * * @return number of rotations since tree was created. */ public int totalRotationCount() { return this.totalRotationCount; } /** * return the string produced by an inorder traversal of this tree */ @Override if (this.root == Node.NULL_NODE) { return ""; } return this.root.toString(); } /** * * @param pos * position in the tree * @return the character at that position * @throws IndexOutOfBoundsException */ if (pos < 0 || pos >= this.size || this.root == Node.NULL_NODE) { } return this.root.get(pos).element; } /** * * @param c * character to add to the end of this tree. */ public void add(char c) { if (this.root == Node.NULL_NODE) { this.root = new Node(c); this.size++; } else { this.add(c, this.size); } } /** * * @param c * character to add * @param pos * character added in this inorder position * @throws IndexOutOfBoundsException * id pos is negative or too large for this tree */ if (pos < 0 || pos > this.size) { } if (this.root == Node.NULL_NODE) { this.root = new Node(c); } else { this.root.add(c, pos, this); } this.size++; } /** * * @return the number of nodes in this tree */ public int size() { return this.size; } /** * * @param pos * position of character to delete from this tree * @return the character that is deleted * @throws IndexOutOfBoundsException */ if (pos < 0 || pos >= this.size || this.root == Node.NULL_NODE) { } if (this.size == 1) { char temp = this.root.element; this.root = Node.NULL_NODE; this.size = 0; return temp; } return this.root.get(pos).delete(this); } /** * This method operates in O(length*log N), where N is the size of this * tree. * * @param pos * location of the beginning of the string to retrieve * @param length * length of the string to retrieve * @return string of length that starts in position pos * @throws IndexOutOfBoundsException * unless both pos and pos+length-1 are legitimate indexes * within this tree. */ if (pos < 0 || (pos + length) > this.size) { } Node start = this.root.get(pos); return start.getString(length); } /** * This method is provided for you, and should not need to be changed. If * split() and concatenate() are O(log N) operations as required, delete * should also be O(log N) * * @param start * position of beginning of string to delete * * @param length * length of string to delete * @return an EditTree containing the deleted string * @throws IndexOutOfBoundsException * unless both start and start+length-1 are in range for this * tree. */ public EditTree delete(int start, int length) if (start < 0 || start + length >= this.size()) (start < 0) ? "negative first argument to delete" : "delete range extends past end of string"); EditTree t2 = this.split(start); EditTree t3 = t2.split(length); this.concatenate(t3); return t2; } /** * Append (in time proportional to the log of the size of the larger tree) * the contents of the other tree to this one. Other should be made empty * after this operation. * * @param other * @throws IllegalArgumentException * if this == other */ if (this == other) { } if (other.root == Node.NULL_NODE) { // do nothing } // If the original tree was empty it is just replaced with the other // tree. else if (this.root == Node.NULL_NODE) { this.root = new Node(); this.root = other.root; this.size = other.size; other.size = 0; other.root = Node.NULL_NODE; } // If the trees are both of size 1 then the new tree is just the old // with the root's right the old root of the other tree. else if (this.size == 1 && other.size == 1) { this.root.right = other.root; this.root.right.parent = this.root; this.root.size++; this.size++; other.size = 0; other.root = Node.NULL_NODE; } // Traverses down to the far left leaf of the tree being concatenated to // the old tree and calls the Node concatenate method at that node. else { Node current = other.root; // Finds the far left leaf and adjusts sizes and ranks accordingly. while (current.left != Node.NULL_NODE) { current.rank--; current.size--; current = current.left; } this.root.concatenate(other.root, current); if (this.root.parent != Node.NULL_NODE) { this.root = this.root.parent; } // Fixes the trees' sizes and empties the other tree. this.size = this.size + other.size; other.size = 0; other.root = Node.NULL_NODE; } } /** * This operation must be done in time proportional to the height of this * tree. * * @param pos * where to split this tree * @return a new tree containing all of the elements of this tree whose * positions are >= position. Their nodes are removed from this * tree. * @throws IndexOutOfBoundsException */ if (pos < 0 || pos >= this.toString().length()) { "Invalid request!"); } EditTree[] trees = new EditTree[2]; trees = this.root.get(pos).split(); this.root = trees[0].root; if (this.root != Node.NULL_NODE) { this.setTreeSize(); } if (trees[1].root != Node.NULL_NODE) { trees[1].setTreeSize(); } return trees[1]; } /** * Don't worry if you can't do this one efficiently. * * @param s * the string to look for * @return the position in this tree of the first occurrence of s; -1 if s * does not occur */ if (!this.toString().contains(s)) { return -1; } return this.toString().indexOf(s); } /** * * @param s * the string to search for * @param pos * the position in the tree to begin the search * @return the position in this tree of the first occurrence of s that does * not occur before position pos; -1 if s does not occur */ if (!current.contains(s)) { return -1; } return current.indexOf(s) + pos; } /** * @return The root of this tree. */ public Node getRoot() { return this.root; } /** * Sets the tree size. */ public void setTreeSize() { this.size = this.root.left.size + this.root.right.size + 1; } }