Учебник по JavaScript, структура данных «дерево»
Начало: Учебник по JavaScript: структуры данных.
В википедии по поводу структуры данных «дерево» есть, как минимум, три статьи:
https://ru.wikipedia.org/wiki/Древовидная_структура
https://ru.wikipedia.org/wiki/Дерево_(структура_данных)
https://ru.wikipedia.org/wiki/Дерево_(теория_графов)
Древовидная структура - один из способов представления в графическом виде иерархии в данных. Структуру данных «дерево» в абстракции удобно представлять так называемым «графом», то есть набором вершин (или узлов; их обычно изображают на иллюстрациях кружочками), соединенных рёбрами-линиями (синонимы: связи, ссылки, переходы, дуги). Вообще, «граф» - это математический термин из теории графов (раздел дискретной математики).
Чтобы набор узлов и связей (граф) можно было назвать деревом, этот набор должен удовлетворять нескольким условиям. Во-первых, граф должен быть связным (еще говорят «связанным»), то есть из одного узла графа должен быть путь по связям и узлам до любого другого узла. Во-вторых, граф должен быть ацикличным (не содержать циклов), еще говорят «ациклическим». Цикл - это замкнутый путь по связям и узлам; «замкнутый» означает, что путь начинается и заканчивается в одной и той же вершине. На следующей иллюстрации цикл можно увидеть на среднем варианте графа из трех (ребра цикла окрашены красным цветом).
Из трех вариантов графа, показанных на этой иллюстрации, деревом может называться только третий вариант, то есть связный ацикличный граф.
У дерева такие свойства: 1) число ребер в дереве всегда на единицу меньше числа вершин (это видно на иллюстрации выше); 2) между любыми парами вершин имеется один и только один путь.
Рассмотренные выше графы еще называют неориентированными графами (сокращенно «неорграфами») из-за того, что их ребра не имеют направления. Если ребрам графа присвоены направления, то такой граф называют ориентированным (сокращенно «орграфом»). В соответствии с этим и деревья бывают ориентированными и неориентированными.
В случае ориентированного дерева узел, в который нет входящего ребра, называют корнем дерева, а узлы, из которых нет выходящих ребер, называют листьями (концевыми узлами) дерева. Отсюда становится понятно, почему такую структуру называют деревом - она похожа на настоящее дерево, только перевернутое, потому что корень дерева как графического представления иерархии в данных на иллюстрациях обычно изображают сверху, листья дерева - снизу.
В случае неориентированного дерева корнем дерева, по идее, можно назначить любой узел, а концевыми узлами будут те узлы, которые соединяются с деревом лишь одним ребром.
Зачем в дереве нужно обозначать какой-то узел корнем, а какие-то узлы концевыми? Эти обозначения пригодятся при обработке дерева. Например, по идее, любая работа с деревом должна начинаться с корневого узла, потому что надо же с чего-то начинать алгоритм обработки.
В ориентированном дереве у узла может быть только одно входящее ребро (у корневого узла входящее ребро на иллюстрациях зачастую не изображают, хотя в программе у нас, по идее, всё равно должна быть ссылка на этот узел, представляющая дерево; эту ссылку можно хранить в переменной tree (что по-русски значит «дерево»)), а выходящих ребер может вообще не быть (концевой узел), может быть только одно, или может быть несколько.
Таким образом, у конкретного узла дерева может быть один родительский узел и от нуля до нескольких дочерних узлов (потомков). Также здесь можно говорить о «глубине» дерева (чем дальше от корневого узла, тем глубже) и об уровнях иерархии (узлы, находящиеся на одной и той же глубине, находятся на одном уровне иерархии).
Еще стоит отметить, что существуют так называемые бинарные (двоичные) деревья. В случае неориентированных деревьев это такие деревья, в которых у каждого узла не более трех ребер. В случае ориентированных деревьев это такие деревья, в которых у каждого узла одно входящее ребро (это и так понятно, уже было отмечено выше) и не более двух выходящих ребер (отсюда и название - «бинарные» или «двоичные» деревья). Почему такие деревья выделяют? Потому что если описать какой-либо алгоритм для бинарного дерева, то расширение этого алгоритма для деревьев с большим количеством выходящих ребер считается элементарной задачей. Поэтому многие алгоритмы обработки деревьев в различных пособиях и справочниках пишут только для бинарных деревьев.
В программе на языке JavaScript узел дерева реализуется примерно так же, как и узел линейного односвязного списка из прошлого поста, только ссылок из узла на следующий узел может быть несколько.
На этой иллюстрации показано, что узел дерева при реализации в программе состоит из нескольких частей: «д» - данные, «с» - ссылка. Причем ссылок в узле хранится столько, сколько у узла существует дочерних узлов. В левой части иллюстрации показан исходный граф (дерево); числа, которые вписаны в узлы, будем считать данными, хранящимися в этих узлах.
На языке JavaScript это можно реализовать, например, так:
let tree = {
data: 1,
ref1: {
data: 2,
ref1: { data: 3 },
ref2: { data: 4 }
},
ref2: {
data: 5,
ref1: { data: 6 },
ref2: {
data: 7,
ref1: { data: 9 },
ref2: { data: 10 }
},
ref3: { data: 8 }
}
};
В обсуждаемом учебнике по JavaScript о деревьях мельком упомянуто в подразделе 6.1 «Рекурсия и стек», приведен пример хранения структуры персонала компании в виде дерева. Там, кстати, показано, как ссылки можно хранить не в отдельных свойствах объекта, а в одном свойстве объекта с помощью массива. Это может упростить обработку дерева. К примеру, можно выполнить вышеприведенную реализацию дерева следующим образом:
let tree = {
data: 1,
refs: [{
data: 2,
refs: [{ data: 3 }, { data: 4 }]
}, {
data: 5,
refs: [{ data: 6 }, {
data: 7,
refs: [{ data: 9 }, { data: 10 }]
}, { data: 8 }]
}]
};
А еще можно реализовать каждый узел дерева с помощью одного свойства объекта. При этом название свойства будет хранить данные, а значение свойства - будет являться ссылкой на следующий узел. Такая реализация продемонстрирована в задаче «Создайте дерево из объекта» к подразделу 1.7 «Изменение документа» второй части учебника. Переделаем нашу реализацию дерева этим способом:
let tree = {
"Один": {
"Два": {
"Три": {},
"Четыре": {}
},
"Пять": {
"Шесть": {},
"Семь": {
"Девять": {},
"Десять": {}
},
"Восемь": {}
}
}
};
Здесь у листьев дерева отсутствие ссылки на дочерние узлы обозначено пустым объектом.
С хранением данных в названиях свойств есть проблема, если нужно хранить целые числа. Конечно, в названия свойств можно вписать целые числа (они будут преобразованы в строку), это не станет ошибкой. Однако, если обычно свойства объектов автоматически сортируются в порядке создания, то в случае свойств с целочисленными названиями эти свойства автоматически сортируются по возрастанию. Об этом можно прочесть в подразделе 4.1 «Объекты» первой части учебника. Такое поведение свойств с целочисленными названиями может нарушить сохраненную в дереве структуру данных, то есть некоторые ветви дерева могут поменяться местами.
В нашем примере, конечно, такого не произойдет, потому что я специально выбрал для хранения числа, идущие в структуре данных по возрастанию. Но если в узлах дерева понадобится хранить любые целые числа, указанная выше проблема может проявиться. В случае же хранения в названиях свойств строк этой проблемы не будет.
В википедии по поводу структуры данных «дерево» есть, как минимум, три статьи:
https://ru.wikipedia.org/wiki/Древовидная_структура
https://ru.wikipedia.org/wiki/Дерево_(структура_данных)
https://ru.wikipedia.org/wiki/Дерево_(теория_графов)
Древовидная структура - один из способов представления в графическом виде иерархии в данных. Структуру данных «дерево» в абстракции удобно представлять так называемым «графом», то есть набором вершин (или узлов; их обычно изображают на иллюстрациях кружочками), соединенных рёбрами-линиями (синонимы: связи, ссылки, переходы, дуги). Вообще, «граф» - это математический термин из теории графов (раздел дискретной математики).
Чтобы набор узлов и связей (граф) можно было назвать деревом, этот набор должен удовлетворять нескольким условиям. Во-первых, граф должен быть связным (еще говорят «связанным»), то есть из одного узла графа должен быть путь по связям и узлам до любого другого узла. Во-вторых, граф должен быть ацикличным (не содержать циклов), еще говорят «ациклическим». Цикл - это замкнутый путь по связям и узлам; «замкнутый» означает, что путь начинается и заканчивается в одной и той же вершине. На следующей иллюстрации цикл можно увидеть на среднем варианте графа из трех (ребра цикла окрашены красным цветом).
Из трех вариантов графа, показанных на этой иллюстрации, деревом может называться только третий вариант, то есть связный ацикличный граф.
У дерева такие свойства: 1) число ребер в дереве всегда на единицу меньше числа вершин (это видно на иллюстрации выше); 2) между любыми парами вершин имеется один и только один путь.
Рассмотренные выше графы еще называют неориентированными графами (сокращенно «неорграфами») из-за того, что их ребра не имеют направления. Если ребрам графа присвоены направления, то такой граф называют ориентированным (сокращенно «орграфом»). В соответствии с этим и деревья бывают ориентированными и неориентированными.
В случае ориентированного дерева узел, в который нет входящего ребра, называют корнем дерева, а узлы, из которых нет выходящих ребер, называют листьями (концевыми узлами) дерева. Отсюда становится понятно, почему такую структуру называют деревом - она похожа на настоящее дерево, только перевернутое, потому что корень дерева как графического представления иерархии в данных на иллюстрациях обычно изображают сверху, листья дерева - снизу.
В случае неориентированного дерева корнем дерева, по идее, можно назначить любой узел, а концевыми узлами будут те узлы, которые соединяются с деревом лишь одним ребром.
Зачем в дереве нужно обозначать какой-то узел корнем, а какие-то узлы концевыми? Эти обозначения пригодятся при обработке дерева. Например, по идее, любая работа с деревом должна начинаться с корневого узла, потому что надо же с чего-то начинать алгоритм обработки.
В ориентированном дереве у узла может быть только одно входящее ребро (у корневого узла входящее ребро на иллюстрациях зачастую не изображают, хотя в программе у нас, по идее, всё равно должна быть ссылка на этот узел, представляющая дерево; эту ссылку можно хранить в переменной tree (что по-русски значит «дерево»)), а выходящих ребер может вообще не быть (концевой узел), может быть только одно, или может быть несколько.
Таким образом, у конкретного узла дерева может быть один родительский узел и от нуля до нескольких дочерних узлов (потомков). Также здесь можно говорить о «глубине» дерева (чем дальше от корневого узла, тем глубже) и об уровнях иерархии (узлы, находящиеся на одной и той же глубине, находятся на одном уровне иерархии).
Еще стоит отметить, что существуют так называемые бинарные (двоичные) деревья. В случае неориентированных деревьев это такие деревья, в которых у каждого узла не более трех ребер. В случае ориентированных деревьев это такие деревья, в которых у каждого узла одно входящее ребро (это и так понятно, уже было отмечено выше) и не более двух выходящих ребер (отсюда и название - «бинарные» или «двоичные» деревья). Почему такие деревья выделяют? Потому что если описать какой-либо алгоритм для бинарного дерева, то расширение этого алгоритма для деревьев с большим количеством выходящих ребер считается элементарной задачей. Поэтому многие алгоритмы обработки деревьев в различных пособиях и справочниках пишут только для бинарных деревьев.
В программе на языке JavaScript узел дерева реализуется примерно так же, как и узел линейного односвязного списка из прошлого поста, только ссылок из узла на следующий узел может быть несколько.
На этой иллюстрации показано, что узел дерева при реализации в программе состоит из нескольких частей: «д» - данные, «с» - ссылка. Причем ссылок в узле хранится столько, сколько у узла существует дочерних узлов. В левой части иллюстрации показан исходный граф (дерево); числа, которые вписаны в узлы, будем считать данными, хранящимися в этих узлах.
На языке JavaScript это можно реализовать, например, так:
let tree = {
data: 1,
ref1: {
data: 2,
ref1: { data: 3 },
ref2: { data: 4 }
},
ref2: {
data: 5,
ref1: { data: 6 },
ref2: {
data: 7,
ref1: { data: 9 },
ref2: { data: 10 }
},
ref3: { data: 8 }
}
};
В обсуждаемом учебнике по JavaScript о деревьях мельком упомянуто в подразделе 6.1 «Рекурсия и стек», приведен пример хранения структуры персонала компании в виде дерева. Там, кстати, показано, как ссылки можно хранить не в отдельных свойствах объекта, а в одном свойстве объекта с помощью массива. Это может упростить обработку дерева. К примеру, можно выполнить вышеприведенную реализацию дерева следующим образом:
let tree = {
data: 1,
refs: [{
data: 2,
refs: [{ data: 3 }, { data: 4 }]
}, {
data: 5,
refs: [{ data: 6 }, {
data: 7,
refs: [{ data: 9 }, { data: 10 }]
}, { data: 8 }]
}]
};
А еще можно реализовать каждый узел дерева с помощью одного свойства объекта. При этом название свойства будет хранить данные, а значение свойства - будет являться ссылкой на следующий узел. Такая реализация продемонстрирована в задаче «Создайте дерево из объекта» к подразделу 1.7 «Изменение документа» второй части учебника. Переделаем нашу реализацию дерева этим способом:
let tree = {
"Один": {
"Два": {
"Три": {},
"Четыре": {}
},
"Пять": {
"Шесть": {},
"Семь": {
"Девять": {},
"Десять": {}
},
"Восемь": {}
}
}
};
Здесь у листьев дерева отсутствие ссылки на дочерние узлы обозначено пустым объектом.
С хранением данных в названиях свойств есть проблема, если нужно хранить целые числа. Конечно, в названия свойств можно вписать целые числа (они будут преобразованы в строку), это не станет ошибкой. Однако, если обычно свойства объектов автоматически сортируются в порядке создания, то в случае свойств с целочисленными названиями эти свойства автоматически сортируются по возрастанию. Об этом можно прочесть в подразделе 4.1 «Объекты» первой части учебника. Такое поведение свойств с целочисленными названиями может нарушить сохраненную в дереве структуру данных, то есть некоторые ветви дерева могут поменяться местами.
В нашем примере, конечно, такого не произойдет, потому что я специально выбрал для хранения числа, идущие в структуре данных по возрастанию. Но если в узлах дерева понадобится хранить любые целые числа, указанная выше проблема может проявиться. В случае же хранения в названиях свойств строк этой проблемы не будет.