使用 +、- 运算符平衡算术表达式树

Question

给定一棵仅由加减运算符和数字组成的二叉算术表达式树，如何使树尽可能平衡？任务是在不评估表达式的情况下平衡树，即节点数应保持不变。

示例：

      +                           +
    /   \                      /     \
   +     15      >>>>>>       -       +
 /   \                       / \     / \
5     -                     6   4   5   15
    /   \
   6     4

加法是可交换的和结合的，可以平衡。可交换性允许交换连续“+”节点的子节点。关联性允许旋转。在上面的例子中，执行的转换可以看作是

在根部的“+”上向右旋转。
交换“5”和“-”节点。

我正在考虑进行有序遍历并首先平衡所有子树。我会尝试通过尝试所有可能的节点排列（只有 12 个）来平衡具有两个连续“+”节点的任何子树，以希望降低树的总高度。此方法应在任何步骤中将树的高度最多减少 1。但是，我无法确定它是否总是给出一个最小高度的树，尤其是当有超过 2 个连续的 '+' 节点时。

另一种方法可能是将表达式树读入数组并用变量替换任何“-”子树。然后我们 DP 来确定括号的最佳位置。这必须自下而上完成，以便任何 '-' 子树在 DP 算法考虑时已经平衡。但是，我很担心，因为可能有 (n+1) 个！排列节点和括号的方法。当我在寻找 O(n) 算法时。

这是一个已知问题吗？是否有具体的解决方法？

Answer 1

冒着做一些像 "evaluating" 这样模糊的事情的风险（尽管我认为这不是），我会做以下事情：

通过将否定标记向下传播到根，将整个树更改为附加节点。一种简单的方法是向每个叶节点添加一个 "colour"。节点的颜色可以在树遍历期间直接计算。在行走过程中，您会跟踪来自 - 个节点的 right-hand 链接的数量（或奇偶校验，因为这是我们唯一感兴趣的部分）；当到达一片叶子时，如果奇偶校验是偶数，则它是绿色的，如果是奇数，则它是红色的。（红叶被否定。）在行走过程中，-个节点变为+.
```
      +                          +
    /   \                      /   \
   +    15       >>>>>>       +    15
 /   \                      /   \
5     -                     5    +
    /   \                      /   \
   6     4                    6    -4
```

现在通过在叶子顶部构造一个最小深度二叉树来最小化树的深度，在不考虑之前的树结构的情况下按顺序获取叶子：

      +                            +
    /   \                      /       \
   +    15       >>>>>>       +         +
 /   \                      /   \     /   \
5     +                     5    6   -4   15
    /   \
   6    -4

将颜色转回 - 节点。简单的变换是没有红色 children（只需删除颜色）的节点和只有一个红色 child 和一个绿色 child 的节点。后面的这些节点变成了-个节点；如果红色的child在左边，那么children也是反的

棘手的情况是所有 children 都是红色的节点。在这种情况下，向上移动树，直到找到 parent 有一些绿色后代。您找到的节点必须有两个 children（否则它只有 child 必须有一个绿色后代），其中只有一个 child 有绿色后代。然后，将该节点更改为 -，如果 right-hand child 具有绿色后代，则将其 children 反转，并将所有 children of the (possibly new) right-hand child.
```
        +                          +
    /      \                   /       \
   +        +    >>>>>>       +         -
 /   \     /   \            /   \     /   \
5     6   -4   15          5     6   15    4
```
也许值得指出的是，根节点在 left-hand 一侧有一个绿色后代，因为第一个叶节点是绿色的。这足以证明上述算法涵盖了所有情况。

使用 +、- 运算符平衡算术表达式树

Balancing arithmetic expression tree with +, - operators

algorithm

tree

binary-tree

arithmetic-expressions

tree-balancing