Scapegoat tree using less memory 0.99b

/* An implementation of scapegoat tree. It has tree methods add, remove,
 * findLE, findEQ, findGE, @@iterator, size, and clear. Ported from Open
 * Data Structures by Pat Morin. Includes a short demonstration of those
 * methods showing traversals of modified tree.
 * The time complexity of #buildTree() in this Beta version improves to
 * O(n*logn) compared to the O(n^2) of previous Beta versions. (Morin
 * Exercise 8..7)
 */

/** A node. */
class Vertex {
  /** constructor() credit: Morin 6.1. */
  constructor() {
    this.value;  // any
    this.left;   // Vertex ref
    this.right;  // Vertex ref
    this.parent; // Vertex ref
    this.numV;   // number of vertices in this subtree
    this.bSeen;  // boolean
  }
}

/** A sorted set. */
class ScapegoatTree {
  #nil; #root; #compare; #oeNV;
  /** constructor() credit: Morin BinaryTree.java, BinarySearchTree.java, ScapegoatTree.java.
   * @param {function} comparator function taking (any, any) and returning -1, 0, or 1
   */
  constructor(comparator) {
    this.#nil = new Vertex();  // vertex used as null
    this.#nil.numV = 0;
    this.#root = this.#nil;  // root vertex
    this.#compare = comparator;
    this.#oeNV = 0;  // an overestimate of this.#root.numV
  }

