How to Balance an Imbalanced Syntax Tree?

[lyd123]

The question asks you to balance a syntax tree. The first part is to describe the tree transformations needed to make it a complete tree. I've attached an example of the transformation.

We will know its a compete tree if (heightOfShortestSubTree -heightOfTallestSubTree<=1).

Normal transformations of BSTs which I know of, won't be fully right because those try to keep the order of numbers correct i.e smaller numbers on the left, bigger on the right. But in this question, order of numbers doesn't matter, except if the operator is a minus. If a node has a 'minus', then that sub-tree's structure can't be changed, because subtraction isn't associative or commutative. How would I approach this question? Thank you!

View attachment 8739

 

[I like Serena]

Hi lyd123,

The subtraction itself is indeed neither commutative nor associative.
But the addition above it is.
That is, we need to treat the subtree with the subtraction as a whole, and swap it with the left hand argument of the addition.

Let me show you. We have:
$$(10 + (40-30)) + 20$$
Suppose we temporarily substitute $A$ for $(40-30)$.
Then we get:
$$(10 + A) + 20$$
Now we can balance it with commutativity and associativity of addition:
$$(10 + A) + 20 = (A + 10) + 20 = A + (10 + 20)$$
Therefore:
$$(10 + (40-30)) + 20= (40-30) + (10 + 20)$$

 

[lyd123]

Hi, thank you Klaas, but I am finding it hard to come up with the steps needed that would work for any imbalanced syntax tree. I think all the rotations would be based off the operator in each node, and we have try to keep a node at each level. But how would this would in code e.g for normal BSTs rotation maybe something the left child of node X becomes the left child of the other node at the same level as node X.