22 Apr 2025Balanced search trees are an improvement on binary search trees (BST). If you have a look at my page on binary search trees, you will see that those trees can become unbalanced, e.g. with most nodes on one side of a root. Search trees perform best when each node is on a similar depth from the root, which is called a balanced tree. A simple way to achieve balance is through 2-3 trees, of which you see an example above. Their name stems from the fact that internal nodes have either 2 or 3 child nodes, whereas BSTs have 0 to 2. In a 2-3 tree the height above each terminal node is equal, on the tree above, it is 2 nodes to the root.
One main operation on 2-3 trees is to find numerical keys in logarithmic time. This is visualised on the panel above. By using the node keys as a guide, the algorithm traverses the tree until it either finds the right node (green) or comes to the conclusion that the key is not in the tree (red). The time required for this operation is proportional to the height of the tree and hence to the logarithm of the number of keys in the tree.
Keys are present in the 2-3 tree according to an order, from smaller numbers (left) to larger numbers (right). By traversing the tree in this fashion we can enumerate all keys in order.
Here we see a 2-3 tree with the opposite order to the previously presented 2-3 trees. Large values are to the left and smaller values are to the right. The tree invariant is illustrated in the same fashion by the animation. For the rest of this page, we return to the small to large ordering.
Here we have omitted the numbers in the nodes, to display a larger 2-3 tree. Note how 2 and 3 children nodes are mixed throughout the tree. With just 4 levels under the root node, this tree accomodates 90 numbers. How does the tree get its mix of 2 and 3-nodes? While inserting numbers into the tree, the algorithm maintains balance of depth by either inserting values into the smaller nodes, or splitting larger nodes into three 2-nodes.
Another form of balanced search trees are red-black trees, which can be derived from 2-3 trees by splitting all 3-nodes into two 2-nodes, by inserting a red edge between their keys. All other, previously present edges, are called black edges. Nodes are coloured according to the edge leading into them. This way we achieve a form of binary search tree, in which the depth of leaves under the root is balanced up to a factor of at most 2. On the diagram above, the 2-3 tree from the first panel on this page has been transformed into a red-black tree, containing the exact same keys.
Again, we can transform the large 2-3 tree from above into an equivalent red-black tree. We won't go into detail about operations on this tree, but they do make sure that this type of tree remains largely balanced. There are different definitions of red-black trees in literature, this is the version found in the book named below.
If you enjoyed this page, there are more algorithms and data structures to be found on the main page.