Структура данных - важная тема, которую нужно изучить, чтобы повысить точность кодирования и способность анализировать код. Мы продолжим обсуждение структуры данных с другой популярной структуры данных, называемой двоичным деревом поиска.
Что такое двоичное дерево поиска (BST)?
Дерево двоичного поиска - это древовидная структура данных, которая разветвляется от родительского узла к его дочерним узлам. Есть несколько свойств, которые делают двоичное дерево поиска немного отличающимся от других типов деревьев:
- Каждый узел (родительский узел) может иметь не более 2 дочерних узлов.
- Два дочерних узла часто упоминаются как левый дочерний и правый дочерний, где значение левого дочернего элемента всегда меньше, чем у родительского, а правый дочерний элемент всегда больше, чем равно к родителю
- Каждый дочерний элемент также должен быть двоичным деревом поиска.
Типы двоичного дерева поиска
Завершить BST
- Все уровни (кроме, возможно, последнего уровня) максимальное количество дочерних узлов
- Все узлы на последнем уровне отображаются как можно дальше слева
Полный BST
- Все нелистовые узлы (узлы на концах) заполнены левым потомком и правым потомком.
Реализация
Типы обхода
Предзаказ
- Получить рут
- Пройдите налево
- Пройдите вправо
Чтобы
- Пройдите налево
- Получить рут
- Пройдите вправо
Пост-заказ
- Пройдите налево
- Пройдите вправо
- Получить рут
Это бинарное дерево поиска, реализованное на JavaScript!
И последнее, что я хочу упомянуть, это то, что есть много способов оптимизировать двоичное дерево поиска, чтобы оно было более полным, чтобы дерево не стало слишком линейным. Обязательно ознакомьтесь с этими методами.
Всем большое спасибо за прочитанное! Вы также можете проверить другие мои сообщения о JavaScript в моем профиле.
Основы JavaScript:
Переменная: https://medium.com/@timhancodes0281/basics-of-javascript-variable-3eb6f4f0af18
Типы данных: https://medium.com/@timhancodes0281/basics-of-javascript-data-types-385bab24b51
Основы JavaScript
Прототипное наследование: https://medium.com/javascript-in-plain-english/javascript-fundamental-prototypal-inheritance-9153ab434aae
ES6
Оператор Rest / Spread в JavaScript: https://medium.com/javascript-in-plain-english/rest-spread-operator-in-javascript-2da13aa942fb
Шпаргалка по методам массива: https://medium.com/@timhancodes/javascript-array-methods-cheatsheet-633f761ac250
Структура данных
Что такое стек и очередь?: https://medium.com/javascript-in-plain-english/javascript-what-are-stack-and-queue-79df7af5a566
Сортировка слиянием
Алгоритм сортировки слиянием в JavaScript: https://medium.com/javascript-in-plain-english/javascript-merge-sort-3205891ac060
