Implement a Countdown Tree, in the file CountdownTree.java. This is a balanced search tree that uses partial rebuilding in a manner similar to scapegoat trees (see OpenDataStructures.org: Scapegoat Trees).

Every countdown tree has a float parameter d, defined when it is created. We call this the tree's countdown delay factor.

Each node u in a countdown tree has an int countdown timer, u.timer. When a new node is created, it's timer is set to Math.ceil(d).

When a node u's timer reaches 0, the node explodes, and the entire subtree rooted at u is rebuilt into a perfectly balanced binary search tree (note that u is probably not the root of this new subtree). Every node v in the rebuilt subtree has it's timer reset to Math.ceil(d*size(v)) where size(v) denotes the number of nodes in the subtree rooted at v.

The add(x) operation in a countdown tree works just like adding in a normal (unbalanced) Binary Search Tree. A new node u containing the value x is added as a leaf in the tree, but in addition u.timer is set to Math.ceil(d). Next, every node on the path from u to the root of the tree has its timer decremented and, if any of these nodes' timers drop to 0, then their subtree 'explodes'.

The remove(x) operation works just like in a normal (unbalanced) Binary Search Tree. We first find the node w that contains x. Now, it might not be easy to remove w because it has two children so we try to find a node u that is easy to delete. If w has no right child, then we set u=w. Otherwise, we pick u to be the leftmost (smallest value) node in w's right subtree. Next we swap u.x and w.x and splice u out of the tree.

Finally, we walk back up the path from (the now removed) u to the root and decrement the timer of every node along the way. If any of these nodes' timers drop to 0, then their subtree explodes.

You don't need to do anything to implement the find(x) operation, it's inherited from the BinarySearchTree class and works unmodified.

