Удаление дублированных поддеревьев из двоичного дерева

Question

Я должен разработать алгоритм под дополнительную домашнюю работу. Этот алгоритм должен сжимать двоичное дерево, преобразовывая его в DAG, удаляя повторяющиеся поддеревья и перенаправляя все эти соединения в одно левое исходное поддерево. Например, у меня есть дерево (я даю предварительный порядок узлов):

1 2 1 3 2 1 3

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

То, как я это вижу: я передаю предзаказ дерева. Для текущего узла 'w' я запускаю рекурсию, которая должна обнаружить (если она существует) исходное поддерево, равное поддереву с корнем 'w'. Я обрезаю рекурсию, если я нахожу равное поддерево (и я делаю то, что должно быть сделано), или когда я получаю «w» в моем поиске той же рекурсии поддерева. Конечно, я предсказываю некоторые небольшие улучшения, такие как сравнение только поддеревьев с равным количеством узлов.

Если я не ошибаюсь, это дает сложность O (n ^ 2), где n - количество узлов данного двоичного дерева. Есть ли шанс сделать это быстрее (я думаю, что это так). Возможен ли линейный алгоритм?

---

Жаль, что мой алгоритм, наконец, имеет сложность O (n ^ 3). Ваши ответы с хешированием, вероятно, будут очень полезны для меня через некоторое время, когда я узнаю намного больше .. Пока это слишком сложно для меня ..

Последний вопрос. Есть ли шанс сделать это в O (n ^ 2), используя элементарные методы (не хэширование)?

Answer 1

Это происходит при построении oBDD.Идея такова: поместить дерево в каноническую форму и создать хеш-таблицу с записью для каждого узла.Хеш-функция - это функция узла + хеш-функции для левого / правого дочерних узлов.Сложность равна O (N), но только если можно полагаться на уникальность хеш-значений.Окончательное сравнение (например, для разрешения коллизий) все равно будет стоить o (N * N) для рекурсивного сравнения поддерева <-> поддерева. Подробнее о дисках BDD или оригинальная бумага Bryant

Используемая в настоящее время хэш-функция:

#define SHUFFLE(x,n) (((x) << (n))|((x) >>(32-(n))))
/* a node's hashvalue is based on its value
 * and (recursively) on it's children's hashvalues.
 */
#define NODE_HASH2(l,r) ((SHUFFLE((l),5)^SHUFFLE((r),9)))
#define NODE_HASH3(v,l,r) ((0x54321u*(v) ^ NODE_HASH2((l),(r))))

Типичное использование:

void node_sethash(NodeNum num)
{
if (NODE_IS_NULL(num)) return;

if (NODE_IS_TERMINAL(num)) switch (nodes[num].var) {
        case 0: nodes[num].hash.hash= HASH_FALSE; break;
        case 1: nodes[num].hash.hash= HASH_TRUE; break;
        case 2: nodes[num].hash.hash= HASH_FALSE^HASH_TRUE; break;
        }
else if (NODE_IS_NAMED(num)) {
        NodeNum f,t;
        f = nodes[num].negative;
        t = nodes[num].positive;
        nodes[num].hash.hash = NODE_HASH3 (nodes[num].var, nodes[f].hash.hash, nodes[t].hash.hash);
        }
return ;
}

Поиск в хеш-таблице:

NodeNum *hash_hnd(NodeNum num, int want_exact)
{
unsigned slot;
NodeNum *ptr, this;
if (NODE_IS_NULL(num)) return NULL;

slot = nodes[num].hash.hash % COUNTOF(hash_nodes);

for (ptr = &hash_nodes[slot]; !NODE_IS_NULL(this= *ptr); ptr = &nodes[this].hash.link) {
        if (this == num) break;
        if (want_exact) continue;
        if (nodes[this].hash.hash != nodes[num].hash.hash) continue;
        if (nodes[this].var != nodes[num].var) continue;
        if (node_compare( nodes[this].negative , nodes[num].negative)) continue;
        if (node_compare( nodes[this].positive , nodes[num].positive)) continue;
                /* duplicate node := same var+same children */
        break;
        }
return ptr;
}

Функция рекурсивного сравнения:

int node_compare(NodeNum one, NodeNum two)
{
int rc;

if (one == two) return 0;

if (NODE_IS_NULL(one) && NODE_IS_NULL(two)) return 0;
if (NODE_IS_NULL(one) && !NODE_IS_NULL(two)) return -1;
if (!NODE_IS_NULL(one) && NODE_IS_NULL(two)) return 1;

if (NODE_IS_TERMINAL(one) && !NODE_IS_TERMINAL(two)) return -1;
if (!NODE_IS_TERMINAL(one) && NODE_IS_TERMINAL(two)) return 1;

if (VAR_RANK(nodes[one].var)  < VAR_RANK(nodes[two].var) ) return -1;
if (VAR_RANK(nodes[one].var)  > VAR_RANK(nodes[two].var) ) return 1;


rc = node_compare(nodes[one].negative,nodes[two].negative);
if (rc) return rc;
rc = node_compare(nodes[one].positive,nodes[two].positive);
if (rc) return rc;

return 0;
}

Answer 2

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

Подход заключается в следующем (и его легко обобщить на более чем 2 дочерних узла):

Алгоритм (Предполагается изменяемая древовидная структура; Вы можете легко построить новое дерево по пути):

MakeDAG(tree):

    HASH = a new hash-table-based dictionary

    foreach subtree NODE in the tree // traverse this however you like

        if NODE is in HASH
            replace NODE with HASH[NODE]
        else
            HASH[NODE] = N // insert the current node, N, in the dictionary

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

Простое наивное вычисление этих хеш-кодов увеличит время выполнения до O (n ^ 2).

Очень важно сохранить результаты на пути вниз по дереву, чтобы избежать повторных рекурсивных вызовов.и улучшить время выполнения до O (n).

Answer 3

Я бы пошел с подходом хэширования.

Хеш для листа это его значение mod P_1.Хеш для узла равен (value+hash(left_son)*P_2+hash(right_son)*P_2^2) mod P_1, где P_1, P_2 - простые числа.Если вы посчитаете эти хэши как минимум для 5 разных больших простых пар (под большим я имею в виду что-то около 10 ^ 8-10 ^ 9, чтобы вы могли выполнять математику без переполнения), вы можете смело предположить, что узлы с одинаковыми хешами одинаковы.

Тогда вы можете сначала пройтись по дереву, проверить сыновей и выполнить свое преобразование.Это будет работать за O (n) раз.

ПРИМЕЧАНИЕ , что вы можете использовать другие хэш-функции, такие как (value + hash(left_son)*P_2 + hash(right_son)*P_3) mod P_1 и т. Д.