5. Дерево (Tree)
5.1 Структура дерева
Дерево — структура данных, эмулирующая древовидную структуру в виде набора связанных узлов.
┌─────┐
| | Корневой узел
└─────┘
/ | \
┌─────┐ ┌─────┐ ┌─────┐
| | | | | | Дочерние узлы
└─────┘ └─────┘ └─────┘
/ | \
┌─────┐ ┌─────┐ ┌─────┐
| | | | | | Дочерние узлы дочерних узлов
└─────┘ └─────┘ └─────┘
Пример — синтаксическое дерево для выражения 2 * sin(3 * z - 7)
┌─────┐
| * |
└─────┘
/ \
┌─────┐ ┌─────┐
| 2 | | sin |
└─────┘ └─────┘
|
┌─────┐
| - |
└─────┘
/ \
┌─────┐ ┌─────┐
| * | | 7 |
└─────┘ └─────┘
/ \
┌─────┐ ┌─────┐
| 3 | | z |
└─────┘ └─────┘
Еще один пример — двоичное дерево поиска. Термин «двоичное» означет, что у каждого из узлов есть не более двух дочерних узлов. «Дерево поиска» означает, что все значения в левом поддереве каждого узла меньше или равны значению этого узла, а все значения в правом поддереве — наоборот — больше.
┌─────┐
| 0 | <- 0 больше -1, но меньше любого из [1, 5, 7, 8, 9]
└─────┘
/ \
┌─────┐ ┌─────┐
| -1 | | 8 | <- 8 больше любого из [1, 5, 7], но меньше 9
└─────┘ └─────┘
/ \
┌─────┐ ┌─────┐
| 5 | | 9 |
└─────┘ └─────┘
/ \
┌─────┐ ┌─────┐
| 1 | | 7 |
└─────┘ └─────┘
Если в таком дереве нам надо найти значение 7, то нам нужно совершить такие действия:
- Зайти в узел 0. Искомое 7 больше 0, значит нужно продолжить итерирование вправо;
- Зайти в узел 8. Искомое 7 меньше 8, значит нужно продолжить итерирование влево;
- Зайти в узел 5. Искомое 7 больше 5, значит нужно продолжить итерирование вправо;
- Зайти в узел 7. Это и есть искомое значение, можно закончить итерирование.
5.2 Операции над деревом
5.2.1 Вычисление высоты дерева (height)
function height(tree) {
// Если дерево пусто, то его высота равна нулю
if (!tree) {
return 0;
}
// Иначе высота равна единице плюс максимальная высота из высот левого и правого поддеревьев
return 1 + Math.max(height(tree.left), height(tree.right));
}
5.2.2 Вычисление размера дерева
function size(tree) {
// Если дерево пусто, то его размер равен нулю
if (!tree) {
return 0;
}
// Иначе размер равен сумме единицы и размеров левого и правого поддеревьев
return 1 + size(tree.left) + size(tree.right);
}
5.3 Обход дерева
Часто возникает задача обхода всех узлов дерева в определенном порядке. Существует два основных способа обхода деревьев:
- Обход в глубину (depth-first) — обход всего поддерева прежде, чем переход к следущему одноуровневому (sibling) поддереву;
- Обход в ширину (breadth-first) — обход всего уровня прежде, чем переход к следущему уровню.
5.3.1 Симметричный обход (in-order traversal)
Симметричный обход — это обход двоичного дерева в глубину, при котором сначала обходится левое поддерево, затем сам текущий узел, а после этого — правое поддерево.
function inOrderTraversal(tree) {
// Если дерево пусто, то нужно остановить обход
if (!tree) {
return;
}
// Обходим сначала левое поддерево
inOrderTraversal(tree.left);
// Выводим значение в текущем узле
console.log(tree.key);
// Затем обходим правое поддерево
inOrderTraversal(tree.right);
}
Например, если у нас есть такое двоичное дерево поиска:
const tree = {
key: 0,
left: {key: -1},
right: {
key: 8,
left: {
key: 5,
left: {key: 1},
right: {key: 7}
},
right: {key: 9}
}
};
То при симметричном обходе мы получим вывод узлов в порядке возрастания.
inOrderTraversal(tree); // -1, 0, 1, 5, 7, 8, 9
5.3.2 Прямой обход (pre-order traversal)
Этот обход отличается от симметричного тем, что обработка значения в текущем узле производится перед обходом левого поддерева. Так же в отличие от симметричного обхода, этот способ определен для всего множества деревьев (не только для двоичных). Главное условие — обработка текущего узла должна произойти раньше обхода поддеревьев.
function preOrderTraversal(tree) {
// Если дерево пусто, то нужно остановить обход
if (!tree) {
return;
}
// Сначала выводим значение в текущем узле
console.log(tree.key);
// Затем обходим левое поддерево
preOrderTraversal(tree.left);
// В конце обходим правое поддерево
preOrderTraversal(tree.right);
}
При прямом обходе того же дерева tree вывод будет таким:
preOrderTraversal(tree); // 0, -1, 8, 5, 1, 7, 9
5.3.3 Обход в обратном порядке (post-order traversal)
Обход в обратном порядке отличается от прямого обхода тем, что обработка узла происходит после обхода левого и правого поддеревьев. Этот способ так же определен на всем множестве деревьев.
function postOrderTraversal(tree) {
// Если дерево пусто, то нужно остановить обход
if (!tree) {
return;
}
// Сначала обходим левое поддерево
postOrderTraversal(tree.left);
// Затем обходим правое поддерево
postOrderTraversal(tree.right);
// В конце выводим значение текущего узла
console.log(tree.key);
}
При обратном обходе дерева tree вывод будет таким:
preOrderTraversal(tree); // -1, 1, 7, 5, 9, 8, 0
5.3.4 Обход дерева по уровням (level traversal)
Обход дерева по уровням — обход в ширину.
В предыдущих случаях (при обходе в глубину) мы неявно использовали некоторую структуру данных для сохранения узлов, в которые нам предстоит зайти в будущем. Эта структура — стек. Каждый раз, когда мы заканчивали работу с текущим узлом, мы возвращались к предыдущему фрейму в стеке вызовов и продолжали обход.
В случае обхода дерева в ширину нам необходимо использовать другую структуру данных — очередь. В этот раз ее использование будет явным.
function levelTraversal(tree) {
// Если дерево пусто, то нужно остановить обход
if (!tree) {
return;
}
// Создаем очередь и добавляем в нее корневой узел
const queue = new ArrayBasedQueue(100);
queue.enqueue(tree);
// Итерируемся до тех пор, пока очередь не пуста
while (!queue.empty()) {
// Достаем узел из очереди
const node = queue.dequeue();
// Выводим значение узла в консоль
console.log(node.key);
// Если у узла есть левое поддерево,
// добавляем его в очередь
if (node.left) {
queue.enqueue(node.left);
}
// То же делаем и с правым поддеревом
if (node.right) {
queue.enqueue(node.right);
}
}
}
При обходе в ширину дерева tree вывод будет таким:
levelTraversal(tree); // 0, -1, 8, 5, 9, 1, 7