Дополнительные ветви добавляются в дерево при генерации

Question

Я реализовал алгоритм синтаксического анализа CYK, который использует подход "снизу вверх" для построения дерева разбора. При прохождении алгоритма путь к окончательному решению сохраняется в обратных указателях. Из обратных указателей мы строим дерево. Этот последний шаг - вот с чем у меня проблемы.

Это структура данных, которую я использую для хранения дерева:

class GrammarTree(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insertLeft(self, new_node):
        self.left = GrammarTree(new_node)

    def insertRight(self, new_node):
        self.right = GrammarTree(new_node)

Вот как я строю дерево, где back хранит кортеж где split индекс используется для разделения дерева и left_rule а также right_rule являются правилами для соответствующего дерева, представленного int. Если достигнут конечный узел, кортежа нет, просто int, представляющий правило терминала.

def build_tree(start,end,idx,back):
    tree = GrammarTree(idx)
    node = back[start][end][idx]
    if isinstance(node,tuple):
        split,left_rule,right_rule = node
        tree.insertLeft(build_tree(start,split,left_rule,back))
        tree.insertRight(build_tree(split,end,right_rule,back))
        return tree
    else:
        tree.insertLeft(GrammarTree(node))
        return tree 

Проблема в том, что когда функция завершает построение дерева, добавляются дополнительные ветви, то есть узлы неправильно склеиваются.

Вот как это выглядит:

Lvl0                                root
                          /                            \
Lvl1                     L1                             R1
                  /       |    \             /           |       \
                 /        |     \           /            |        \
                /         |      \         /             |         \
               /          |       \       /              |          \
              /           |        \     /               |           \
Lvl2  L1.left=None L1.right=None L1.data R1.left=None R1.right=None R1.data
                                  /    \                            /    \
Lvl3                             L2     R2                         L3     R3

Там не должно быть data узел между деревьями.

Редактировать:

Проблема не в том, что существует дополнительный узел данных (приведенное выше утверждение неверно), а в том, что после Lvl1 вместо новых веток добавляются L1.left/right а также R1.left/right на Lvl2 они добавляются в L1 а также R1'sdata поля. Так L1/R1.data в конечном итоге дерево само по себе и L1.left/right а также R1.left/right не используются и, следовательно, None,

Это должно выглядеть так:

                  root
           /               \
          /                 \
   L1=root.left         R1=root.right
     /    \                 /   \
    /      \               /     \
   /        \             /       \
L2=L1.left  R2=L1.right L3=R1.left R3=R1.right

Вот где я называю дерево сборки:

back = [[[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (1, 6, 7), 0, 3, 0, (1, 7, 7)], [0, 0, 0, (1, 6, 7), 0, (1, 7, 3), 0, (1, 7, 7)], [0, 0, 0, (1, 6, 7), 0, (2, 7, 3), 0, (1, 7, 7)]],\ 
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (2, 6, 7), 0, (2, 7, 3), 0, (2, 7, 7)], [0, 0, 0, (2, 6, 7), 0, (2, 7, 3), 0, (3, 7, 7)]],\
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2], [0, 0, 0, (3, 6, 7), 0, 3, 0, (3, 7, 7)]],\
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 6, 0, 3, 0, 2]],\
        [[0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0, 0, 0]]]
build_tree(0,4,5,back)

Answer 1

Проблема была в insertLeft() а также insertRight() методы GrammarTree учебный класс. Вместо того, чтобы просто соединить ветви, вы увидите, что я звонил GrammarTree конструктор, поэтому я, по сути, оборачивал дерево внутри другого дерева.

Я исправил проблему, убрав вызов конструктора.

class GrammarTree(object):
    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

    def insertLeft(self, new_node):
        self.left = new_node  ## <- NOT GrammarTree(new_node) 

    def insertRight(self, new_node):
        self.right = new_node ## <- NOT GrammarTree(new_node)