Балансировка арифметического дерева выражений с помощью операторов +, - - PullRequest
Новая
       37

Балансировка арифметического дерева выражений с помощью операторов +, -

0 голосов
/ 02 января 2019

Учитывая двоичное дерево арифметических выражений, состоящее только из операторов сложения и вычитания и чисел, как сбалансировать дерево в максимально возможной степени?Задача состоит в том, чтобы сбалансировать дерево без оценки выражения, то есть количество узлов должно оставаться неизменным.

Пример: 

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

Добавление является коммутативным и ассоциативным, что позволяет проводить балансировку.Коммутативность позволяет менять местами дочерние узлы «+».Ассоциативность учитывает вращения.В приведенном выше примере выполненное преобразование можно просмотреть как

  1. Поворот вправо на «+» в корне.
  2. Замена мест «5» и «-».

Я думал о том, чтобы сделать обход по порядку и сначала уравновесить любые поддеревья.Я бы попытался сбалансировать любое поддерево с двумя последовательными узлами «+», попробовав все возможные расположения узлов (их всего 12), чтобы, надеюсь, уменьшить общую высоту дерева.Этот метод должен уменьшить высоту дерева максимум на 1 на любом шаге.Однако я не могу определить, будет ли оно всегда давать дерево минимальной высоты, особенно когда имеется более 2 последовательных узлов '+'.

Другой подход может состоять в том, чтобы прочитать дерево выражений в массив и заменить любое'-' поддерево с переменной.А потом нам DP, чтобы определить лучшие места для скобок.Это должно быть сделано снизу вверх, так что любое поддерево «-» уже сбалансировано, когда оно рассматривается алгоритмом DP.Тем не менее, я волнуюсь, потому что может быть (n + 1)!способы размещения узлов и скобок.Пока я ищу алгоритм O (n).

Это известная проблема и существует ли к ней особый подход?

1 Ответ

0 голосов
/ 03 января 2019

С риском сделать что-то неопределенное, например, «оценить» (хотя это не по моему мнению), я бы сделал следующее:

  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

    Возможно, стоит указать, что корневой узел имеет зеленого потомка с левой стороны, потому что самый первый листовой узел зеленый. Этого достаточно, чтобы продемонстрировать, что приведенный выше алгоритм охватывает все случаи.

...