import java.util.Random; import java.util.SortedSet; import java.util.TreeSet;  public class CountdownTree extends BinarySearchTree, T> implements SSet { // countdown delay factor double d; public static class Node extends BSTNode,T> { int timer; // the height of the node } public CountdownTree(double d) { this.d = d; sampleNode = new Node(); c = new DefaultComparator(); } public boolean add(T x) { Node u = new Node(); u.timer = (int)Math.ceil(d); u.x = x; if (super.add(u)) { // add some code here return true; } return false; } public void splice(Node u) { Node w = u.parent; super.splice(u); // add some code here (we just removed u from the tree } protected void explode(Node u) { // Write this code to explode u // Make sure to update u.parent and/or r (the tree root) as appropriate } // Here is some test code you can use public static void main(String[] args) { Testum.sortedSetSanityTests(new SortedSSet(new CountdownTree(1)), 1000); Testum.sortedSetSanityTests(new SortedSSet(new CountdownTree(2.5)), 1000); Testum.sortedSetSanityTests(new SortedSSet(new CountdownTree(0.5)), 1000); java.util.List> ell = new java.util.ArrayList>(); ell.add(new java.util.TreeSet()); ell.add(new SortedSSet(new CountdownTree(1))); ell.add(new SortedSSet(new CountdownTree(2.5))); ell.add(new SortedSSet(new CountdownTree(0.5))); Testum.sortedSetSpeedTests(ell, 1000000); } } 

__________________________________________________________________

import java.util.Collection; import java.util.Comparator; import java.util.Iterator; public class BinarySearchTree, T> extends BinaryTree implements SSet { public Comparator c; /**  * The number of nodes (elements) currently in the tree  */  public int n; public Node newNode(T x) { Node u = super.newNode(); u.x = x; return u; } public BinarySearchTree(Node is, Comparator c) { super(is); this.c = c; } public BinarySearchTree(Node is) { this(is, new DefaultComparator()); } /**  * Create a new instance of this class  * @warning child must set sampleNode before anything that  * might make calls to newNode()  */  public BinarySearchTree() { this(null, new DefaultComparator()); } /**  * Search for a value in the tree  * @return the last node on the search path for x  */  public Node findLast(T x) { Node w = r, prev = nil; while (w != nil) { prev = w; int comp = c.compare(x, w.x); if (comp < 0) { w = w.left; } else if (comp > 0) { w = w.right; } else { return w; } } return prev; } /**  * Search for a value in the tree  * @return the last node on the search path for x  */  public Node findGENode(T x) { Node w = r, z = nil; while (w != nil) { int comp = c.compare(x, w.x); if (comp < 0) { z = w; w = w.left; } else if (comp > 0) { w = w.right; } else { return w; } } return z; } public T findEQ(T x) { Node u = r; while (u != nil) { int comp = c.compare(x, u.x); if (comp < 0) u = u.left; else if (comp > 0) u = u.right; else return u.x; } return null; } public T find(T x) { Node w = r, z = nil; while (w != nil) { int comp = c.compare(x, w.x); if (comp < 0) { z = w; w = w.left; } else if (comp > 0) { w = w.right; } else { return w.x; } } return z == nil ? null : z.x; } public T findGE(T u) { if (u == null) { // find the minimum value Node w = r; if (w == nil) return null; while (w.left != nil) w = w.left; return w.x; } Node w = findGENode(u); return w == nil ? null : w.x; } /**  * Search for a value in the tree  * @return the last node on the search path for x  */  public Node findLTNode(T x) { Node u = r, z = nil; while (u != nil) { int comp = c.compare(x, u.x); if (comp < 0) { u = u.left; } else if (comp > 0) { z = u; u = u.right; } else { return u; } } return z; } public T findLT(T x) { if (x == null) { // find the maximum value Node w = r; if (w == nil) return null; while (w.right != nil) w = w.right; return w.x; } Node w = findLTNode(x); return w == nil ? null : w.x; } /**  * Add the node u as a child of node p -- ASSUMES p has no child  * where u should be added  * @param p  * @param u  * @return true if the child was added, false otherwise  */  public boolean addChild(Node p, Node u) { if (p == nil) { r = u; // inserting into empty tree } else { int comp = c.compare(u.x, p.x); if (comp < 0) { p.left = u; } else if (comp > 0) { p.right = u; } else { return false; // u.x is already in the tree } u.parent = p; } n++; return true; } /**  * Add a new value  * @param x  * @return  */  public boolean add(T x) { Node p = findLast(x); return addChild(p, newNode(x)); } /**  * Add a new value  * @param x  * @return  */  public boolean add(Node u) { Node p = findLast(u.x); return addChild(p, u); } /**  * Remove the node u --- ASSUMING u has at most one child  * @param u  */  public void splice(Node u) { Node s, p; if (u.left != nil) { s = u.left; } else { s = u.right; } if (u == r) { r = s; p = nil; } else { p = u.parent; if (p.left == u) { p.left = s; } else { p.right = s; } } if (s != nil) { s.parent = p; } n--; } /**  * Remove the node u from the binary search tree  * @param u  */  public void remove(Node u) { if (u.left == nil || u.right == nil) { splice(u); } else { Node w = u.right; while (w.left != nil) w = w.left; u.x = w.x; splice(w); } } /**  * Do a left rotation at u  * @param u  */  public void rotateLeft(Node u) { Node w = u.right; w.parent = u.parent; if (w.parent != nil) { if (w.parent.left == u) { w.parent.left = w; } else { w.parent.right = w; } } u.right = w.left; if (u.right != nil) { u.right.parent = u; } u.parent = w; w.left = u; if (u == r) { r = w; r.parent = nil; } } /**  * Do a right rotation at u  * @param u  */  public void rotateRight(Node u) { Node w = u.left; w.parent = u.parent; if (w.parent != nil) { if (w.parent.left == u) { w.parent.left = w; } else { w.parent.right = w; } } u.left = w.right; if (u.left != nil) { u.left.parent = u; } u.parent = w; w.right = u; if (u == r) { r = w; r.parent = nil; } } /**  * Remove a node  * @param x  * @return  */  public boolean remove(T x) { Node u = findLast(x); if (u != nil && c.compare(x,u.x) == 0) { remove(u); return true; } return false; } public String toString() { String s = "["; Iterator it = iterator(); while (it.hasNext()) { s += it.next().toString() + (it.hasNext() ? "," : ""); } s += "]"; return s; } @SuppressWarnings({"unchecked"}) public boolean contains(Object x) { Node u = findLast((T)x); return u != nil && c.compare(u.x, (T)x) == 0; } public boolean containsAll(Collection c) { for (Object x : c) if (!contains(x)) return false; return true; } public Iterator iterator(Node u) { class BTI implements Iterator { public Node w, prev; public BTI(Node iw) { w = iw; } public boolean hasNext() { return w != nil; } public T next() { T x = w.x; prev = w; w = nextNode(w); return x; } public void remove() { // FIXME: This is a bug. remove() methods have to be changed BinarySearchTree.this.remove(prev); } } return new BTI(u); } public Iterator iterator() { return iterator(firstNode()); } public Iterator iterator(T x) { return iterator(findGENode(x)); } public int size() { return n; } public boolean isEmpty() { return n == 0; } public void clear() { super.clear(); n = 0; } public Comparator comparator() { return c; } }

________________________________________________________

public class BSTNode,T> extends BinaryTreeNode { /**  * The key stored at this node  */  T x; } 

____________________________________________

import java.util.LinkedList; import java.util.Queue; import java.util.Random; public class BinaryTree> 

 { /**  * Used to make a mini-factory  */  public Node sampleNode; /**  * The root of this tree  */  public Node r; /**  * This tree's null node  */  public Node nil; /**  * Create a new instance of this class  * @param isampleNode  */  public BinaryTree(Node nil) { sampleNode = nil; this.nil = null; } /**  * Create a new instance of this class  * @warning child must set sampleNode before anything that  * might make calls to newNode()  */  public BinaryTree() { } /**  * Allocate a new node for use in this tree  * @return  */  @SuppressWarnings({"unchecked"}) public Node newNode() { try { Node u = (Node)sampleNode.getClass().newInstance(); u.parent = u.left = u.right = nil; return u; } catch (Exception e) { return null; } } public int depth(Node u) { int d = 0; while (u != r) { u = u.parent; d++; } return d; } /**  * Compute the size (number of nodes) of this tree  * @return the number of nodes in this tree  */  public int size() { return size(r); } /**  * @return the size of the subtree rooted at u  */  public int size(Node u) { if (u == nil) return 0; return 1 + size(u.left) + size(u.right); } public int height() { return height(r); } /**  * @return the size of the subtree rooted at u  */  public int height(Node u) { if (u == nil) return -1; return 1 + Math.max(height(u.left), height(u.right)); } /**  * @return  */  public boolean isEmpty() { return r == nil; } /**  * Make this tree into the empty tree  */  public void clear() { r = nil; } public void traverse(Node u) { if (u == nil) return; traverse(u.left); traverse(u.right); } public void traverse2() { Node u = r, prev = nil, next; while (u != nil) { if (prev == u.parent) { if (u.left != nil) next = u.left; else if (u.right != nil) next = u.right; else next = u.parent; } else if (prev == u.left) { if (u.right != nil) next = u.right; else next = u.parent; } else { next = u.parent; } prev = u; u = next; } } public int size2() { Node u = r, prev = nil, next; int n = 0; while (u != nil) { if (prev == u.parent) { n++; if (u.left != nil) next = u.left; else if (u.right != nil) next = u.right; else next = u.parent; } else if (prev == u.left) { if (u.right != nil) next = u.right; else next = u.parent; } else { next = u.parent; } prev = u; u = next; } return n; } public void bfTraverse() { Queue q = new LinkedList(); q.add(r); while (!q.isEmpty()) { Node u = q.remove(); if (u.left != nil) q.add(u.left); if (u.right != nil) q.add(u.right); } } /**  * Find the first node in an in-order traversal  * @return  */  public Node firstNode() { Node w = r; if (w == nil) return nil; while (w.left != nil) w = w.left; return w; } /**  * Find the node that follows u in an in-order traversal  * @param w  * @return  */  public Node nextNode(Node w) { if (w.right != nil) { w = w.right; while (w.left != nil) w = w.left; } else { while (w.parent != nil && w.parent.left != w) w = w.parent; w = w.parent; } return w; } public static > void completeBinaryTree(BinaryTree t, int n) { Queue q = new LinkedList(); t.clear(); if (n == 0) return; t.r = t.newNode(); q.add(t.r); while (--n > 0) { Node u = q.remove(); u.left = t.newNode(); u.left.parent = u; q.add(u.left); if (--n > 0) { u.right = t.newNode(); u.right.parent = u; q.add(u.right); } } } /**  * Create a new full binary tree whose expected number of nodes is n  * @param <Node> * @param t  * @param n  */  public static > void galtonWatsonFullTree(BinaryTree t, int n) { Random r = new Random(); Queue q = new LinkedList(); t.clear(); t.r = t.newNode(); q.add(t.r); double p = ((double)0.5 - ((double)1)/(n+n)); while (!q.isEmpty()) { Node u = q.remove(); if (r.nextDouble() < p) { u.left = t.newNode(); u.left.parent = u; q.add(u.left); u.right = t.newNode(); u.right.parent = u; q.add(u.right); } } } static > void galtonWatsonTree(BinaryTree t, int n) { Random r = new Random(); Queue q = new LinkedList(); t.clear(); t.r = t.newNode(); q.add(t.r); double p = ((double)0.5 - ((double)1)/(n+n)); while (!q.isEmpty()) { Node u = q.remove(); if (r.nextDouble() < p) { u.left = t.newNode(); u.left.parent = u; q.add(u.left); } if (r.nextDouble() < p) { u.right = t.newNode(); u.right.parent = u; q.add(u.right); } } } } 

________________________________________________________________________

import java.util.Comparator; import java.util.Iterator; /**  * The SSet interface is a simple interface that allows a class to implement  * all the functionality of the (more complicated) SortedSet interface. Any  * class that implements SSet can be wrapped in a SortedSSet to obtain an  * implementation of SortedSet  *  * @author morin  *  * @param <T> * @see SortedSSet<T> */ public interface SSet extends Iterable { /**  * @return the comparator used by this SSet  */  public Comparator comparator(); /**  * @return the number of elements in this SSet  */  public int size(); /**  * Find the smallest element in the SSet that is greater than or equal to x.  * If x is null, return the smallest element in the SSet  *  * @param x  * @return the smallest element in the SSet that is greater than or equal to  * x. If x is null then the smallest element in the SSet  */  public T findGE(T x); /**  * Find the largest element in the SSet that is greater than to x. If x is  * null, return the largest element in the SSet  *  * @param x  * @return the largest element in the SSet that is less than x. If x is null  * then the smallest element in the SSet  */  public T findLT(T x); /**  * Add the element x to the SSet  *  * @param x  * @return true if the element was added or false if x was already in the  * set  */  public boolean add(T x); /**  * Remove the element x from the SSet  *  * @param x  * @return true if x was removed and false if x was not removed (because x  * was not present)  */  public boolean remove(T x); /**  * Clear the SSet, removing all elements from the set  */  public void clear(); /**  * Return an iterator that iterates over the elements in sorted order,  * starting at the first element that is greater than or equal to x.  */  public Iterator iterator(T x); } 

__________________________________________________________________________

import java.util.Comparator; class DefaultComparator implements Comparator { @SuppressWarnings("unchecked") public int compare(T a, T b) { return ((Comparable)a).compareTo(b); } }

__________________________________________________________________

import java.util.AbstractSet; import java.util.ArrayList; import java.util.Collection; import java.util.Comparator; import java.util.Iterator; import java.util.SortedSet; /**  * This class is a wrapper that allows any class that implements SSet to  * allow it to also implement SortedSet.  *  * @author morin  *  * @param <T> */ public class SortedSSet extends AbstractSet implements SortedSet { protected SSet s; public SortedSSet(SSet s) { this.s = s; } public Comparator comparator() { return s.comparator(); } public T first() { return s.findGE(null); } public T last() { return s.findLT(null); } public SortedSet headSet(T b) { return new RangeSSet(s, null, b); } public SortedSet subSet(T a, T b) { return new RangeSSet(s, a, b); } public SortedSet tailSet(T a) { return new RangeSSet(s, a, null); } public boolean add(T x) { return s.add(x); } public void clear() { s.clear(); } @SuppressWarnings("unchecked") public boolean contains(Object o) { T y = s.findGE((T) o); return y != null && y.equals(o); } public Iterator iterator() { return s.iterator(); } @SuppressWarnings("unchecked") public boolean remove(Object x) { return s.remove((T) x); } public int size() { return s.size(); } public boolean isEmpty() { return !s.iterator().hasNext(); } } 

________________________________________________

import java.util.ArrayList; import java.util.Collection; import java.util.Iterator; import java.util.LinkedList; import java.util.List; import java.util.Random; import java.util.Set; import java.util.SortedSet; import java.util.TreeSet; /** * A utility class with some static methods for testing List implementations * @author morin */ public class Testum { protected static void myassert(boolean b) throws AssertionError { if (!b) { throw new AssertionError(); } } protected static String s(Object c) { return c.getClass().getName(); } public static void sortedSetSanityTests(SortedSet ss, int n) { SortedSet ts = new TreeSet(); ss.clear(); Random r = new Random(); for (int i = 0; i < n; i++) { Integer x = r.nextInt(2*n); if (ts.add(x) != ss.add(x)) throw new RuntimeException("add(x) returned wrong value"); if (!compareSortedSets(ts,ss)) throw new RuntimeException("sorted sets differ!"); } for (int i = 0; i < n; i++) { Integer x = r.nextInt(2*n); if (ts.remove(x) != ss.remove(x)) throw new RuntimeException("remove(x) returned wrong value"); if (!compareSortedSets(ts,ss)) throw new RuntimeException("sorted sets differ!"); } ss.clear(); ts.clear(); compareSortedSets(ts,ss); } public static void sortedSetSpeedTests(Collection> css, int n) { long start, stop; for (SortedSet ss : css) { ss.clear(); myassert(ss.size() == 0); } for (SortedSet ss : css) { System.out.print("random insertions (" + s(ss) + ")..."); start = System.nanoTime(); Random r = new Random(); for (int i = 0; i < n; i++) ss.add(r.nextInt(2*n)); stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); myassert(ss.size() >= n/2); } System.out.println(); for (SortedSet ss : css) { System.out.print("random contains (" + s(ss) + ")..."); start = System.nanoTime(); Random r = new Random(); for (int i = 0; i < 2*n; i++) ss.contains(r.nextInt(2*n)); stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("random removals (" + s(ss) + ")..."); start = System.nanoTime(); Random r = new Random(); for (int i = 0; i < 2*n; i++) ss.remove(r.nextInt(2*n)); stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("random headSets (" + s(ss) + ")..."); start = System.nanoTime(); Random r = new Random(); for (int i = 0; i < n; i++) { ss.headSet(r.nextInt(2*n)); Iterator it = ss.iterator(); if (it.hasNext()) it.next(); } stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("iteration (" + s(ss) + ")..."); start = System.nanoTime(); for (Integer i : ss) { i = i + 1; } stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("clear (" + s(ss) + ")..."); start = System.nanoTime(); ss.clear(); stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("sequential insertions (" + s(ss) + ")..."); start = System.nanoTime(); for (int i = 0; i < n; i++) { myassert(ss.size() == i); ss.add(i*2); } stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); myassert(ss.size() == n); } System.out.println(); for (SortedSet ss : css) { System.out.print("sequential contains (" + s(ss) + ")..."); start = System.nanoTime(); for (int i = 0; i < 2*n; i++) ss.contains(i); stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("sequential headSets (" + s(ss) + ")..."); start = System.nanoTime(); for (int i = 0; i < 2*n; i++) ss.headSet(i); stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); for (SortedSet ss : css) { System.out.print("iteration over subSets (" + s(ss) + ")..."); start = System.nanoTime(); for (Integer i : ss.subSet(n/2, 3*n/4)) { i = i + 1; } stop = System.nanoTime(); System.out.println(" " + (1e-9 * (stop - start)) + " seconds"); } System.out.println(); } protected static boolean compareSortedSets(Collection a, Collection b) { if (a.size() != b.size()) return false; for (T x : a) { if (!b.contains(x)) return false; } for (T x : b) { if (!a.contains(x)) return false; } Iterator ita = a.iterator(); Iterator itb = b.iterator(); while (ita.hasNext()) { if (!ita.next().equals(itb.next())) return false; } return true; } }