AVL Trees in Clojure
An AVL tree is a self-balancing binary search tree, where-by the height of a node’s children differ by at most one. In the event that this property is violated a re-balancing process takes place. In the past I have discussed how to implement a Binary Search Tree in Clojure, providing average time complexity of O(log n). However, in the event that the order of insertion is sequential (either every value greater than, or every value less than the last), time complexity increases to be linear, the same as a linked-list. Self-balancing trees such as the AVL variant provide us with the familiar worst-case of O(log n), thanks to it’s re-balancing phase.
Using the previous Binary Search Tree implementation as a base, we are able to expand upon this to include the AVL property.
For the sake of performance you would typically store the height of each nodes children within the structure, however, as I wish to re-use the existing implementation I will instead calculate their height upon
The balance factor per. node is calculated by the difference between the two child node’s heights, as shown below.
The above two functions provide us with the described behavior, allowing us to supply a root node and return it’s balance factor.
So as to complete the final re-balancing step we must also be able to rotate a given node both left and right within the tree structure.
This can be achieved as shown above, taking advantage of an immutable approach.
With the balance factor and rotation actions now available, we are able to begin work on the four different situations a node could be placed in that would require a tree rotation.
With these conditions now locatable, we can apply the desired tree rotations which can be seen visualised in the diagrams above.
Finally, we are able to create a new AVL insertion/deletion variant, that is a composition of the Binary Search Tree functions and the newly created
These created data-structures can then be visualised using the following function.