Дерево без рекурсии
В этой статье я покажу двоичное дерево без рекурсии. Я думаю что оно в некоторых случаях будет более удобно, нежели дерево с рекурсией.
Итак, начнем. Допустим есть задачка, получить много данных и вывести совпадения. Я нашел одно решение с рекурсией в интернете и понял как это сделать просто. Мне понравилось это решение, но мы знаем что рекурсия заполняет стек и если будет большая вложенность, то будет много выходов из функций. Я захотел попробовать сделать такой алгоритм, который не нуждается в рекурсии. Я буду писать на C, потому что это такой язык, который могут понять все.
Первым делом определим структуру.
Здесь number это число, по которому будет идти сортировка node. Count это количество совпадений. Step нужен будет для вывода совпадений в консоль, он будет определять, было ли вхождение в этот node или нет.
Делаем глобальную ссылку на корень дерева.
Теперь добавляем нашу функцию по вставке чисел, она выглядит немного по другому — например теперь в отличие от рекурсивной функции, она не требует адрес структуры.
static void add_node (const int number) < register struct node *prev = NULL; register unsigned long left = 0; register struct node *p = root; while (1) < if (p == NULL) < p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; if (prev) < if (left) prev->left = p; else prev->right = p; p->parent = prev; > if (root == NULL) < root = p; p->parent = NULL; > return; > prev = p; if (p->number > number) < left = 1; if (p->left && p->number < p->left->number) < register struct node *up = p; register struct node *down = p->left; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->left = down; return; > p = p->left; > else if (p->number < number) < left = 0; if (p->right && p->number > p->right->number) < register struct node *up = p; register struct node *down = p->right; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->right = down; return; > p = p->right; > else if (p->number == number) < p->count++; return; > > > Я указал локальные переменные как регистры, чтобы хоть чуточку быстрее работало. Если посмотреть через дизассемблер, то можно увидеть, что у 64 битного проца хватает регистров.
[0x00401080]> s sym.add_node [0x00401166]> pd 30 ;-- add_node: 0x00401166 55 push rbp 0x00401167 4889e5 mov rbp, rsp 0x0040116a 4155 push r13 0x0040116c 4154 push r12 0x0040116e 53 push rbx 0x0040116f 4883ec18 sub rsp, 0x18 0x00401173 897ddc mov dword [rbp - 0x24], edi 0x00401176 41bc00000000 mov r12d, 0 0x0040117c 41bd00000000 mov r13d, 0 0x00401182 488b1dcf2e00. mov rbx, qword [obj.root] ; [0x404058:8]=0 0x00401189 4885db test rbx, rbx ┌─< 0x0040118c 7559 jne 0x4011e7 Теперь добавление происходит без рекурсии. Далее надо пройтись по дереву и посмотреть есть ли совпадения. Такое тоже возможно не применяя рекурсию. Вот код.
static void find_matches ( ) < register struct node *n = root; register nm = 0; register n->step = 0; while (n) < if (n->step == 0 && n->count > 1) < printf ("%ld: %ld\n", n->number, n->count); nm++; > n->step = 1; if (n->left && n->left->step == 0) < n = n->left; continue; > else if (n->right && n->right->step == 0) < n = n->right; continue; > else if (n->step == 1) < if (n->left) n->left->step = 0; if (n->right) n->right->step = 0; n = n->parent; if (n && n->step == 1 && n->parent == NULL) < n->step == 2; continue; > else if (!n) break; > if (n->step == 1 && n->parent == NULL) break; > >Да, она выглядит больше во много чем рекурсивная функция, но это цена за реализацию поиска в одном цикле. Я использовал step переменную, чтобы определять, где уже указатель был, а где не был.
Теперь посмотрите полный код.
static void add_node (const int number) < register struct node *prev = NULL; register unsigned long left = 0; register struct node *p = root; while (1) < if (p == NULL) < p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; if (prev) < if (left) prev->left = p; else prev->right = p; p->parent = prev; > if (root == NULL) < root = p; p->parent = NULL; > return; > prev = p; if (p->number > number) < left = 1; if (p->left && p->number < p->left->number) < register struct node *up = p; register struct node *down = p->left; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->left = down; return; > p = p->left; > else if (p->number < number) < left = 0; if (p->right && p->number > p->right->number) < register struct node *up = p; register struct node *down = p->right; p = calloc (1, sizeof (struct node)); p->number = number; p->count = 1; p->parent = up; p->right = down; return; > p = p->right; > else if (p->number == number) < p->count++; return; > > > В целом я не видел проблем рекурсивной функции на миллион элементов или 10 миллионов, но возможно, что алгоритм, который я буду использовать, привел в этой статье, возможно будет даже лучше рекурсивной функции. Но для этого надо произвести расчёты, которые я только учусь делать.
Я поменял статью, дерево теперь сбалансированное.
Источник
Нерекурсивные процедуры обхода бинарных деревьев
Учитывая важность эффективной реализации обходов бинарных деревьев, рассмотрим нерекурсивные процедуры обходов. Общий нерекурсивный алгоритм для всех трех порядков обхода использует стек S для хранения упорядоченных пар (p, n), где p узел бинарного дерева, а n номер операции, которую надо применить к p, когда пара (p, n) будет выбрана из стека. Операции «посетить корень», «пройти левое поддерево», «пройти правое поддерево» нумеруются числами 1, 2, 3 в зависимости от порядка их выполнения в данном варианте обхода. В алгоритме эти операции будут реализованы следующим образом:
посетить корень – посетить (p);
пройти левое поддерево if not Null (Left (p)) then S (Left (p), 1);
пройти правое поддерево if not Null (Right (p)) then S (Right (p), 1).
Здесь и далее для краткости и наглядности использованы следующие обозначения операций со стеком: S e вместо S := Push (e, S) и e S вместо Pop2 (e, S).
Тогда общий алгоритм имеет вид:
procedure обход (b: BTree);
var S: Stack of (BTree, operation);
p: BTree; op: operation ;
S := Create; S (b, 1);
while not Null (S) do
begin (p, op) S;
if op = 1 then begin S (p, 2); операция 1 end
else if op = 2 then begin S (p, 3); операция 2 end
else op = 3> операция 3
В случае КЛП-обхода можно существенно упростить алгоритм, исключая лишние для этого варианта манипуляции со стеком. Здесь нет необходимости хранить в стеке номер операции. Итак, конкретизация (с упрощением) общего алгоритма для КЛП-обхода имеет вид:
procedure обход_КЛП (b: BTree);
var S: Stack of BTree; p: BTree;
S:= Create; S b;
while not Null (S) do
p S; посетить (p);
if not Null (Right (p)) then S Right (p);
if not Null (Left (p)) then S Left (p)
В случае ЛКП-обхода также возможно некоторое упрощение в стеке сохраняются указания лишь на операции 1 или 2:
procedure обход_ЛКП (b: BTree);
var S: Stack of (BTree, operation);
p: BTree; op: operation ;
begin S:= Create; S (b , 1);
while not Null (S) do
begin (p, op) S;
if op = 1 then
begin S (p, 2); if not Null (Left (p)) then S (Left (p), 1)
посетить (p); if not Null (Right (p)) then S (Right (p), 1)
Конкретизация общего алгоритма для ЛПК-обхода (здесь нет упрощений) имеет вид:
procedure обход_ЛПК (b: BTree);
var S: Stack of (BTree, operation);
p: BTree; op: operation ;
begin S:= Create; S (b, 1);
while not Null (S) do
if op = 1 then
begin S (p, 2); if not Null (Left (p)) then S (Left (p), 1)
else if op = 2 then
S (p, 3); if not Null (Right (p)) then S (Right (p), 1)
end else op=3 > посетить (p)
Еще один полезный способ обхода бинарного дерева обход в горизонтальном порядке (в ширину). При таком способе узлы бинарного дерева проходятся слева направо, уровень за уровнем от корня вниз (поколение за поколением от старших к младшим). Легко указать нерекурсивную процедуру горизонтального обхода, аналогичную процедуре КЛП-обхода (в глубину), но использующую очередь вместо стека:
procedure обход_горизонтальный (b: BTree);
var Q: queue of BTree;
while not Null (Q) do
if not Null (Left (p)) then Q Left (p);
if not Null (Right (p)) then Q Right (p)
Источник
3.7. Обходы бинарных деревьев и леса
Многие алгоритмы работы с бинарными деревьями основаны на последовательной обработке узлов дерева. Если для линейного списка последовательность обработки элементов очевидна (в однонаправленных списках только в прямом, в двунаправленных — в прямом и обратном направлении), то в бинарном дереве имеется гораздо больше возможностей из-зи наличия ветвления. В связи с этим вводится понятие обхода дерева. При обходе дерева каждый узел посещается только один раз, при этом узлы выстраиваются в определённую линейную последовательность узлов, т.е. можно говорить о предыдущем и следующем узле.
Понятие обхода вводится для любых деревьев, однако удобнее начать с обхода бинарных деревьев ввиду простоты и универсальности.
Наиболее известны и практически важны 3 способа прохождения, которые отличаются порядком и направлением обхода бинарного дерева. К сожалению, в литературе встречается довольно много различных названий для данных обходов, что порождает некоторую путаницу. В таблице 3.4 приведены основные названия (верхняя строка) и алгоритмы рекурсивного прохождения узлов дерева для каждого способа (нижняя строка).
Рекурсивное прохождение бинарного дерева.
Postorder(постфиксный)
3. Пройти правое поддерево
3. Пройти правое поддерево
2. Пройти правое поддерево
Прямой порядок прохождения означает обход в направлении сверху-вниз, когда после посещения очередного разветвления продолжается прохождение вглубь дерева, пока не пройдены все потомки достигнутого узла. По этой причине прямой порядок прохождения часто называют нисходящим, или прохождением в глубину. Прямой порядок используется в представлении дерева в форме вложенных скобок (левое скобочное представление), в виде уступчатого списка или десятичной классификации Дьюи. В геналогических терминах прямой порядок прохождения дерева отражает династический порядок престолонаследования, когда титул передается старшему потомку.
При центрированном (симметричном) проядке дерево проходится слева направо. Такой порядок используется, например, при обходе бинарного дерева поиска, порождая упорядоченную последовательность значений. Подробнее об этом будет рассказано в главах, посвященных сортировке и поиску.
Если применяется концевой порядок прохождения, то получается обход дерева снизу-вверх, когда в момент посещения любого узла все его потомки уже пройдены, а корень дерева проходится последним. Из-за этой особенности обхода, концевой порядок называют восходящим, или обратным относительно прямого.
Иногда используется еще один способ обхода бинарного дерева обход в горизонтальном порядке (в ширину). При таком способе узлы бинарного дерева проходятся слева направо, уровень за уровнем от корня вниз (поколение за поколением от старших к младшим).
Очередность обработки узлов
Источник
Нерекурсивный обход бинарного дерева без стека
Единственное, что смог найти по теме - обход Морриса, но данный алгоритм временно преобразует дерево в "прошитое" дерево, поэтому не подходит.
@VladD: Это не диссертация, я хочу разобраться с упражнением из книги Кормена. По условию константа ограничена глобально.
1 ответ 1
static void Walk(Node node) < Node lastNode = null; while (node != null) < if (lastNode == node.Parent) < if (node.Left != null) < lastNode = node; node = node.Left; continue; >else lastNode = null; > if (lastNode == node.Left) < Output(node); if (node.Right != null) < lastNode = node; node = node.Right; continue; >else lastNode = null; > if (lastNode == node.Right) < lastNode = node; node = node.Parent; >> > Но, строго говоря, в BST ссылки на родителя нет, и обойти его без модификации дерева и с лимитом на память нельзя.
@DarkGenius очень легко. Алгоритим в процессе обхода дерева из N нод может находится в N различных состояниях. т.к. дерево модифицировать нельзя, то для описания состояния требуется дополнительной памяти log2(N) бит. Приведенный выше алгоритм не попадает под требования - он не заработает на количестве нод > 2^32 - т.к. он хранит состояние как int32.
@DarkGenius ну а если расход памяти log2(N) бит приемлем (читерство!), то достаточно просто написать функцию, которая будет идти по дереву, считать ноды (нерекурсивно), и выводить N-ю ноду. И вызвать ее с параметром от 1 до N. Т.е. теоретически лимит будет нарушаться, но на практике - нет (потому что такое дерево просто не влезет в память).
Эээ. Ну то, что указатель 32-битный, это читерство немного. Дерево с к-вом узлов > 2^32 нельзя даже представить в указанном виде, не то что обойти, т. к. на каждый узел должен быть указатель.
Источник