Search code examples
data-structuresbinary-treeavl-tree

Different Definitions of Balance Factor

I keep seeing the balance factor of a binary tree defined differently.

My textbook and the Wikipedia AVL Tree page define it as:

Balance Factor(X) = Height ( RightSubtree ( X ) ) − Height ( LeftSubtree ( X ) )

Yet other places define it in exactly the opposite fashion:

Balance Factor(X) = Height ( LeftSubtree ( X ) ) − Height ( RightSubtree ( X ) )

What am I missing?

Solution

  • It actually doesn't matter how you define the balance factor as long as you do so consistently within the same tree. The algorithms for repairing an AVL tree in response to different balance factors are symmetric: the way you fix an imbalance of -2 is the mirror image of the way you fix an imbalance of +2, so there's no real difference between imbalances in the positive versus negative direction. If you were to multiply all the imbalances in the tree by -1, you wouldn't notice anything.

    So in a sense, either definition would be fine. You just need to make sure that you're consistent about it so that you don't try doing rotations that expect one set of balance factors when you're using the other.