Поиск грамматики атрибутов для красно-черного дерева

У меня есть рекурсивная грамматика с неупорядоченным обходом, подобная этой. T--> L | TNT
Для красно-черного дерева, где T равно Binary tree, L равно Leaf, а N равно Node.

При поиске каждый узел определяется как пара (цвет, значение). Я пытаюсь найти 2 вещи.

  1. Я хочу расширить грамматику, чтобы она стала грамматикой атрибутов, которая проверяет, выполняются ли условия красного/черного дерева или нет. Проблема в том, что я не знаю, как мне добавить в грамматику условия красно-черного?
  2. Нахождение синтезированных и унаследованных признаков грамматики.

red-black-tree binary-tree binary-search-tree context-free-grammar formal-languages
person saeedrobot    schedule 08.01.2016    source источник
comment
Эта грамматика неоднозначна, а грамматика атрибутов обычно не разрешает неоднозначности. Это ваше намерение? Вам, безусловно, нужен синтезированный атрибут глубины черного; если вы разрешите дно как значение, это, вероятно, все.   -  person rici    schedule 09.01.2016
comment
Я много искал, чтобы найти CFG, который сначала распознает двоичное дерево с неупорядоченным обходом, а затем расширяет его до грамматики атрибутов. Проблема в том, что в Интернете нет даже отправной точки, которую я мог бы использовать. Вот почему я использовал эту грамматику   -  person saeedrobot    schedule 09.01.2016

Ответы (1)


arrow_upward
1
arrow_downward

Производство

T → T N T

является (экспоненциально) неоднозначным, поскольку нет указаний на то, следует ли расширять сначала левое или правое T.

Поскольку N включает цвет, мы могли бы просто распространить цвет с помощью синтаксического анализа, если он предоставляет больше информации. (Это эквивалентно синтезу атрибута цвета для каждого T путем копирования атрибута цвета N или черного для листьев.) Это приводит к:

RN → "red" value
BN → "black" value
RT → BT RN BT
BT → L | T BN T
T  → BT | RT

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

На самом деле, нет никакого способа устранить неоднозначность. Даже если каждый N помечен своей глубиной черного, все равно невозможно однозначно построить дерево из упорядоченного хода.

Рассмотрим следующие два дерева:

       B                             B
      / \                           / \
     /   \                         /   \
     R    B                        R    B
    / \                           / \
   /   \                         /   \
   B    B                        B    B
    \                                /
     \                              /
      R                             R

Оба они являются действительными деревьями RB и имеют обход по порядку:

B R R B B B

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

Альтернативной проблемой может быть построение некоторого допустимого красно-черного дерева из упорядоченного обхода бинарного дерева поиска. Существует восходящий алгоритм, который сделает это, не требуя, чтобы узлы были аннотированы их цветом. Кроме того, алгоритм имеет сложность O(1) для каждого добавленного узла.

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

Я почти уверен, что однажды решил эту проблему, но у меня нет под рукой решения, и меня не удивляет, что его нелегко найти в Интернете. Если это то, что вы ищете, я бы посоветовал вам начать с Статья Ральфа Хинце 1999 года о построении красно-черных деревьев.

person rici    schedule 09.01.2016