A Balanced Tree
Tags: structure, avl, tree
Published: 2020-04-16 05:18:59

Part 9 arrives after many months, following many personal events, and now a worldwide pandemic. You'll find [part 8 back here](https://dev.to/quoll/save-the-trees-4n4p), or if you've forgotten everything as I had, you can go back to [the beginning](https://dev.to/quoll/what-s-with-data-structures-2fk7).

# Georgy and Evgenii
The binary trees discussed in previous posts have a major problem that makes them unsuitable for general use, and that is that they can be _unbalanced_. This means that some branches of the tree may be very deep, while others may be very shallow. In the worst case, such as when sorted data is inserted, a tree can even become a linked list.
![Unbalanced tree](https://github.com/quoll/raw-data/raw/master/pi-linked.png)

There are various approaches to balancing a tree, but the one I want to focus on is the [AVL Tree](https://en.wikipedia.org/wiki/AVL_tree). The name comes from the designers, whose names were Georgy Adelson-Velsky and Evgenii Landis.

AVL trees are a binary tree like the ones already discussed, with the additional property of being _balanced_. This means that if any branch starts to get much longer than the other branches, then the nodes will get rearranged, or "rotated", in such a way as to rebalance the tree. Of particular significance is that the number of write operations for a rotation during insertion is always a fixed, constant amount. This differs significantly from other tree structures which can result in occasional pauses when large rebalancing write operations occur.

This isn't to say that writing is an _O(1)_ operation. All sorted trees require an _O(log(n))_ search to be performed so the location for inserting can be identified, and nodes above an insertion need to have their balance updated until the rotation point is found. But once a tree has been accessed, most of the top levels will be cached in memory by the Operating System, making the tree fast to read, and rotations almost always happen near the leaves, making balance updates small as well.

## Rebalancing
Back in [part 7](https://dev.to/quoll/shaking-the-tree-2oi2), I presented the code for creating a binary tree. I also introduced a function called `height` which recursively found the height at a node, and a function called `balance` which returned the difference in heights.

A distinguishing property of an AVL tree is that the absolute value of the balance of a node will never get larger than 1. If it ever gets as high as 2 (or as low as -2) then the node must be rebalanced. Rebalancing is a little involved, and I will get to that soon, but for now just be aware that it involved moving 2 or 3 nodes in the tree, and nothing else.

If a node is rebalanced, then no further rebalancing is required throughout the tree. This means that the balance of any parents of a rebalanced node will not change after rebalancing. This not only lets the work stop at this point, but it also means that nodes can remember their balance, and not need to worry about the heights of their branches that gave them that balance.

To accomplish this, I want to add a new `balance` value to each node. This updates the [Node definition](https://dev.to/quoll/shaking-the-tree-2oi2#node) from part 7:
<a name="node"/>
```javascript
class Node {
  constructor(value) {
    this.value = value;
    this.balance = 0;
  }

  setLeft(left) {
    this.left = left;
    this.balance = this.balance - 1;
    return this;
  }

  setRight(right) {
    this.right = right;
    this.balance = this.balance + 1;
    return this;
  }
}
```
This initializes a node's `balance` to 0, and when a child is added to the node, then the balance is shifted in the direction of the child (-1 for left, +1 for right).

Now we want to update the [function for inserting a node into a tree](https://dev.to/quoll/shaking-the-tree-2oi2#insert-node) to update this balance: 
<a name="insert-node"/>
```javascript
function insertNode(node, newNode) {
  if (newNode.value <= node.value) {
    if (node.left === undefined) {
      return node.setLeft(newNode);
    } else {
      let childBalance = node.left.balance;
      node.left = insertNode(node.left, newNode);
      // Did the child balance change from 0? Then it's deeper
      if (childBalance == 0 && node.left.balance != 0) {
        node.balance = node.balance - 1;
      }
    }
  } else {
    if (node.right === undefined) {
      return node.setRight(newNode);
    } else {
      let childBalance = node.right.balance;
      node.right = insertNode(node.right, newNode);
      // Did the child balance change from 0? Then it's deeper
      if (childBalance == 0 && node.right.balance != 0) {
        node.balance = node.balance + 1;
      }
    }
  }
  // ... more ...
  return node;
}
```
In the previous version of this function, the two `else` clauses just called `this.insertNode`. This time, they start by remembering the balance of the child they are about to insert into, and if it changes to indicate that the height got deeper, then they will update the balance of this node.

Recall that we are only inserting things into this tree, so if a balance changes towards 0 then this means that a node that was heavy on one side has now evened out, and if it changes from 0 then it must have become deeper on one side.

This will record balances correctly, but it isn't an AVL tree unless those balances are kept within the range of -1 to 1. So now we need to add that operation by replacing the `... more ...` comment with the following code:
```javascript
  if (Math.abs(node.balance) == 2) {
    return rebalance(node);
  }
```
This just checks if the balance of a node has changed to -2 or +2, in which case a rebalance needs to happen. This is where the fun happens.

## Rebalancing
The first step to rebalancing is to figure out the kind of rebalancing that is needed. There are 2 different types of rebalancing operations, but because of symmetry they are each duplicated for left and right.

Rather than duplicate the full explanation here, I will refer you to the [Wikipedia article](https://en.wikipedia.org/wiki/AVL_tree#Rebalancing), and then you can come back here to see it play out.

### Simple Rotation
The first type of rebalancing is a [simple rotation of nodes](https://en.wikipedia.org/wiki/AVL_tree#Simple_rotation). This is required when a node is heavy on one side, and the heavy child is also heavy on the same side. For instance, if a node has a balance of +2 (it has to be +2 if it's being rebalanced), and its right child has a balance of +1. I will call this an RR rotation, indicating that both nodes were heavy on the right. In this case, the child on the right becomes the new root of this branch, and the previously unbalanced node will become the left child that root. The children of these nodes must be switched appropriately to keep the ordering, and the balances of each node can be reset to zero.
<a name="rebalanceRR"/>
```javascript
function rebalanceRR(node) {
  nodeR = node.right;
  node.right = nodeR.left;
  nodeR.left = node;
  node.balance = 0;
  nodeR.balance = 0;
  return nodeR;
}
```
The `rebalanceLL` function is symmetric, with all references to right/left reversed:
<a name="rebalanceLL"/>
```javascript
function rebalanceLL(node) {
  nodeL = node.left;
  node.left = nodeL.right;
  nodeL.right = node;
  node.balance = 0;
  nodeL.balance = 0;
  return nodeL;
}
```
### Double Rotation
Things get a little more complex when the heavy child is heavy on the inside rather than the outside of the structure. The resulting moves can be performed with a double rotation, but it is more straightforward to implement the overall move in a single step.

Starting with a child on the right that is heavy on the left, we have the `rebalanceRL` function:
<a name="rebalanceRL"/>
```javascript
function rebalanceRL(node) {
  nodeR = node.right;
  nodeRL = nodeR.left;
  node.right = nodeRL.left;
  nodeR.left = nodeRL.right;
  nodeRL.left = node;
  nodeRL.right = nodeR;
  if (nodeRL.balance < 0) {
    node.balance = 0;
    nodeR.balance = 1;
  } else if (nodeRL.balance > 0) {
    node.balance = -1;
    nodeR.balance = 0;
  } else {
    node.balance = 0;
    nodeR.balance = 0;
  }
  nodeRL.balance = 0;
  return nodeRL;
}
```
The first 6 lines accomplish the rotations. This puts the right/left child (`nodeRL`) at the root, the original root (`node`) to the left of this new root, the left child of `nodeRL` to the right of `node`, and the right child of the original root (`nodeR`) to the right of the new root. It took me a while of working it through with pencil and paper to fully understand this when I first encountered it, but once you try it out it all makes sense.

The last `if/elseif/else` block sets the balances appropriately. How these work out depends on a few things. Was the `nodeRL` node heavy on the left or the right? This changes the outcome such that either `node` or `nodeR` will be unbalanced, while the other is balanced. There is also the case where the root node is near the leaves of the tree. In this case, it will not have a left node, and `nodeRL` will not have any children at all, making its balance 0. In this case, both `node` and `nodeR` will get a final balance of 0.

While rotations are something that I find I can do in my head, determining the rebalancing from first principles is something that definitely requires pen and paper to work out for yourself.

Just like the duality of `rebalanceRR/rebalanceLL`, the `rebalanceLR` function is symmetric with `rebalanceRL`:
<a name="rebalanceLR"/>
```javascript
function rebalanceLR(node) {
  nodeL = node.left;
  nodeLR = nodeL.right;
  node.left = nodeLR.right;
  nodeL.right = nodeLR.left;
  nodeLR.right = node;
  nodeLR.left = nodeL;
  if (nodeLR.balance > 0) {
    node.balance = 0;
    nodeL.balance = -1;
  } else if (nodeLR.balance < 0) {
    node.balance = 1;
    nodeL.balance = 0;
  } else {
    node.balance = 0;
    nodeL.balance = 0;
  }
  nodeLR.balance = 0;
  return nodeLR;
}
```
## Loading Up
Let's try putting some data into this, and see if it works as expected.
```javascript
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];
```
It's a mental exercise for me to try to remember these digits. I try to add on a few more every birthday. I figure that when I turn 100 I will really impress some people!

Inserting these digits in order should sort them. We'll start by creating the tree with the first digit, and then insert the rest:
```javascript
let pi = new Tree(digits[0]);
digits.slice(1).forEach(d => pi.add(d));
```
Do they come out sorted? Let's traverse using the [`treeString` function](https://dev.to/quoll/shaking-the-tree-2oi2#treeString) from part 7, remembering that the function takes a node, rather than the tree object: 
```javascript
> treeString(pi.root)
'0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9, 9'
```
This looks about right. Lets compare with the correctly sorted digits:
```javascript
> treeString(pi.root) === digits.sort().join(', ')
true
```
But how about the height of the tree?

`digits` is 66 elements long. An efficient binary tree should be storing at close to ⌈log2(n)⌉. The log2(66) ≈ 6.044, so the minimum possible number is 7, and we are hoping for a number not much larger than that:
```javascript
> height(pi.root)
7
```
Which is fortuitously better than I'd hoped for 😊

## Recap
After a long break, I've finally shown how to balance a binary tree using the AVL algorithm. While [B-Trees](https://en.wikipedia.org/wiki/B-tree) are the industry standard for database storage, years of experience have shown AVL trees to be highly competitive for write-heavy storage.

There is quite a bit of redundancy around the symmetry of this code, and I will be demonstrating how to avoid this in the [next installment](https://dev.to/quoll/a-symmetric-position-55o4). This has benefits in avoiding silly duplication errors, as well as moving a little closer to the structures that we eventually want in persistent storage.