关于AVL树插入时左右双旋转中w.bfactor=0场景的技术问询

Great question! This is a really subtle edge case, and you’re right to be confused—because in pure insertion operations, this scenario where w.bfactor == 0 actually doesn’t occur. Let me break down why:

First, recall the balance factor definition here: bfactor = height(right subtree) - height(left subtree). When inserting a node into w’s subtree, we add exactly one node, which increases the height of either w’s left or right subtree by 1. This means:

• If we insert into w’s left subtree: w’s left height rises by 1, so its balance factor shifts from its original value (which was -1, 0, or 1, since the tree was balanced before insertion) to either -1, 0, or -2.
• If we insert into w’s right subtree: w’s right height rises by 1, shifting its balance factor to 1, 0, or 2.

The only way w.bfactor becomes 0 after insertion is if:

• w originally had a bfactor of 1 (right subtree taller by 1), and we insert into its left subtree, making both subtrees equal in height.
• OR w originally had a bfactor of -1 (left subtree taller by 1), and we insert into its right subtree.

But here’s the catch: neither of these scenarios will trigger the double rotation in balancefromleft. For balancefromleft to run, z (the root of the imbalance) must end up with a balance factor of -2 (left subtree 2 levels taller than the right).

Let’s walk through the first scenario:

1. Start with a balanced tree where z has a left child y, which has a right child w with bfactor = 1.
2. Insert a node into w’s left subtree. Now w.bfactor = 0.
3. This insertion increases w’s subtree height by 1, making y’s right subtree taller than its left by 1 (y.bfactor = 1).
4. z’s left subtree is now only 1 level taller than its right (z.bfactor = -1)—not 2. So we never enter the balancefromleft function at all.

So even though inserting can set w.bfactor to 0, it never creates the severe imbalance at z that would trigger the double rotation case where this code runs.

So why is this case in the code? It’s almost certainly included to handle delete operations, where subtree heights can decrease. Deletions can create situations where w.bfactor is 0 while requiring a double rotation to rebalance the tree. For insertion, this case is redundant, but it doesn’t break anything—just safely sets the balance factors of z and y to 0 if it ever (unexpectedly) runs.

内容的提问来源于stack exchange，提问作者wangdq