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.
Top comments (0)