Обход бинарного дерева javascript

Saved searches

Use saved searches to filter your results more quickly

You signed in with another tab or window. Reload to refresh your session. You signed out in another tab or window. Reload to refresh your session. You switched accounts on another tab or window. Reload to refresh your session.

License

corocoto/binary-search-tree

This commit does not belong to any branch on this repository, and may belong to a fork outside of the repository.

Name already in use

A tag already exists with the provided branch name. Many Git commands accept both tag and branch names, so creating this branch may cause unexpected behavior. Are you sure you want to create this branch?

Sign In Required

Please sign in to use Codespaces.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching GitHub Desktop

If nothing happens, download GitHub Desktop and try again.

Launching Xcode

If nothing happens, download Xcode and try again.

Launching Visual Studio Code

Your codespace will open once ready.

There was a problem preparing your codespace, please try again.

Latest commit

Git stats

Files

Failed to load latest commit information.

README.md

Реализация двоичного дерева поиска на JavaScript

Узел в двоичном дереве (или как его еще называют бинарном) имеет не более двух дочерних элементов: левого и правого элемента. Это определение позволяет вам писать алгоритмы для более эффективной вставки, поиска и удаления узлов.

Двоичное дерево поиска (binary search tree — BST) — это тоже двоичное дерево.

Основное отличие состоит в том, что BST позволяет хранить отсортированные узлы с меньшим значением слева и узлы с большим значением справа.

Обход дерева (Traverse) — это процесс посещения всех узлов дерева и выполнения операции на каждом узле.

Существует три общих подхода:

• Прямой (in-order);
• Симметричный или поперечный (pre-order);
• В обратном порядке (post-order).

При прямом обходе будут посещаться все узлы в порядке возрастания, начиная с указанного узла (хотя это и необязательно), и выполнять заданную функцию обратного вызова callback (также необязательно).

При симметричном обходе посещаются каждый узел до его потомков.

При обходе в обратном порядке посещаются узлы после посещения его потомков.

Метод удаления является наиболее сложным. Его сложность обусловлена различными сценариями, которые нам нужны.

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

Удаление крайнего узла (leaf node)

Первый сценарий включает в себя крайний узел (leaf node), то есть у которого нет левого или правого дочернего элемента. В этом случае нам нужно будет удалить узел, присвоив ему значение null . Однако не стоит забывать, что мы также должны позаботиться о ссылках из родительского узла.

Удаление узла с одним потомком

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

Удаление узла с двумя потомками

Третий и последний сценарий включает в себя узел с двумя дочерними элементами. Чтобы удалить такой узел, нужно выполнить следующие действия:

1. Как только вы найдете узел, который нужно удалить, найдите минимальный узел из его правого края поддерева (см. заштрихованную область на диаграмме ниже).
2. Далее вы можете обновить значение узла ключом минимального узла из его правого поддерева. Этим действием вы заменяете ключ узла, что означает, что он будет удален.
3. Теперь у вас есть два узла в дереве с одним и тем же ключом, что не правильно. Таким образом, нужно удалить минимальный узел из правого поддерева, поскольку вы переместили его на место удаленного узла.
4. Наконец, нужно вернуть обновленную ссылку на узел его родителю.

Источник

Дерево

Дерево — структура данных, эмулирующая древовидную структуру в виде набора связанных узлов.

 ┌─────┐ | | Корневой узел └─────┘ / | \ ┌─────┐ ┌─────┐ ┌─────┐ | | | | | | Дочерние узлы └─────┘ └─────┘ └─────┘ / | \ ┌─────┐ ┌─────┐ ┌─────┐ | | | | | | Дочерние узлы дочерних узлов └─────┘ └─────┘ └─────┘ 

Пример — синтаксическое дерево для выражения 2 * sin(3 * z — 7)

 ┌─────┐ | * | └─────┘ / \ ┌─────┐ ┌─────┐ | 2 | | sin | └─────┘ └─────┘ | ┌─────┐ | - | └─────┘ / \ ┌─────┐ ┌─────┐ | * | | 7 | └─────┘ └─────┘ / \ ┌─────┐ ┌─────┐ | 3 | | z | └─────┘ └─────┘ 

Еще один пример — двоичное дерево поиска. Термин «двоичное» означет, что у каждого из узлов есть не более двух дочерних узлов. «Дерево поиска» означает, что все значения в левом поддереве каждого узла меньше или равны значению этого узла, а все значения в правом поддереве — наоборот — больше.

Если в таком дереве нам надо найти значение 7, то нам нужно совершить такие действия:

1. Зайти в узел 0. Искомое 7 больше 0, значит нужно продолжить итерирование вправо;
2. Зайти в узел 8. Искомое 7 меньше 8, значит нужно продолжить итерирование влево;
3. Зайти в узел 5. Искомое 7 больше 5, значит нужно продолжить итерирование вправо;
4. Зайти в узел 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 Обход дерева

Часто возникает задача обхода всех узлов дерева в определенном порядке. Существует два основных способа обхода деревьев:

1. Обход в глубину (depth-first) — обход всего поддерева прежде, чем переход к следущему одноуровневому (sibling) поддереву;
2. Обход в ширину (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: -1>, right: < key: 8, left: < key: 5, left: 1>, right: 7> >, right: 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 

Источник