AVLTree.js

assert = require('assert');

const LEFT = -1;
const RIGHT = 1;

function other(side) {
  return side == LEFT ? RIGHT : LEFT;
}

class Node {
  constructor(transactionId, value) {
    this.transactionId = transactionId;
    this.value = value;
    this.balance = 0;
    this.children = [undefined, undefined];
  }

  updateChild(side, child) {
    let index = side == LEFT ? 0 : 1;
    this.children[index] = child;
    return this;
  }

  setChild(side, child) {
    this.updateChild(side, child);
    this.balance = (this.balance === undefined) ? side : this.balance + side;
    return this;
  }

  getChild(side) {
    return this.children[side == LEFT ? 0 : 1];
  }

  getBalance() {
    return this.balance;
  }

  setBalance(balance) {
    this.balance = balance;
    return this;
  }

  copyOnWrite(transactionId) {
    if (this.transactionId === transactionId) {
      return this;
    } else {
      let node = new Node(transactionId);
      node.value = this.value;
      node.balance = this.balance;
      node.children = this.children.slice();
      return node;
    } 
  } 
} 

class Tree {
  constructor(other = null) {
    if (other === null) {
      this.root = null;
      this.nextTransaction = 0;
    } else {
      this.root = other.root;
      this.nextTransaction = other.nextTransaction;
    }
    this.transactionRoot = null;
    this.transactionId = null;
  }

  startTx() {
    this.transactionId = this.nextTransaction++;
    this.transactionRoot = this.root;
    return this;
  }

  commitTx() {
    var nextTree = new Tree(this);
    this.transactionId = null;
    nextTree.root = this.transactionRoot;
    this.transactionRoot = null;
    return nextTree;
  }

  rollbackTx() {
    this.transactionId = null;
    this.transactionRoot = null;
    return this;
  }

  add(value) {
    if (this.transactionId == null) {
      throw "Update occurred outside of a transaction";
    }
    let node = new Node(this.transactionId, value);
    if (this.transactionRoot === null) {
      this.transactionRoot = node;
    } else {
      this.transactionRoot = this.insertNode(this.transactionRoot, node);
    }
    return this;
  }

  insertNode(node, newNode) {
    let side = (newNode.value < node.value) ? LEFT : RIGHT;
    node = node.copyOnWrite(this.transactionId);

    if (node.getChild(side) === undefined) {
      return node.setChild(side, newNode);
    } else {
      let childBalance = node.getChild(side).getBalance();
      node.updateChild(side, this.insertNode(node.getChild(side), newNode));
      // Did the child balance change from 0? Then it's deeper
      if (childBalance == 0 && node.getChild(side).getBalance() != 0) {
        node.setBalance(node.getBalance() + side);
      }
    }

    if (Math.abs(node.getBalance()) == 2) {
      return rebalance(node);
    }
    return node;
  }

}

function rebalance(node) {
  side = node.getBalance() < 0 ? LEFT : RIGHT;
  if (side == node.getChild(side).getBalance()) {
    return rebalanceSS(node, side);
  } else {
    return rebalanceSO(node, side);
  }
}

function rebalanceSS(node, side) {
  nodeS = node.getChild(side);
  node.updateChild(side, nodeS.getChild(other(side)));
  nodeS.updateChild(other(side), node);
  node.setBalance(0);
  nodeS.setBalance(0);
  return nodeS;
}

function rebalanceSO(node, side) {
  otherSide = other(side);

  nodeS = node.getChild(side);
  nodeSO = nodeS.getChild(otherSide);
  node.updateChild(side, nodeSO.getChild(otherSide));
  nodeS.updateChild(otherSide, nodeSO.getChild(side))
  nodeSO.updateChild(otherSide, node);
  nodeSO.updateChild(side, nodeS);
  if (nodeSO.getBalance() == otherSide) {
    node.getBalance(0);
    nodeS.getBalance(side);
  } else if (nodeSO.getBalance() == side) {
    node.setBalance(otherSide);
    nodeS.setBalance(0);
  } else {
    node.setBalance(0);
    nodeS.setBalance(0);
  }
  nodeSO.setBalance(0);
  return nodeSO;
}

function appendToArray(arr, node) {
  if (node === undefined) {
    return arr;
  } else {
    return appendToArray(appendToArray(arr, node.getChild(LEFT)).concat([node.value]), node.getChild(RIGHT));
  }
}

function toArray(t) {
  if (t.root == null) {
    return [];
  }
  return appendToArray(appendToArray([], t.root.getChild(LEFT)).concat(t.root.value), t.root.getChild(RIGHT));
}


// user session
let digits =
  [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5, 8, 9, 7, 9, 3, 2, 3, 8, 4, 6, 2, 6, 4, 3, 3, 8, 3, 2, 7, 9, 5, 0,
   2, 8, 8, 4, 1, 9, 7, 1, 6, 9, 3, 9, 9, 3, 7, 5, 1, 0, 5, 8, 2, 0, 9, 7, 4, 9, 4, 4, 5, 9, 2, 3, 0];

var pi = new Tree();
pi.startTx();
digits.slice(0, 33).forEach(d => pi.add(d));
var halfPi = pi.commitTx();

halfPi.startTx();
digits.slice(33).forEach(d => halfPi.add(d));
var fullPi = halfPi.commitTx();

assert(toArray(halfPi).join(',') === digits.slice(0, 33).sort().join(','));
assert(toArray(fullPi).join(',') === digits.sort().join(','));