Balancing a Binary Search Tree

Question

I was reading about binary search trees on it's Wikipedia article. I was a little confused by this image. Why is it that the right branch to the head node does not have a sub-tree? I understand why it can be valid like this but surely the "8" could branch to "13" instead, then "10" and "14" could become the descendants of "13". It seems like this would be far more balanced. So I researched around for more information about binary search tree balancing and I'm still unsure. Why is the diagram in the Wikipedia article was favored? Is my suggestion wrong?

Depth-first in-order traversal still works as I presume the same for all other traversal methods.

Answer 1

Yes, the right subtree could be $13(10,14)$.
But notice that the article you've linked discusses the most naive version of building a Binary Search Tree, in which numbers are simply inserted into the tree one-after-another without balancing. So in your example first the $10$ was inserted, then the $14$, then $13$. Of course there are plenty of other algorithms that balance the tree (they are also linked in the Wiki-article).

Answer 2

Yes, @john_leo is right. I like to add to his answer.

When one is interested in building balanced trees, one usually does not insist on the best balanced tree, with completely filled levels except the last level. When building balanced trees one adds some "slack" in the definition to avoid excessive rebalancing every addition. As an example, I add a picture of an AVL-tree (with its balance factors) that is within the limits imposed by the definition.

The purpose of various types of balanced search trees is to keep performance (adding, deleting, searching) within logarithmic time.