Optimising the rebalancing operation in a self-balancing binary search treeOne of the core requirements for a self-balancing binary search tree, is that it, well, self-balances. Balancing strategies are what set different binary search tree variant apart. In this example, let’s have a look at the self-balancing operations as I had originally implemented them for a Dict based on AVL trees. If you’re curious about how rebalancing for AVL trees works, do have a look at Brian Hicks’ series on Functional Sets, where I first learned about them, too.First, a recap of what the code for the core balance function looked like at its first iteration:https://medium.com/media/a242caad42ef839cb1030a27e8536821/hrefThere are a few points we can improve upon straight away, based on what we saw in part 2: we have a few places where we’re piping the new tree with balanced inner node into our rotation functions.However, there is something much more important here: we’re calculating heightDiff dict in 4 different places. In the worst case scenario, i.e. an already balanced tree, that means we’re recalculating the function 4 times too many.So, let’s use a let..in block to memoise that value. Our benchmark, in this case, will be testing creation of trees of a certain size — 10 and 100 — with sequential keys, since this is a pathological case for tree insertion in self-balancing binary search trees.https://medium.com/media/bce0dc30dbc516c625d9515a0eabd509/hrefA modest improvementThat already helps some. We can push this a little further, though. One thing we actually know for sure, is that our tree will never become unbalanced by more that an absolute heightDiff of 2. So there is really no need to compare using > and < : we already know we should only ever enter those branches if the balance-factor is off by exactly 2. So, let’s replace those inequalities by == .This reveals something else: our first branch is a special case of our second branch, and our fourth branch is a special case of our third branch. In other words, we could group our cases. Doing this yields us the following.https://medium.com/media/e38155f98726f20230d8c32b05dcb2da/hrefAnother modest improvement!Now we’re getting somewhere. There’s one last thing we can do, though. We’re comparing diff to 2 constant values and introducing a default branch. There’s no reason we couldn’t do a straight case..of there, which would additionally buy us the ability to inline the heightDiff dict call, scrapping a let..in block. Let’s see if that gains us any performance:https://medium.com/media/881de7245eb719513593391ce40d1db5/hrefAlright!Alright! Not bad.Let’s have one last look at the before and after, and then sum up the takeaways here.https://medium.com/media/22aa30537633bb342ffe4fba700decee/hrefFinal score!Takeaways:
- Don’t recalculate things if you don’t need to.
- Prefer equality checks with constants over inequalities. This isn’t apparent here, but this is especially important when dealing with other types than integers.
- When doing multiple comparisons to constant values, prefer case..of (which generates switches) over long if/else..if/else.. blocks.
- Part 1: Introduction
- Part 2: Optimising the foldl operation in a recursive data structure
- Part 3: Optimising the rebalancing operation in a self-balancing search tree
- Part 4: Optimising a toHex function
- Part 5: Pitfalls you may run into