A Symmetric Position
Tags: structure, avl, tree
Published: 2020-04-16 19:08:03

Part 10 is really just a continuation of [Part 9](https://dev.to/quoll/a-balanced-tree-27ik), cleaning up the code into something a little more practical before getting to the next step. The beginning of this series is [here](https://dev.to/quoll/what-s-with-data-structures-2fk7).

# 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](https://dev.to/quoll/mapping-the-way-15j2#getters).

<a name="sides"/>As a first step, let's define constants to represent the sides:
```javascript
const LEFT = -1;
const RIGHT = 1;
```
It will also be useful to refer to the opposite side:
```javascript
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:
```javascript
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](https://en.wikipedia.org/wiki/Information_hiding), the [previous incarnation of this code](https://dev.to/quoll/a-balanced-tree-27ik#rebalanceRR) 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.<a name="node"/>
```javascript
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](https://dev.to/quoll/a-balanced-tree-27ik#insert-node) (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:<a name="insertNode"/>
```javascript
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.

<a name="rebalance"/>Now, instead of the `rebalance` function finding 4 different alternatives, it need only look for 2:
```javascript
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 <strong><em>S</em></strong>ide and <strong><em>O</em></strong>ther-side to replace <strong><em>L</em></strong>eft and <strong><em>R</em></strong>ight:
```javascript
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.<a name="toArray"/>
```javascript
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:
```javascript
> 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.