Interactive Data Structure
VisualizationsHeight-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.