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

Question

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

例子:

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

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

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

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

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

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

Answer 1

冒着做一些像“评估”这样含糊不清的事情的风险(尽管我认为这不是)，我会做以下事情:

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

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

2. 现在通过在叶子顶部构建最小深度二叉树来最小化树的深度，在不考虑先前树结构的情况下按顺序获取叶子:

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

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

   棘手的情况是所有子节点都是红色的节点。在这种情况下，向上移动树，直到找到具有绿色后代的父代。您找到的节点必须有两个 child (否则它唯一的 child 必须有一个绿色后代)，其中只有一个 child 有绿色后代。然后，将该节点更改为 -，如果右侧 child 有绿色后代，则反转其 child ，并将(可能是新的)右侧 child 的所有 child 重新着色为绿色。

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

   也许值得指出的是，根节点在左侧有一个绿色后代，因为第一个叶节点是绿色的。这足以证明上述算法涵盖了所有情况。