Part 10 is really just a continuation of Part 9, cleaning up the code into something a little more practical before getting to the next step. The beginning of this series is here.

Dextrous and Sinister

The AVL code so far has been symmetric between left and right, leading to a lot of duplicated code that differs only by these terms. Redundancy like this is a great way to create a bug that only appears when a particular code path is followed. The way to eliminate this redundancy is by parameterizing the side.

While there are a few ways to do this, one of the most natural is to use numbers to represent the side. This matches well with the balance factor (negative for left, positive for right), and also aligns somewhat with the idea of storing fields in a buffer.

As a first step, let's define constants to represent the sides:

const LEFT = -1;
const RIGHT = 1;

It will also be useful to refer to the opposite side:

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

Now, instead of defining a Node with left and right fields, we can use an array, and identify which index in the array with the side value. LEFT can map to 0, and RIGHT can map to 1. The setLeft and setRight methods can be updated to take the side as a parameter:

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

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

Contrary to the OOP principle of information hiding, the previous incarnation of this code was reading and updating the left and right fields directly. We want to encapsulate that instead to allow for this parameterization.

The setChild function is for the initial setting of the child of a node, and it works out its own balance from this. However, the rotation operations require setting the children while manually updating the balance. So I'm going to refactor this into a pair of methods: the original setChild which is for the initial setting of the child of a node, and updateChild which is used by the rotation operations. We will also want a getter function for the child nodes.

class Node {
  constructor(value) {
    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];
  }
}

We can leave the balance field for the moment, since getters and setters are verbose, and not really needed for that field yet. But they will have to be introduced when we move to persisting this structure, since the balance field will need to be stored in the buffer along with the rest of the node.

Stir Until Reduced

With this new Node definition, we can rewrite the other functions.

The insertNode function (yes, it's still a function and not a method on Node. There's a reason for that, but I'll get to it later) can now avoid the outer if/else statement, and be reduced to the simpler structure found in each branch:

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

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

Note that the syntax of the code is a little bit more complex. For instance, the expression:
node.left = insertNode(node.left, newNode);
has changed to:
node.updateChild(side, insertNode(node.getChild(side), newNode));
This is because we're now calling a setter instead of directly accessing the left field. Languages like Scala and C++ let you override the = operator so that things like node.left = will call your setter. However, operator overloading isn't available in Javascript. Fortunately, this is not really a problem as it is only a syntactic convenience.

Now, instead of the rebalance function finding 4 different alternatives, it need only look for 2:

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

And finally, the rebalancing can be done using letters to indicate Side and Other-side to replace Left and Right:

function rebalanceSS(node, side) {
  nodeS = node.getChild(side);
  node.updateChild(side, nodeS.getChild(other(side)));
  nodeS.updateChild(other(side), node);
  node.balance = 0;
  nodeS.balance = 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.balance == otherSide) {
    node.balance = 0;
    nodeS.balance = side;
  } else if (nodeSO.balance == side) {
    node.balance = otherSide;
    nodeS.balance = 0;
  } else {
    node.balance = 0;
    nodeS.balance = 0;
  }
  nodeSO.balance = 0;
  return nodeSO;
}

This has nearly halved the code from the previous post, and ensured that the behavior is identical for both left and right conditions. That's a win.

Extraneous

The other functions that were in use for accessing this structure just need some small tweaks to use the new getter methods. But rather than creating a string with the tree contents, it makes more sense to create an array. This can be converted to a string with .join if needed.

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) {
  return appendToArray([], t.root);
}

function height(node) {
  if (node === undefined) return 0;
  return 1 + Math.max(height(node.getChild(LEFT)), height(node.getChild(RIGHT)));
}

We can check that this all now works the way the last one did:

> let pi = new Tree(digits[0]);
> digits.slice(1).forEach(d => pi.add(d));
> toArray(pi).join(', ') === digits.sort().join(', ')
true

Recap

We just rewrote the previous AVL Tree implementation, parameterizing the left and right variations. It made sense to build the full left and right variations to start with, as it is easier to follow and see that everything is working correctly. However, once this was established, the shift to parameterizing the sides reduced the code size significantly, and the underlying array is starting to look more like a buffer underlying the persisted node.

This gets us to the point of building a balanced tree over a buffer, so let's look at that next.