Interactive Data Structure Visualizations
Height-Balanced Trees

Height-balancing is important when we wish to use a binary search tree to implement a keyed table. The reason it is important is that in a height-balanced tree, the ratio of the height of the tree to the number of nodes is logarithmic. Maintaining a logarithmic ratio ensures that the big-O for the insert, delete, and find operations will all be logarithmic.

Every binary tree has a height, or depth, that depends upon the height of its subtrees. Observe when interacting with the corresponding visualization in the I'll Try mode that you will be asked supply the height of each of the subtrees first. In fact, you will be prompted for the height of each node in a postorder traversal of the tree. Another important observation that you should make is that in this visualization, the nodes of the trees that you will see contain no values. The property of height-balancing depends only upon the shape of the tree, not on the contents of the nodes.

Once you understand the concept of tree height, proceed to balance factors, which depends upon your understanding of height and is necessary for understanding height-balancing. When you are asked to supply the balance factors, all the heights of each subtree is provided to assist you.

Finally, move to height-balanced trees, and balanced trees, which are a special case. You should note that full and complete trees are the most balanced and that every complete tree is a balanced tree. Every balanced tree is a height-balanced-2 tree and so on. As the n in height-balance-n increases the more unbalanced the trees are allowed to be. Notice that when you are asked to determine whether a tree is height-balanced-n or balanced, if it is not you must demonstrate this fact by clicking any node which is out of balance.