Red-black tree using open content

/* An implementation of left-leaning red-black 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.
 */

// Vertex colors. credit: Morin 9.2.
const red = 0, black = 1;

/** A node. */
class Vertex {
  /** constructor() credit: Morin 6.1, 9.2. */
  constructor() {
    this.value;  // any
    this.left;   // Vertex ref
    this.right;  // Vertex ref
    this.parent; // Vertex ref
    this.color;  // number
    this.bSeen;  // boolean
  }
}

/** A sorted set. */
class RedBlackTree {
  #nil; #root; #numV; #compare;
  /** constructor() credit: Morin BinaryTree.java, BinarySearchTree.java, RedBlackTree.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.#root = this.#nil;  // root vertex
    this.#numV = 0;   // number of vertices
    this.#compare = comparator;

    this.#nil.color = black;
  }

  /** #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]);
  }

  /** #pushBlack() credit: Morin 9.2.2.
   * @param {Vertex} vertex vertex to push black
   */
  #pushBlack(vertex) {
    vertex.color--;
    vertex.left.color++;
    vertex.right.color++;
  }

  /** #pullBlack() credit: Morin 9.2.2.
   * @param {Vertex} vertex vertex to pull black
   */
  #pullBlack(vertex) {
    vertex.color++;
    vertex.left.color--;
    vertex.right.color--;
  }

  /** #swapColors() credit: Morin RedBlackTree.java.
   * @param {Vertex} a a vertex
   * @param {Vertex} b another vertex
   */
  #swapColors(a, b) {
    var c = a.color;
    a.color = b.color;
    b.color = c;
  }

  /** #rotateLeft() credit: Morin 7.2.
   * @param {Vertex} vertex vertex to rotate left
   */
  #rotateLeft(vertex) {
    var cur = vertex.right;
    cur.parent = vertex.parent;
    if (cur.parent != this.#nil) {
      if (cur.parent.left == vertex) { cur.parent.left = cur; }
      else { cur.parent.right = cur; }
    }
    vertex.right = cur.left;
    if (vertex.right != this.#nil) {
      vertex.right.parent = vertex;
    }
    vertex.parent = cur;
    cur.left = vertex;
    if (vertex == this.#root) {
      this.#root = cur;
      this.#root.parent = this.#nil;
    }
  }

  /** #rotateRight() credit: Morin 7.2.
   * @param {Vertex} vertex vertex to rotate right
   */
  #rotateRight(vertex) {
    var cur = vertex.left;
    cur.parent = vertex.parent;
    if (cur.parent != this.#nil) {
      if (cur.parent.left == vertex) { cur.parent.left = cur; }
      else { cur.parent.right = cur; }
    }
    vertex.left = cur.right;
    if (vertex.left != this.#nil) {
      vertex.left.parent = vertex;
    }
    vertex.parent = cur;
    cur.right = vertex;
    if (vertex == this.#root) {
      this.#root = cur;
      this.#root.parent = this.#nil;
    }
  }

  /** #flipLeft() credit: Morin 9.2.2.
   * @param {Vertex} vertex vertex to flip left
   */
  #flipLeft(vertex) {
    this.#swapColors(vertex, vertex.right);
    this.#rotateLeft(vertex);
  }

  /** #flipRight() credit: Morin 9.2.2.
   * @param {Vertex} vertex vertex to flip right
   */
  #flipRight(vertex) {
    this.#swapColors(vertex, vertex.left);
    this.#rotateRight(vertex);
  }

  /** #addFixup() credit: Morin 9.2.3.
   * @param {Vertex} vertex vertex to fix-up for add
   */
  #addFixup(vertex) {
    while (vertex.color == red) {
      if (vertex == this.#root) {  // vertex is the root = done
        vertex.color = black;
        return;
      }
      var cur = vertex.parent;
      if (cur.left.color == black) {  // ensure left-leaning
        this.#flipLeft(cur);
        vertex = cur;
        cur = vertex.parent;
      }
      if (cur.color == black) {
        return;  // no red-red edge = done
      }
      var gP = cur.parent;  // grandparent of vertex
      if (gP.right.color == black) {
        this.#flipRight(gP);
        return;
      } else {
        this.#pushBlack(gP);
        vertex = gP;
      }
    }
  }

  /** #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;
  }

  /** #addChild() credit: Morin 6.2.2.
   * @param {Vertex} prev last vertex encountered
   * @param {Vertex} vertex vertex to add
   * @returns {boolean} success?
   */
  #addChild(prev, vertex) {
    if (prev == this.#nil) {
      this.#root = vertex;  // inserting into empty tree
    } else {
      var res = this.#compare(vertex.value, prev.value);
      if (res < 0) {
        prev.left = vertex;
      } else if (res > 0) {
        prev.right = vertex;
      } else {
        return false;  // vertex.value is already in the tree
      }
      vertex.parent = prev;
    }
    this.#numV++;
    return true;
  }

  /** #addVertex() credit: Morin BinarySearchTree.java.
   * @param {Vertex} vertex vertex to add
   * @returns {boolean} success?
   */
  #addVertex(vertex) {
    var prev = this.#findLast(vertex.value);
    return this.#addChild(prev, vertex);
  }

  /** add() credit: Morin 9.2.3.
   * @param {any} value value to add
   * @returns {boolean} success?
   */
  add(value) {
    var vertex = this.#newVertex(value);
    vertex.color = red;
    var res = this.#addVertex(vertex);
    if (res) { this.#addFixup(vertex); }
    return res;
  }

  /** #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) {
      this.#root = cur;
      prev = this.#nil;
    } else {
      prev = vertex.parent;
      if (prev.left == vertex) {
        prev.left = cur;
      } else {
        prev.right = cur;
      }
    }
    if (cur != this.#nil) {
      cur.parent = prev;
    }
    this.#numV--;
  }

  /** #removeFixupCase1() credit: Morin 9.2.4.
   * @param {Vertex} vertex vertex to fix-up for remove
   * @returns {Vertex} fixed-up vertex
   */
  #removeFixupCase1(vertex) {
    this.#flipRight(vertex.parent);
    return vertex;
  }

  /** #removeFixupCase2() credit: Morin 9.2.4.
   * @param {Vertex} vertex vertex to fix-up for remove
   * @returns {Vertex} fixed-up vertex
   */
  #removeFixupCase2(vertex) {
    var w = vertex.parent;
    var v = w.right;
    this.#pullBlack(w);  // w.left
    this.#flipLeft(w);  // w is now red
    var q = w.right;
    if (q.color == red) {  // q-w is red-red
      this.#rotateLeft(w);
      this.#flipRight(v);
      this.#pushBlack(q);
      if (v.right.color == red) {
        this.#flipLeft(v);
      }
      return q;
    } else {
      return v;
    }
  }

  /** #removeFixupCase3() credit: Morin 9.2.4.
   * @param {Vertex} vertex vertex to fix-up for remove
   * @returns {Vertex} fixed-up vertex
   */
  #removeFixupCase3(vertex) {
    var w = vertex.parent;
    var v = w.left;
    this.#pullBlack(w);
    this.#flipRight(w);  // w is now red
    var q = w.left;
    if (q.color == red) {  // q-w is red-red
      this.#rotateRight(w);
      this.#flipLeft(v);
      this.#pushBlack(q);
      return q;
    } else {
      if (v.left.color == red) {
        this.#pushBlack(v);  // both v's children are red
        return v;
      } else {  // ensure left-leaning
        this.#flipLeft(v);
        return w;
      }
    }
  }

  /** #removeFixup() credit: Morin 9.2.4.
   * @param {Vertex} vertex vertex to fix-up for remove
   */
  #removeFixup(vertex) {
    while (vertex.color > black) {
      if (vertex == this.#root) {
        vertex.color = black;
      } else if (vertex.parent.left.color == red) {
        vertex = this.#removeFixupCase1(vertex);
      } else if (vertex == vertex.parent.left) {
        vertex = this.#removeFixupCase2(vertex);
      } else {
        vertex = this.#removeFixupCase3(vertex);
      }
    }
    if (vertex != this.#root) {  // restore left-leaning property if needed
      var cur = vertex.parent;
      if (cur.right.color == red && cur.left.color == black) {
        this.#flipLeft(cur);
      }
    }
  }

  /** remove() credit: Morin 9.2.4.
   * @param {any} value value to remove
   * @returns {boolean} success?
   */
  remove(value) {
    var prev = this.#findLast(value);
    if (prev == this.#nil || this.#compare(prev.value, value) != 0) {
      return false;
    }
    var cur = prev.right;
    if (cur == this.#nil) {
      cur = prev;
      prev = cur.left;
    } else {
      while (cur.left != this.#nil) {
        cur = cur.left;
      }
      prev.value = cur.value;
      prev = cur.right;
    }
    this.#splice(cur);
    prev.color += cur.color;
    prev.parent = cur.parent;
    this.#removeFixup(prev);
    return true;
  }

  /** 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);
  }

  /** #verifyVertex() credit: Morin RedBlackTree.java.
   * @param {Vertex} vertex vertex to verify
   * @returns {number} black height of vertex
   */
  #verifyVertex(vertex) {
    if (vertex == this.#nil) {
      return vertex.color;
    }
    if (vertex.color < red || vertex.color > black) {
      throw new Error("verify: invalid color = " + vertex.color);
    }
    if (vertex.color == red) {
      if (vertex.left.color == red || vertex.right.color == red) {
        throw new Error("verify: red-red edge found");
      }
    }
    if (vertex.right.color == red && vertex.left.color != red) {
      throw new Error("verify: non-left-leaning vertex found");
    }
    var depthL = this.#verifyVertex(vertex.left);
    var depthR = this.#verifyVertex(vertex.right);
    if (depthL != depthR) {
      throw new Error("verify: black-height property violated");
    }
    return depthL + vertex.color;
  }

  /** verify() credit: Morin RedBlackTree.java. */
  verify() {
    if (this.#sizeOfV(this.#root) != this.#numV) {
      throw new Error("verify: size is incorrect");
    }
    this.#verifyVertex(this.#root);
  }

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

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

  /** #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]);
        var size = this.#sizeOfV(vertices[i]);
        retVertices += "  height=" + height + "  size=" + size;
        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 {RedBlackTree} 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"];
var wuValues = ["adams", "boston", "chicago", "denver", "easy", "frank", "george", "henry",
                "ida", "john", "king", "lincoln", "mary", "new york", "ocean", "peter",
                "queen", "roger", "sugar", "thomas"];
var rbTree = new RedBlackTree(compare);
var valuesSet = new Set();

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

console.log(rbTree.traverse());

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

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

console.log(rbTree.traverse());

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

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

console.log(rbTree.traverse2());

console.log("findEQ(" + JSON.stringify(natoValues[0]) + ") = " + rbTree.findEQ(natoValues[0]));
var ndxLast = natoValues.length / 2 - 1;
console.log("findLE(" + JSON.stringify(natoValues[ndxLast]) + ") = " + rbTree.findLE(natoValues[ndxLast]));
console.log("findGE(" + JSON.stringify(natoValues[0]) + ") = " + rbTree.findGE(natoValues[0]));

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

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

/** @version 1.0 */