# 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.

### Balance Factor

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 `factor` invocation. 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.

### Rotations

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.

### Re-balancing Phase

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.

### Example Usage

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 `balance` one.

These created data-structures can then be visualised using the following function.