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

Optimising for performance in Elm, Pt. 3 was originally published in Ilias Van Peer on Medium, where people are continuing the conversation by highlighting and responding to this story.