  /** #newVertex() credit: Morin BinaryTree.java, BinarySearchTree.java.
   * @param {any} value value used to order the tree
   * @returns {Vertex} a new vertex
   */
  #newVertex(value) {
    var vertex = new Vertex();
    vertex.value = value;
    vertex.left = this.#nil;
    vertex.right = this.#nil;
    vertex.parent = this.#nil;
    vertex.bSeen = false;
    return vertex;
  }

  /** #firstVertex() credit: Morin BinaryTree.java.
   * @returns {Vertex} first vertex reported in in-order traversal
   */
  #firstVertex() {
    var vertex = this.#root;
    if (vertex == this.#nil) { return this.#nil; }
    while (vertex.left != this.#nil) {
      vertex = vertex.left;
    }
    return vertex;
  }

  /** #nextVertex() credit: Morin BinaryTree.java.
   * @param {Vertex} vertex a vertex
   * @returns {Vertex} vertex following the given in in-order traversal
   */
  #nextVertex(vertex) {
    if (vertex.right != this.#nil) {
      vertex = vertex.right;
      while (vertex.left != this.#nil) {
        vertex = vertex.left;
      }
    } else {
      while (vertex.parent != this.#nil && vertex.parent.left != vertex) {
        vertex = vertex.parent;
      }
      vertex = vertex.parent;
    }
    return vertex;
  }

  /** @@iterator() Iterator of in-order values. credit: Morin BinarySearchTree.java. */
  *[Symbol.iterator]() {
    var cur = this.#firstVertex();
    while(cur != this.#nil) {
      var value = cur.value;
      cur = this.#nextVertex(cur);
      yield value;
    }
  }

  /** toString() credit: Morin BinarySearchTree.java.
   * @returns {string} in-order values formatted as array
   */
  toString() {
    return JSON.stringify([...this]);
  }

  /** #dnOfI() A recursive helper that calculates the depth of and size of
   *  a vertex in a perfectly balanced tree.
   * @param {Array} dn array with [depth, numV] of vertex
   * @param {number} vxSz size of tree containing vertex
   * @param {number} i the index of vertex such that 0 <= i < vxSz
   * @returns {Array} array with [depth, numV] of vertex
   */
  #dnOfI(dn, vxSz, i) {
    var hfVS = Math.floor(vxSz / 2);
    if (i < hfVS) {   // left
      if (hfVS > 0) {
        dn[0]++;
        dn = this.#dnOfI(dn, hfVS, i);
      }
    } else if (i == hfVS) { // middle
      dn[1] = vxSz;
    } else {    // right
      if (vxSz - hfVS - 1 > 0) {
        dn[0]++;
        dn = this.#dnOfI(dn, vxSz - hfVS - 1, i - hfVS - 1);
      }
    }
    return dn;
  }

  /** #buildTree() Builds a perfectly balanced subtree from an ordered
   *  linked list of vertices.
   * @param {Vertex} head head of linked list
   * @param {number} vxSz vertex size
   * @param {Vertex} dummy dummy vertex at tail of linked list
   * @returns {Vertex} the root of the newly created subtree
   */
  #buildTree(head, vxSz, dummy) {
    var cur = head, i = 0, dCur;
    var stack = new Array();  // of [vertex, depth]
    if (head != dummy) {
      // get depth and numV of head vertex
      dCur = this.#dnOfI([0, 0], vxSz, i);
      cur.numV = dCur[1];
    }
    while (cur != dummy) {
      var next = cur.right;
      if (next != dummy) {
        // get depth and numV of next vertex
        var dNext = this.#dnOfI([0, 0], vxSz, ++i);
        next.numV = dNext[1];
        if (dNext[0] < dCur[0]) {
          if (dCur[0] - dNext[0] == 1) {
            // put current below next
            next.left = cur;
            cur.parent = next;
          } else if (dCur[1] == 2 && stack.length > 0) {
            var p = stack[stack.length - 1];
            p[0].right = cur;
            cur.parent = p[0];
          }
          cur.right = this.#nil;
          if (dCur[1] == 1) { cur.left = this.#nil; }
        } else {
          if (dNext[0] - dCur[0] == 1) {
            // put current above next
            next.parent = cur;
          }
          var nPop = 0, bLoop = true;
          // visit at most two [vertex, depth] pairs on stack
          for (var j = stack.length - 1; j >= 0 && bLoop; j--) {
            if (stack[j][1] > dCur[0]) {
              if (stack[j][1] - dCur[0] == 1) {
                cur.left = stack[j][0];
                stack[j][0].parent = cur;
              }
              nPop++;
            } else {
              stack[j][0].right = cur;
              cur.parent = stack[j][0];
              bLoop = false;
            }
          }
          for (var j = 0; j < nPop; j++) { stack.pop(); }
          stack.push([cur, dCur[0]]);
        }
        dCur = dNext;
      } else {  // last vertex
        if (dCur[1] == 2 && stack.length > 0) {
          var p = stack[stack.length - 1];
          p[0].right = cur;
          cur.parent = p[0];
        }
        cur.right = this.#nil;
        if (dCur[1] == 1) { cur.left = this.#nil; }
      }
      cur = next;
    }
    return stack.shift()[0];
  }

  /** #flatten() A recursive helper that converts the subtree rooted at given
   *  vertex into a linked list of vertices. credit: Morin ScapegoatTree2.java.
   * @param {Vertex} vertex root of subtree
   * @param {Vertex} tail tail of linked list
   * @returns {Vertex} head of linked list
   */
  #flatten(vertex, tail) {
    if (vertex == this.#nil) { return tail; }
    vertex.right = this.#flatten(vertex.right, tail);
    return this.#flatten(vertex.left, vertex);
  }

  /** #rebuildTree() Builds a perfectly balanced subtree out of a scapegoat.
   *  credit: Morin ScapegoatTree2.java.
   * @param {Vertex} scapegoat root of subtree
   * @returns {Vertex} the root of the newly created subtree
   */
  #rebuildTree(scapegoat) {
    var dummy = this.#newVertex(undefined);
    var head = this.#flatten(scapegoat, dummy);
    return this.#buildTree(head, scapegoat.numV, dummy);
  }

  /** #rebuild() credit: Morin ScapegoatTree2.java.
   * @param {Vertex} vertex root of subtree
   */
  #rebuild(vertex) {
    var p = vertex.parent;
    if (p != this.#nil) {
      if (p.left == vertex) {
        vertex = this.#rebuildTree(vertex);
        p.left = vertex;
      } else {
        vertex = this.#rebuildTree(vertex);
        p.right = vertex;
      }
      vertex.parent = p;
    } else {
      this.#root = this.#rebuildTree(vertex);
      this.#root.parent = p;
    }
  }

  /** #addWithDepth() Do a normal BinarySearchTree insertion, but return the
   *  depth of the newly inserted vertex. credit: Morin ScapegoatTree.java.
   * @param {Vertex} vertex vertex to add
   * @returns {number} the depth of the newly inserted vertex, or -1 if
   *              the vertex was not inserted
   */
  #addWithDepth(vertex) {
    var cur = this.#root;
    if (cur == this.#nil) {
      this.#root = vertex;
      this.#oeNV++;
      return 0;
    }
    var done = false;
    var depth = 0;
    do {
      var res = this.#compare(vertex.value, cur.value);
      if (res < 0) {
        if (cur.left == this.#nil) {
          cur.left = vertex;
          vertex.parent = cur;
          done = true;
        }
        cur = cur.left;
      } else if (res > 0) {
        if (cur.right == this.#nil) {
          cur.right = vertex;
          vertex.parent = cur;
          done = true;
        }
        cur = cur.right;
      } else {
        return -1;
      }
      depth++;
    } while (!done);
    // traverse up the tree, incrementing num. vertices
    while (cur != this.#root) {
      cur = cur.parent;
      cur.numV++;
    }
    this.#oeNV++;
    return depth;
  }

  /** log32() Compute the ceiling of log_{3 / 2}(oeNV). credit: Morin ScapegoatTree.java.
   * @param {number} oeNV overestimate of num. vertices
   * @returns {number} the ceiling of log_{3 / 2}(oeNV)
   */
  static log32(oeNV) {
    const log23 = 2.4663034623764317;
    return Math.ceil(log23 * Math.log(oeNV));
  }

  /** add() credit: Morin 8.1.
   * @param {any} value value to add
   * @returns {boolean} success?
   */
  add(value) {
    var vertex = this.#newVertex(value);
    vertex.numV = 1;
    var depth = this.#addWithDepth(vertex); // get depth of inserted vertex
    if (depth > ScapegoatTree.log32(this.#oeNV)) {  // depth exceeded, find scapegoat
      var cur = vertex.parent;
      while (3 * cur.numV <= 2 * cur.parent.numV) {
        cur = cur.parent;
      }
      this.#rebuild(cur.parent);
    }
    return depth >= 0;
  }

  /** #splice() credit: Morin 6.2.3.
   * @param {Vertex} vertex vertex to splice
   */
  #splice(vertex) {
    var cur, prev;
    if (vertex.left != this.#nil) {
      cur = vertex.left;
    } else {
      cur = vertex.right;
    }
    if (vertex == this.#root) {
      if (cur == vertex.left && vertex.right != this.#nil) {
        cur.numV += vertex.right.numV;
      }
      this.#root = cur;
      prev = this.#nil;
    } else {
      prev = vertex.parent;
      if (prev.left == vertex) {
        prev.left = cur;
      } else {
        prev.right = cur;
      }
      // traverse up the tree, decrementing num. vertices
      var p = vertex.parent;
      do {
        p.numV--;
        p = p.parent;
      } while (p != this.#nil);
    }
    if (cur != this.#nil) {
      cur.parent = prev;
    }
  }

  /** #rmVert() Remove the given vertex from the binary search tree.
   *  credit: Morin 6.2.3.
   * @param {Vertex} vertex vertex to remove
   */
  #rmVert(vertex) {
    if (vertex.left == this.#nil || vertex.right == this.#nil) {
      this.#splice(vertex);
    } else {
      var cur = vertex.right;
      while (cur.left != this.#nil) { cur = cur.left; }
      vertex.value = cur.value;
      this.#splice(cur);
    }
  }

  /** #findLast() credit: Morin 6.2.2.
   * @param {any} value value for comparison
   * @returns {Vertex} last vertex found on path for value
   */
  #findLast(value) {
    var cur = this.#root, prev = this.#nil;
    while (cur != this.#nil) {
      prev = cur;
      var res = this.#compare(value, cur.value);
      if (res < 0) { cur = cur.left; }
      else if (res > 0) { cur = cur.right; }
      else { return cur; }
    }
    return prev;
  }

  /** rmVal() credit: Morin BinarySearchTree.java.
   * @param {any} value value to remove
   * @returns {boolean} success?
   */
  #rmVal(value) {
    var vertex = this.#findLast(value);
    if (vertex != this.#nil && this.#compare(value, vertex.value) == 0) {
      this.#rmVert(vertex);
      return true;
    }
    return false;
  }

  /** remove() credit: Morin 8.1.
   * @param {any} value value to remove
   * @returns {boolean} success?
   */
  remove(value) {
    if (this.#rmVal(value)) {
      if (2 * this.#root.numV < this.#oeNV) {
        this.#rebuild(this.#root);
        this.#oeNV = this.#root.numV;
      }
      return true;
    }
    return false;
  }

  /** findEQ() Find an equal value. credit: Morin 6.2.1.
   * @param {any} value value to find
   * @returns {any} value if found, undefined if not found
   */
  findEQ(value) {
    var cur = this.#root;
    while (cur != this.#nil) {
      var res = this.#compare(value, cur.value);
      if (res < 0) { cur = cur.left; }
      else if (res > 0) { cur = cur.right; }
      else { return cur.value; }
    }
    return undefined;
  }

  /** #findGEVertex() credit: Morin BinarySearchTree.java.
   * @param {any} value value to find
   * @returns {Vertex} last vertex found on path for value
   */
  #findGEVertex(value) {
    var cur = this.#root, last = this.#nil;
    while (cur != this.#nil) {
      var res = this.#compare(value, cur.value);
      if (res < 0) {
        last = cur;
        cur = cur.left;
      } else if (res > 0) {
        cur = cur.right;
      } else {
        return cur;
      }
    }
    return last;
  }

  /** findGE() Find smallest value in tree greater than or equal to given value, or undefined
   * if no such value. Or, if given value is undefined then the smallest value in tree.
   * credit: Morin BinarySearchTree.java, SSet.java.
   * @param {any} value value to find
   * @returns {any} smallest value in tree greater than or equal to given value, or undefined if no
   *               such value. Or, if given value is undefined then the smallest value in tree.
   */
  findGE(value) {
    if (value == undefined) {  // find the minimum value
      var cur = this.#root;
      if (cur == this.#nil) { return undefined; }
      while (cur.left != this.#nil) {
        cur = cur.left;
      }
      return cur.value;
    }
    var cur = this.#findGEVertex(value);
    if (cur == this.#nil) { return undefined; }
    return cur.value;
  }

  /** #findLEVertex() credit: Morin BinarySearchTree.java.
   * @param {any} value value to find
   * @returns {Vertex} last vertex found on path for value
   */
  #findLEVertex(value) {
    var cur = this.#root, last = this.#nil;
    while (cur != this.#nil) {
      var res = this.#compare(value, cur.value);
      if (res < 0) {
        cur = cur.left;
      } else if (res > 0) {
        last = cur;
        cur = cur.right;
      } else {
        return cur;
      }
    }
    return last;
  }

  /** findLE() Find largest value in tree less than or equal to given value, or undefined
   * if no such value. Or, if given value is undefined then the largest value in tree.
   * credit: Morin BinarySearchTree.java findLT [sic].
   * @param {any} value value to find
   * @returns {any} largest value in tree less than or equal to given value, or undefined if no
   *               such value. Or, if given value is undefined then the largest value in tree.
   */
  findLE(value) {
    if (value == undefined) {  // find the maximum value
      var cur = this.#root;
      if (cur == this.#nil) { return undefined; }
      while (cur.right != this.#nil) {
        cur = cur.right;
      }
      return cur.value;
    }
    var cur = this.#findLEVertex(value);
    if (cur == this.#nil) { return undefined; }
    return cur.value;
  }

  /** #depth() Get vertex depth. credit: Morin 6.1.
   * @param {Vertex} vertex vertex to calculate depth for
   * @returns {number} depth of given vertex
   */
  #depth(vertex) {
    var count = 0;
    while (vertex != this.#root) {
      vertex = vertex.parent;
      count++;
    }
    return count;
  }

  /** #sizeOfV() Get vertex size. credit: Morin 6.1.1.
   * @param {Vertex} vertex vertex to calculate size for
   * @returns {number} size of given vertex
   */
  #sizeOfV(vertex) {
    if (vertex == this.#nil) { return 0; }
    return 1 + this.#sizeOfV(vertex.left) + this.#sizeOfV(vertex.right);
  }

  /** size3() Get tree size.
   * @returns {number} size of tree
   */
  size3() {
    return this.#sizeOfV(this.#root);
  }

  verify() {
    if (this.size3() != this.#root.numV) {
      throw new Error("verify: size is incorrect");
    } else if (2 * this.#root.numV < this.#oeNV) {
      throw new Error("verify: overestimate is too high");
    } else if (this.height() > ScapegoatTree.log32(this.#oeNV)) {
      throw new Error("verify: tree is too tall");
    }
  }

  /** size() Get tree size. credit: Morin BinarySearchTree.java.
   * @returns {number} size of tree
   */
  size() {
    return this.#root.numV;
  }

  /** clear() credit: Morin BinaryTree.java, BinarySearchTree.java. */
  clear() {
    this.#root = this.#nil;
  }

  /** #heightOfV() Get vertex height. credit: Morin 6.1.1.
   * @param {Vertex} vertex vertex to calculate height for
   * @returns {number} height of given vertex, or -1 if nil vertex
   */
  #heightOfV(vertex) {
    if (vertex == this.#nil) { return -1; }
    return 1 + Math.max(this.#heightOfV(vertex.left), this.#heightOfV(vertex.right));
  }

  /** height() Get tree height.
   * @returns {number} height of root, or -1 if nil root
   */
  height() {
    return this.#heightOfV(this.#root);
  }

  /** #formatVertices()
   * @param {boolean} flag if true, append additional vertex info
   * @param {Vertex[]} vertices vertices in this tree
   * @returns {string} vertices formatted as tree
   */
  #formatVertices(flag, vertices) {
    var retVertices = "";
    for (var i = 0; i < vertices.length; i++) {
      retVertices += '\n' + " ".repeat(this.#depth(vertices[i]) + 1) + vertices[i].value;
      if (flag) {
        var height = this.#heightOfV(vertices[i]);
        retVertices += "  height=" + height + "  size=" + vertices[i].numV;
        if (vertices[i].parent != this.#nil) {
          retVertices += "  parent=" + vertices[i].parent.value;
        }
      }
    }
    return retVertices;
  }

  /** #traverseInner() Inner depth-first traverse. credit: Morin 6.1.2.
   * @param {Vertex} vertex vertex to traverse
   * @param {Vertex[]} dfVertices discovered vertices
   */
  #traverseInner(vertex, dfVertices) {
    if (vertex == this.#nil) { return; }
    vertex.bSeen = true;
    if (!vertex.left.bSeen) {
      vertex.left.bSeen = true;
      this.#traverseInner(vertex.left, dfVertices);
    }
    if (!vertex.right.bSeen) {
      vertex.right.bSeen = true;
      this.#traverseInner(vertex.right, dfVertices);
    }
    dfVertices.unshift(vertex);
  }

  /** traverse() Depth-first traverse.
   * @returns {string} vertices formatted as tree
   */
  traverse() {
    var dfVertices = [];
    this.#traverseInner(this.#root, dfVertices);
    this.bfTraverse(false);
    return "depth-first traverse" + this.#formatVertices(false, dfVertices);
  }

  /** traverse2() Depth-first traverse. credit: Morin 6.1.2.
   * @returns {string} vertices formatted as tree
   */
  traverse2() {
    var dfVertices = [];
    var cur = this.#root, prev = this.#nil, next;
    while (cur != this.#nil) {
      if (prev == cur.parent) {
        if (cur.left != this.#nil) { next = cur.left; }
        else if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else if (prev == cur.left) {
        if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else {
        next = cur.parent;
      }
      prev = cur;
      if (!cur.bSeen) {
        dfVertices.push(cur);
        cur.bSeen = true;
      }
      cur = next;
    }
    this.bfTraverse(false);
    return "depth-first traverse #2" + this.#formatVertices(false, dfVertices);
  }

  /** bfTraverse() Breadth-first traverse. credit: Morin 6.1.2.
   * @param {boolean} flag true: set bSeen, false: unset bSeen
   * @returns {string} vertices formatted as tree
   */
  bfTraverse(flag) {
    var bfVertices = [];
    var queue = [];  // queue of Vertex's
    if (this.#root != this.#nil) {
      queue.push(this.#root);
      this.#root.bSeen = flag;
    }
    while (queue.length > 0) {
      var vertex = queue.shift();
      if (flag) { bfVertices.push(vertex); }
      if (vertex.left != this.#nil) {
        if (flag) {
          if (!vertex.left.bSeen) {
            queue.push(vertex.left);
            vertex.left.bSeen = flag;
          }
        } else {
          queue.push(vertex.left);
          vertex.left.bSeen = flag;
        }
      }
      if (vertex.right != this.#nil) {
        if (flag) {
          if (!vertex.right.bSeen) {
            queue.push(vertex.right);
            vertex.right.bSeen = flag;
          }
        } else {
          queue.push(vertex.right);
          vertex.right.bSeen = flag;
        }
      }
    }
    if (flag) { this.bfTraverse(false); }
    return "breadth-first traverse" + this.#formatVertices(true, bfVertices);
  }

  /** size2() Get tree size. credit: Morin 6.1.2.
   * @returns {number} size of tree
   */
  size2() {
    var cur = this.#root, prev = this.#nil, next;
    var count = 0;
    while (cur != this.#nil) {
      if (prev == cur.parent) {
        count++;
        if (cur.left != this.#nil) { next = cur.left; }
        else if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else if (prev == cur.left) {
        if (cur.right != this.#nil) { next = cur.right; }
        else { next = cur.parent; }
      } else {
        next = cur.parent;
      }
      prev = cur;
      cur = next;
    }
    return count;
  }
}

/** compare() Compare values. This will work for string and number types.
 * @param {any} a a value
 * @param {any} b another value
 * @returns {number} -1 if a < b, 0 if a == b, 1 if a > b
 */
function compare(a, b) {
  if (a < b) { return -1; }
  else if (a > b) { return 1; }
  return 0;
}

/** assertSets() Assert that sizes and values of tree and set are equal.
 * @param {ScapegoatTree} aTree a tree
 * @param {Set} aSet a set
 */
function assertSets(aTree, aSet) {
  if (aTree.size() == aSet.size) {
    var i = 0, setVals = Array.from(aSet).sort(compare);
    for (const tVal of aTree) {
      if (compare(tVal, setVals[i]) != 0) {
        throw new Error("assert: value mismatch");
      }
      i++;
    }
  } else {
    throw new Error("assert: size mismatch");
  }
}


var natoValues = ["alpha", "bravo", "charlie", "delta", "echo", "foxtrot", "golf", "hotel",
                  "india", "juliet", "kilo", "lima", "mike", "november", "oscar", "papa",
                  "quebec", "romeo", "sierra", "tango", "uniform"];
var wuValues = ["adams", "boston", "chicago", "denver", "easy", "frank", "george", "henry",
                "ida", "john", "king", "lincoln", "mary", "new york", "ocean", "peter",
                "queen", "roger", "sugar", "thomas", "union"];
var sgTree = new ScapegoatTree(compare);
var valuesSet = new Set();
var midNV = Math.floor(natoValues.length / 2);

for (var i = 0; i < natoValues.length; i++) {
  sgTree.add(natoValues[i]);
  valuesSet.add(natoValues[i]);
}
console.log("--added " + natoValues.length + " nato phonetics--");
sgTree.verify();
assertSets(sgTree, valuesSet);

console.log(sgTree.traverse());

console.log("findEQ(" + JSON.stringify(wuValues[0]) + ") = " + sgTree.findEQ(wuValues[0]));
console.log("findGE(" + JSON.stringify(wuValues[0]) + ") = " + sgTree.findGE(wuValues[0]));
console.log("findEQ(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findEQ(natoValues[0]));
console.log("size = " + sgTree.size());

for (var i = wuValues.length - 1; i >= 0; i--) {
  sgTree.add(wuValues[i]);
  valuesSet.add(wuValues[i]);
}
console.log("--added (in reverse order) " + wuValues.length + " western union phonetics--");
sgTree.verify();
assertSets(sgTree, valuesSet);

console.log(sgTree.traverse());

console.log("findEQ(" + JSON.stringify(wuValues[0]) + ") = " + sgTree.findEQ(wuValues[0]));
console.log("findLE(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findLE(natoValues[0]));
console.log("minimum = " + sgTree.findGE(undefined) + ", maximum = " + sgTree.findLE(undefined));
console.log("size = " + sgTree.size() + ", size #2 = " + sgTree.size2() + ", size #3 = " + sgTree.size3());
console.log("height = " + sgTree.height());

for (var i = 0; i < midNV; i++) {
  sgTree.remove(natoValues[i]);
  valuesSet.delete(natoValues[i]);
}
console.log("--removed first " + midNV + " nato phonetics--");
sgTree.verify();
assertSets(sgTree, valuesSet);

console.log(sgTree.traverse2());

console.log("findEQ(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findEQ(natoValues[0]));
console.log("findLE(" + JSON.stringify(natoValues[midNV]) + ") = " + sgTree.findLE(natoValues[midNV]));
console.log("findGE(" + JSON.stringify(natoValues[0]) + ") = " + sgTree.findGE(natoValues[0]));

console.log(sgTree.bfTraverse(true));

console.log("toString = " + sgTree.toString());
sgTree.clear();
valuesSet.clear();
console.log("--clear--");
console.log("toString = " + sgTree.toString());

/** @version 0.99b */