- // Debugging ///////////////////////////////////////////////////////////////////////////
-
- public void check() { check(false); }
- public void check(boolean expensive) {
- if(expensive) System.err.println("--> Running expensive balanced tree checks");
- try {
- if(expensive)
- for(int i=0;i<NUM_SLOTS;i++)
- if(left[i] < 0 || right[i] < 0) throw new Error("someone inserted a negative number");
- if(parent[root] != 0) throw new Error("parent of the root isn't 0");
- if(left[0] != 0 || right[0] != 0 || size[0] != 0 || parent[0] != 0)
- throw new Error("someone messed with [0]");
-
- int c = 0;
- int n = leftmost(root);
- while(n != 0) { c++; n = next(n); }
- if(c != size[root]) throw new Error("size[] mismatch");
-
- if(root != 0) check(root);
- } catch(Error e) {
- printTree();
- throw e;
- }
- }
-
- private void check(int node) {
- //if(next(node) != next2(node)) throw new Error("next(" + node + ") != next2(" + node + ")");
- //if(prev(node) != prev2(node)) throw new Error("prev(" + node + ") != prev2(" + node + ")");
-
- if(left[node] > 0) {
- if(parent[left[node]] != node) throw new Error("parent node mismatch on left child of " + node);
- check(left[node]);
- }
- if(right[node] > 0) {
- if(parent[right[node]] != node) throw new Error("parent node mismatch on right child of " + node);
- check(right[node]);
- }
- }
-