Clojure Data Structures and Algorithms Cookbook

Building self-balancing, search-efficient splay trees

One widely used tree structure for storing data are binary search trees. For instance, in order to store an element into such trees, you'd recursively walk it down, seeing every time how the value you're inserting compares in regard to the one stored in the node currently being visited if it is less you carry-on with the same process visiting the left sub-tree, else you'd dive into the right branch. Searching pretty much follows the same logic, recursively descending the tree and deciding at each level if you'd go left or right.

Now the most common problem with these trees is balance, or the lack thereof if left uncontrolled, one branch of the binary search tree could get substantially longer ...