4

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

例子：

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

加法是可交换的和关联的，并且允许平衡。交换性允许交换连续“+”节点的子节点。关联性允许旋转。在上面的例子中，执行的转换可以被视为

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

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

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

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

4

1 回答 1

3

冒着做一些像“评估”这样模糊的事情的风险（尽管我不这么认为），我会做以下事情：

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

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

  2. 现在通过在叶子顶部构造一个最小深度的二叉树来最小化树的深度，按照叶子的顺序而不考虑之前的树结构：

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

  3. 将颜色转回-节点。简单的变换是没有红色子节点的节点（只需去除颜色）和恰好有一个红色子节点和一个绿色子节点的节点。后面的这些节点变成了-节点；如果红色的孩子在左边，那么孩子们也被颠倒了。

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

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

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

于 2019-01-02T21:49:46.060 回答