Алгоритм Рейнгольда-Тилфорда, объясненный с пошаговым руководством

Алгоритм Рейнгольда-Тилфорда

Алгоритм для построения узлов дерева с числовыми примерами и кодом на Python

Фото от Sergiu Vălenaș на Unsplash

Введение

Алгоритм Рейнгольда-Тилфорда 1981 года создает визуально приятное представление иерархических данных, располагая узлы в структуре дерева для максимальной читаемости. Другими словами, это алгоритм для получения координат (x, y) каждого узла в дереве.

Согласно статье, имеется несколько эстетических правил, которым должна соответствовать хорошая диаграмма дерева:

1. Узлы на одной глубине должны лежать на прямой линии, а прямые линии, определяющие глубины, должны быть параллельными

2. Левый потомок должен находиться слева от своего родительского узла, а правый потомок – справа (только для бинарных деревьев)

3. Родительский узел должен быть расположен по центру относительно своих потомков

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

Определение координат y узлов просто, в то время как координаты x немного сложнее. В этой статье будет попытка объяснить алгоритм на числовых примерах на немного более сложном дереве, чем в других статьях и статьях, которые я читал, чтобы рассмотреть больше сценариев. Я также представлю дополнительные термины, которые не используются в оригинальной статье, чтобы лучше различать разные термины.

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

Интересный факт: библиотека Python scikit-learn также использует этот алгоритм для построения деревьев решений!

Терминология

Перед определением конечных координат каждого узла важны 3 термина. В оригинальной статье упоминаются термины x и mod, но в моем объяснении я буду использовать дополнительный термин shift