Деревья
Давайте сблизимся с природой, посадим дерево и соберем с него урожай. Чувствую ваше сердцебиение участилось и рука тянется к
Деревья — одна из наиболее распространенных структур данных в информатике. И это не просто так, деревья позволяют представлять большое количество информации и при этом они очень просты и понятны для человека.
Перед тем как дать формальное описание давайте посмотрим как они выглядят:
Это дерево? В реальном мире деревья растут вверх, вниз у них растут только корни. Все у этих компьютерщиков не так.
ожидание и реальность
Структура
Несмотря на такое досадное не соответствие, сходство у компьютерных деревьев и наших любимых дубов, березок и лип все же есть. Давайте посмотрим из чего состоят информационные деревья:
- Корневой узел
- Узел
- Терминальный узел
- Связь
Корневой узел• это начало нашего дерева, то что у биологического дерева вырастает из земли. Корневой узел не может быть потомком другого узла.
Узел• это потомок корневого узла. В отличии от корневого узла он может иметь узел-родитель. Если провести аналогию с настоящим деревом то узел и его потомки это ветка.
Терминальный узел• - конечный узел нашего дерева. Он может иметь родителя, но не может иметь потомков. Он как лист у настоящего дерева.
Все наши узлы могут иметь связи. С помощью них родители знают о своих потомкам, а потомки о родителям. Заметим что терминальный узел и корневой узел это частные случаи более общей сущности узел на которую наложены ограничения по связям.
Вообще деревья это частный случай того, что математики называют графом. Компьютерное дерево это связный граф не содержащий циклов.
Представление данных
Деревья позволяют представлять данные имеющие иерархию. Приведем пример структуры каталогов, представленной в виде дерева:
Как мы видим в корне у нас находится каталог с именем / который содержит каталоги дир1 и дир2, дир1 в свою очередь содержит дир3.
Мне кажется для любого человека это выглядит натурально и понятно. Возможно потому что люди много вещей представляют в подобной структуре: от семьи до вселенной.
Давайте приведем еще более интересный пример. Знаете ли вы что любую конечную и последовательную игру (конечное число ходов, игроки ходят последовательно) можно представить в виде дерева? Шахматы, шашки, крестики-нолики: все они имеют конечное число ходов и комбинаций, вопрос только какое это число. Клод Шеннон в 1950 году вычислил количество возможных не повторяющихся шахматных партий — 10120. Этой особенностью пользуются компьютерные программы которые успешно могут противостоять лучшим игрокам — людям.
У нас нет таких вычислительных мощностей чтобы посчитать все дерево шахмат, поэтому давайте построим игровое дерево для вот этой незаконченной партии в крестики-нолики, ходит крестик:
Данная партия складывается не в пользу нолика, только в одном узле данного дерева он выигрывает. Построить такое дерево очень просто:
- Берем данную доску и поочередно ставим в каждую пустую клетку знак текущего игрока. Получившийся массив досок это потомки исходной доски.
- Если при установке знака произошел выигрыш текущего игрока, или ничья, тогда у этой доски не может быть потомков.
- Для каждого потомка данной доски, в котором нету выигрыша или ничьи, делаем то что описано в пункте 1.
Реализация на Яваскрипте
В замечательном языке программирования для не программистов Яваскрипт нету встроенной структуры данных дерево. Но к счастью деревья не только просты и натуральны для людей, они отлично подходят для представления и обработки данных в компьютере. Если в вашем любимом языке программирования есть массивы вы с легкостью можете представить любое дерево.
Давайте посмотрим на наше дерево каталогов, которое мы представили ранее. Для простоты откинем родительскую связь, тогда у нас остаются узлы, которые содержат данные и могут иметь потомков.
Данные это имя каталога, у нас это: /, дир1, дир2, дир3. Это можно представить в виде строки:
"/" "дир1" "дир2" "дир3"
Еще у нас должно быть место для связи, но сначала давайте рассмотрим эту связь отдельно. Каталог дир3 не содержит потомков, следовательно это должно быть представлено в виде каких то пустых данных. Каталог дир1 содержит каталог дир3, а каталог / содержит каталоги дир1 и дир2. Это тип данных с неопределенной длинной, ага, это же массив.
И все это, данные и связи, должны быть представлены в виде одного элемента. Комбинировать данные нам поможет массив, представим каталог дир3:
["дир3",[]]
Первый элемент массива это наши данные, второй это собственно связи. Поскольку дир3 не имеет связей вторым элементом массива идет пустой массив.
Непонятно и сложно? Яваскрипт спешит на помощь, в нем есть тип данных объект который представляет из себя ассоциативный массив. Давайте представим дир3 используя объект:
{name: "дир3", childs: []}
Стало намного понятнее, а теперь давайте представим всю структуру каталогов:
var dir3 = {name: "дир3", childs: []}
var dir2 = {name: "дир2", childs: []}
var dir1 = {name: "дир1", childs: [dir3]}
var root = {name: "/", childs: [dir1, dir2]}
Тадамс, дерево посадили. Попробуем вывести имя каталога дир3, внука корневого каталога:
console.log(root.childs[0].childs[0].name)
Практика
Небольшая задача для вас. В Студии Лебедева продается набор матрешек «Матрешкус бланко», он состоит из шести матрешек: бит, байт, килобайт, мегабайт, гигабайт, терабайт. Представьте эти матрешки в виде древа, в корневом узле должен находится терабайт, далее его потомок гигабайт и так далее. Решение в комменты.
Дальше — больше
Изначально я готовил пост про решение задачи n-ферзей, но он получился настолько большим что пришлось разбить его на 3 части. В этой части мы рассмотрели одну часть этой проблемы и очень интересную структуру данных — дерево. В следующей части мы посмотрим на рекурсивные функции и научимся с помощью них обрабатывать наши деревья. И наконец, в последней части мы решим проблему n-ферзей. Методы которые мы будет использовать при решении этой проблемы можно применить для решения огромного количества интересных задач. К примеру можно сделать программу для автоматического решения судоку или нарисовать кучу интересных фракталов.
