Как вывести таблицу со списком всех потомков для каждого узла древовидной структуры?
Есть таблица с деревом (id, parent) Нужно написать запрос, который вернет для каждого узла все дочерние узлы и дочерние узлы всех дочерних узлов (рекурсивно), а так же столбец с уровнем в дереве текущего узла и столбец с уровнем в дереве дочернего узла. Я написал запрос, но он виснет. Конкретно виснет (выполняется очень долго и я не могу его отменить). При этом ошибки с достижением уровня рекурсии 100 не вылетает. То есть, я так понял, рекурсия не уходит в глубину, но выполнение одной итерации уходит в бесконечность.
WITH Tree(Id,Parent,Level) AS ( SELECT Node_Id ,0 ,0 FROM CatalogOKPD WHERE Node_Parent_Id = 0 UNION ALL SELECT okpd.Node_Id ,okpd.Node_Parent_Id ,t.Level+1 FROM CatalogOKPD okpd JOIN Tree t ON t.Id = okpd.Node_Parent_Id) ,FullTree(Id,Child,Level,ChildLevel) AS ( SELECT t1.Id ,t2.Id ,t1.Level ,t2.Level FROM Tree t1 JOIN Tree t2 ON t1.Id=t2.Parent UNION ALL SELECT ft.Id ,t.Id ,ft.Level ,t.Level FROM Tree t JOIN FullTree ft ON t.Parent = ft.Child ) SELECT * FROM FullTree id parent --- ------- 1 0 2 1 3 1 4 0 5 4 6 4 7 6 8 7 id child level childlevel ----------- ----------- ----------- ----------- 1 2 0 1 1 3 0 1 4 5 0 1 4 6 0 1 4 7 0 2 4 8 0 3 6 7 1 2 6 8 1 3 7 8 2 3 UPD: поправил запрос, проверил на малом количестве данных, все норм. А вот на реальной таблице с 70000 записями запрос выполняется нереально долго. Так что его нужно оптимизировать (или переписать иначе)
Я не понял как по входным данным добраться до записей с id 6, 7, 8 потому как от заданного вами корня (с parent=0) нет никакого пути до них. И не ясно что такое childLevel, обычно уровень дочернего элемента на 1 больше, чем у родителя.
@Mike, вы невнимательно прочитали. «все дочерние узлы и дочерние узлы всех дочерних узлов (рекурсивно)» означает, что для узла с нужно вернуть не только узлы 5 и 6, но и их дочерние узлы и узлы их дочерних узлов, короче все поддерево
2 ответа 2
WITH Nums(N) AS (select 0 union select 1), Tree(id,Child,Level,ChildLevel,old_n) AS ( SELECT Node_Id, Node_Id, 0, 0, 1 FROM CatalogOKPD WHERE Node_Parent_Id = 0 UNION ALL SELECT case when N=0 then t.id else okpd.Node_Id end, okpd.Node_Id, t.Level+N, t.ChildLevel+1, N FROM Tree t, CatalogOKPD okpd, Nums N WHERE t.Child = okpd.Node_Parent_Id and (old_n=1 or N=0) ) select id, Child, Level, ChildLevel from Tree where old_n=0 order by Level, id, ChildLevel Идея в том, что на каждом уровне рекурсии мы раздваиваем пришедшую на вход запись, одна из них идет дальше от того же корня, что пришедшая. А вторая запись становится новым корнем. Раздваиваются только те записи, которые на предыдущем уровне стали корневыми ( old_n=1 ).
UPD Как работает .
Для примера возьмем только одну ветку данных, от записи 4/0:
id=4, child=4, old_n=0, N=1 Затравочная запись выбрана первой частью она поступает на вход рекурсивной части как Tree . Тут по parent=child к ней приклеены 2 записи (5, 6) old_n на входе равен 1 - значит по условию (old_n=1 or N=0) для каждой из них будут взяты 2 записи Nums, что даст 4 записи: id=4, child=5, old_n=0, N=0 В old_n перешел номер 0 из Nums id=5, child=5, old_n=1, N=1 Т.к. N=1 в качестве id был взят child, что дало новый корень (5) id=4, child=6, old_n=0, N=0 id=6, child=6, old_n=1, N=1 тут все аналогично На следующем уровне рекурсии для записи 5 потомков нет, значит она уже ничего не породит. Следим за 6 id=4, child=7, old_n=0, N=0 По условию (old_n=1 or N=0) взята только 1 запись из Nums N=0 child взят из следующей дочерней записи id=6, child=7, old_n=1, N=0 т.к. old_n=1 то берется 2 записи Nums (0,1) у данной N=0, поэтому корень сохранился child=7, old_n=1, N=1 N=1 поэтому корень 6 заменен на 7 И аналогично следующий уровень рекурсии id=4, child=8, old_n=0, N=0 id=6, child=8, old_n=0, N=0 id=7, child=8, old_n=1, N=0 id=8, child=8, old_n=1, N=1 Затравка для следующего уровня, если бы он был Итоговый запрос берет все записи с N=0 из примера выше, он в выборке находится в поле old_n. Записи с N=1 используются только внутри рекурсии для порождения новых ветвей дерева.
Источник
Двоичное дерево поиска
Двоичное дерево поиска. Итеративная реализация.
Д воичные деревья – это структуры данных, состоящие из узлов, которые хранят значение, а также ссылку на свою левую и правую ветвь. Каждая ветвь, в свою очередь, является деревом. Узел, который находится в самой вершине дерева принято называть корнем (root), узлы, находящиеся в самом низу дерева и не имеющие потомков называют листьями (leaves). Ветви узла называют потомками (descendants). По отношению к своим потомкам узел является родителем (parent) или предком (ancestor). Также, развивая аналогию, имеются сестринские узлы (siblings – родные братья или сёстры) – узлы с общим родителем. Аналогично, у узла могут быть дяди (uncle nodes) и дедушки и бабушки ( grandparent nodes). Такие названия помогают понимать различные алгоритмы.
Двоичное дерево. На этом рисунке узел 10 корень, 7 и 12 его наследники. 6, 9, 11, 14 — листья. 7 и 12, также как и 6 и 9 являются сестринскими узлами, 10 — это дедушка узла 6, а 12 — дядя узла 6 и узла 9
Двоичные деревья одна из самых простых структур (по сравнению, например, с другими деревьями). Они обычно реализуют самый базовый и самый естественный способ классификации элементов – делят их по определённому признаку, размещая одну группу в левом поддереве, а другую группу в правом. В поддеревьях рекурсивно поддерживается такой же порядок, за счёт чего узлы дерева упорядочиваются.
Двоичное дерево поиска (далее ДДП) – это несбалансированное двоичное дерево, в котором элементы БОЛЬШЕ корневого размещаются справа, а элементы, которые МЕНЬШЕ размещаются слева.
Такое размещение – слева меньше, справа больше – не обязательно, можно располагать элементы, которые меньше, справа. Отношение БОЛЬШЕ и МЕНЬШЕ – это не обязательно естественная сортировка по величине, это некоторая бинарная операция, которая позволяет разбить элементы на две группы.
Для реализации бинарного дерева поиска будем использовать структуру Node, которая содержит значение, ссылку на правое и левое поддерево, а также ссылку на родителя. Ссылка на родительский узел, в принципе, не является обязательной, однако сильно упрощает и ускоряет все алгоритмы. Далее, ради тренировки, мы ещё рассмотрим реализацию без ссылки на родителя.
ЗАМЕЧАНИЕ: мы рассматриваем случай, когда в дереве все значения разные и не равны NULL. Деревья с повторяющимися узлами рассмотрим позднее.
Обычно в качестве типа данных мы используем void* и далее передаём функции сравнения через указатели. В этот раз будем использовать пользовательский тип и макросы.
typedef int T; #define CMP_EQ(a, b) ((a) == (b)) #define CMP_LT(a, b) ((a) < (b)) #define CMP_GT(a, b) ((a) >(b)) typedef struct Node < T data; struct Node *left; struct Node *right; struct Node *parent; >Node;
Сначала, как обычно, напишем функцию, которая создаёт новый узел. Она принимает в качестве аргументов значение и указатель на своего родителя. Корневой элемент не имеет родителя, значение указателя parent равно NULL.
Node* getFreeNode(T value, Node *parent) < Node* tmp = (Node*) malloc(sizeof(Node)); tmp->left = tmp->right = NULL; tmp->data = value; tmp->parent = parent; return tmp; >
Разберёмся со вставкой. Возможны следующие ситуации
- 1) Дерево пустое. В этом случае новый узел становится корнем ДДП.
- 2) Новое значение меньше корневого. В этом случае значение должно быть вставлено слева. Если слева уже стоит элемент, то повторяем эту же операцию, только в качестве корневого узла рассматриваем левый узел. Если слева нет элемента, то добавляем новый узел.
- 3) Новое значение больше корневого. В этом случае новое значение должно быть вставлено справа. Если справа уже стоит элемент, то повторяем операцию, только в качестве корневого рассматриваем правый узел. Если справа узла нет, то вставляем новый узел.
Пусть нам необходимо поместить в ДДП следующие значения
Первое значение становится корнем.
Второе значение меньше десяти, так что оно помещается слева.
Число 9 меньше 10, так что узел должен располагаться слева, но слева уже стоит значение. 9 больше 7, так что новый узел становится правым потомком семи.
Число 12 помещается справа от 10.
Добавляем оставшиеся узлы 14, 3, 4, 11
Функция, добавляющая узел в дерево
Два узла. Первый – вспомогательная переменная, чтобы уменьшить писанину, второй – тот узел, который будем вставлять.
Node *tmp = NULL; Node *ins = NULL;
Проверяем, если дерево пустое, то вставляем корень
Проходим по дереву и ищем место для вставки
Пока не дошли до пустого узла
Если значение больше, чем значение текущего узла
Если при этом правый узел не пустой, то за корень теперь считаем правую ветвь и начинаем цикл сначала
if (tmp->right) < tmp = tmp->right; continue;
Если правой ветви нет, то вставляем узел справа
> else < tmp->right = getFreeNode(value, tmp); return; >
Также обрабатываем левую ветвь
> else if (CMP_LT(value, tmp->data)) < if (tmp->left) < tmp = tmp->left; continue; > else < tmp->left = getFreeNode(value, tmp); return; > > else < exit(2); >>
void insert(Node **head, int value) < Node *tmp = NULL; Node *ins = NULL; if (*head == NULL) < *head = getFreeNode(value, NULL); return; >tmp = *head; while (tmp) < if (CMP_GT(value, tmp->data)) < if (tmp->right) < tmp = tmp->right; continue; > else < tmp->right = getFreeNode(value, tmp); return; > > else if (CMP_LT(value, tmp->data)) < if (tmp->left) < tmp = tmp->left; continue; > else < tmp->left = getFreeNode(value, tmp); return; > > else < exit(2); >> >
Рассмотрим результат вставки узлов в дерево. Очевидно, что структура дерева будет зависеть от порядка вставки элементов. Иными словами, форма дерева зависит от порядка вставки элементов.
Если элементы не упорядочены и их значения распределены равномерно, то дерево будет достаточно сбалансированным, то есть путь от вершины до всех листьев будет одинаковый. В таком случае максимальное время доступа до листа равно log(n), где n – это число узлов, то есть равно высоте дерева.
Но это только в самом благоприятном случае. Если же элементы упорядочены, то дерево не будет сбалансировано и растянется в одну сторону, как список; тогда время доступа до последнего узла будет порядка n. Это слабая сторона ДДП, из-за чего применение этой структуры ограничено.
Дерево, которое получили вставкой чередующихся возрастающей и убывающей последовательностей (слева) и полученное при вставке упорядоченной последовательности (справа)
Для решения этой проблемы можно производить балансировку дерева, или использовать структуры, которые автоматически проводят самобалансировку во время вставки и удаления.
Поиск в дереве
И звестно, что слева от узла располагается элемент, который меньше чем текущий узел. Из чего следует, что если у узла нет левого наследника, то он является минимумом в дереве. Таким образом, можно найти минимальный элемент дерева
Node* getMinNode(Node *root) < while (root->left) < root = root->left; > return root; >
Аналогично, можно найти максимальный элемент
Node* getMaxNode(Node *root) < while (root->right) < root = root->right; > return root; >
Опять же, если дерево хорошо сбалансировано, то поиск минимума и максимума будет иметь сложность порядка log(n), а в случае плохой балансировки стремится к n.
Поиск нужного узла по значению похож на алгоритм бинарного поиска в отсортированном массиве. Если значения больше узла, то продолжаем поиск в правом поддереве, если меньше, то продолжаем в левом. Если узлов уже нет, то элемент не содержится в дереве.
Node *getNodeByValue(Node *root, T value) < while (root) < if (CMP_GT(root->data, value)) < root = root->left; continue; > else if (CMP_LT(root->data, value)) < root = root->right; continue; > else < return root; >> return NULL; >
Удаление узла
С уществует три возможных ситуации.
- 1) У узла нет наследников (удаляем лист). Тогда он просто удаляется, а его родитель обнуляет указатель на него.
Источник