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 than the other, leading to inefficient access times.

Self-balancing binary search trees were devised to address this matter. These trees have the capability to rearrange themselves on insert operations, so their left and right branches' depth are kept...