Двоичное дерево поиска
Описание
Двоичное (или бинарное) дерево поиска (binary search tree, BST) (ДДП), иногда называемое упорядоченным или отсортированным двоичным деревом, - это структура данных для хранения "элементов" (чисел, имен и др.) в памяти. Она позволяет выполнять быстрый поиск, добавление и удаление элементов и может использоваться для реализации динамических множеств элементов или поисковых таблиц, позволяющих искать значения по ключу (например, искать номер телефона по имени человека).
Ключи ДДП являются отсортированными, поэтому поиск и другие операции полагаются на принцип двоичного поиска: при поиске ключа (или места для его добавления) дерево обходится от корня к листьям, ключи, хранящиеся в узлах, сравниваются, и принимается решение о том, в каком поддереве, правом или левом, продолжать поиск. В среднем, это означает, что выполнение операции обходится примерно в два раза дешевле, т.е. поиск, вставка и удаление выполняются за время, пропорциональное логарифму количества элементов, хранящихся в дереве. Это лучше, чем линейное время, необходимое для поиска элемента по ключу в (неупорядоченном) массиве, но хуже, чем соответствующие операции хзш-таблицы (см. часть 2, раздел 5).
ДДП размером 9 и глубиной (высотой) 3 с корнем со значением 8.
Интерактивную визуализации ДДП можно посмотреть здесь.
Сложность
Временная
| Поиск | Вставка | Удаление |
|---|---|---|
O(log n) | O(log n) | O(log n) |
Пространственная
O(n)
Реализация
Начнем с реализации суперкласса узла двоичного дерева:
// data-structures/tree/binary-tree-node.js
import Comparator from '../../utils/comparator'
import HashTable from '../hash-table'
export default class BinaryTreeNode {
constructor(value = null) {
// Значение
this.value = value
// Левый потомок
this.left = null
// Правый потомок
this.right = null
// Предок
this.parent = null
// Дополнительная информация об узле
this.meta = new HashTable()
// Функция сравнения узлов
this.nodeComparator = new Comparator()
}
}
Несколько геттеров для получения высоты (глубины) поддеревьев:
// Геттер высоты (глубины) левого поддерева
get leftHeight() {
if (!this.left) {
return 0
}
return this.left.height + 1
}
// Геттер высоты правого поддерева
get rightHeight() {
if (!this.right) {
return 0
}
return this.right.height + 1
}
// Геттер максимальной высоты
get height() {
return Math.max(this.leftHeight, this.rightHeight)
}
// Геттер разницы между высотой левого и правого поддеревьев
// (фактор балансировки, баланс-фактор)
get balanceFactor() {
return this.leftHeight - this.rightHeight
}
Для определения правильного места для вставки элемента нам также потребуется геттер узла, соседнего с родительским (дяди):
// Геттер дяди
get uncle() {
// Если нет предка, то нет и дяди
if (!this.parent) {
return null
}
// Если нет дедушки, то нет и дяди
if (!this.parent.parent) {
return null
}
// Если у дедушки нет двух потомков, то нет и дяди
if (!this.parent.parent.left || !this.parent.parent.right) {
return null
}
// Выясняем, кто является дядей
// путем сравнения предка с потомком дедушки
if (this.nodeComparator.equal(this.parent, this.parent.parent.left)) {
// Дядя - правый узел
return this.parent.parent.right
}
// Дядя - левый узел
return this.parent.parent.left
}
Методы установки значения, левого и правого потомков:
// Устанавливает значение
setValue(value) {
this.value = value
return this
}
// Устанавливает левого потомок
setLeft(node) {
// Сбрасываем предка левого узла
if (this.left) {
this.left.parent = null
}
// Обновляем левый узел
this.left = node
// Делаем текущий узел предком нового левого узла
if (this.left) {
this.left.parent = this
}
return this
}
// Устанавливает правого потомка
setRight(node) {
// Сбрасываем предка правого узла
if (this.right) {
this.right.parent = null
}
// Обновляем правый узел
this.right = node
// Делаем текущий узел предком нового правого узла
if (this.right) {
this.right.parent = this
}
return this
}
Методы удаления и замены потомка:
// Удаляет потомка
removeChild(nodeToRemove) {
// Если удаляется левый потомок
if (this.left && this.nodeComparator.equal(this.left, nodeToRemove)) {
this.left = null
return true
}
// Если удаляется правый потомок
if (this.right && this.nodeComparator.equal(this.right, nodeToRemove)) {
this.right = null
return true
}
return false
}
// Заменяет потомка
replaceChild(nodeToReplace, replacementNode) {
if (!nodeToReplace || !replacementNode) {
return false
}
// Если заменяется левый потомок
if (this.left && this.nodeComparator.equal(this.left, nodeToReplace)) {
this.left = replacementNode
return true
}
// Если заменяется правый потомок
if (this.right && this.nodeComparator.equal(this.right, nodeToReplace)) {
this.right = replacementNode
return true
}
return false
}
Метод обхода дерева в порядке возрастания ключей (симметричный обход):
// Обходит дерево в порядке возрастания ключей (inorder, infix traverse):
// сначала обходится левое поддерево, затем корень, затем правое поддерево
traverseInOrder() {
let result = []
if (this.left) {
result = result.concat(this.left.traverseInOrder())
}
result.push(this.value)
if (this.right) {
result = result.concat(this.right.traverseInOrder())
}
return result
}
Статический метод копирования узла и метод преобразования дерева в строку:
// Статический метод копирования узла
static copyNode(sourceNode, targetNode) {
targetNode.setValue(sourceNode.value)
targetNode.setLeft(sourceNode.left)
targetNode.setRight(sourceNode.right)
}
// Преобразует дерево в строку
toString() {
return this.traverseInOrder().toString()
}
Полный код узла двоичного дерева
Тесты
Запускаем тесты:
npm run test ./data-structures/tree/__tests__/binary-tree-node.test.js
Приступаем к реализации узла двоичного дерева поиска:
// data-structures/tree/binary-search-tree.js
import BinaryTreeNode from './binary-tree-node'
import Comparator from '../../utils/comparator'
export class BinarySearchTreeNode extends BinaryTreeNode {
constructor(value = null, fn) {
super(value)
this.compareFn = fn
this.nodeValueComparator = new Comparator(fn)
}
}
Метод добавления значения (узла):
// Добавляет значение (узел)
insert(value) {
// Если значение отсутствует
if (this.nodeValueComparator.equal(this.value, null)) {
this.value = value
return this
}
// Если новое значение меньше текущего
if (this.nodeValueComparator.lessThan(value, this.value)) {
// Если имеется левый потомок,
if (this.left) {
// добавляем значение в него
return this.left.insert(value)
}
// Создаем новый узел
const newNode = new BinarySearchTreeNode(value, this.compareFn)
// и делаем его левым потомком
this.setLeft(newNode)
return newNode
}
// Если новое значение больше текущего
if (this.nodeValueComparator.greaterThan(value, this.value)) {
// Если имеется правый потомок,
if (this.right) {
// добавляем значение в него
return this.right.insert(value)
}
// Создаем новый узел
const newNode = new BinarySearchTreeNode(value, this.compareFn)
// и делаем его правым потомком
this.setRight(newNode)
return newNode
}
return this
}
Метод удаления узла по значению:
// Удаляет узел по значению
remove(value) {
// Ищем удаляемый узел
const nodeToRemove = this.find(value)
if (!nodeToRemove) {
return null
}
// Извлекаем предка
const { parent } = nodeToRemove
if (!nodeToRemove.left && !nodeToRemove.right) {
// Узел является листовым, т.е. не имеет потомков
if (parent) {
// У узла есть предок. Просто удаляем указатель на этот узел у предка
parent.removeChild(nodeToRemove)
} else {
// У узла нет предка. Обнуляем значение текущего узла
nodeToRemove.setValue(null)
}
} else if (nodeToRemove.left && nodeToRemove.right) {
// Узел имеет двух потомков.
// Находим следующее большее значение (минимальное значение в правом поддереве)
// и заменяем им значение текущего узла
const nextBiggerNode = nodeToRemove.right.findMin()
if (!this.nodeComparator.equal(nextBiggerNode, nodeToRemove.right)) {
this.remove(nextBiggerNode.value)
nodeToRemove.setValue(nextBiggerNode.value)
} else {
// В случае, когда следующее правое значение является следующим большим значением,
// и этот узел не имеет левого потомка,
// просто заменяем удаляемый узел правым
nodeToRemove.setValue(nodeToRemove.right.value)
nodeToRemove.setRight(nodeToRemove.right.right)
}
} else {
// Узел имеет одного потомка.
// Делаем этого потомка прямым потомком предка текущего узла
const childNode = nodeToRemove.left || nodeToRemove.right
if (parent) {
parent.replaceChild(nodeToRemove, childNode)
} else {
BinaryTreeNode.copyNode(childNode, nodeToRemove)
}
}
// Обнуляем предка удаленного узла
nodeToRemove.parent = null
return true
}
Методы поиска узла по значению и определения наличия узла в дереве:
// Ищет узел по значению
find(value) {
// Проверяем корень
if (this.nodeValueComparator.equal(this.value, value)) {
return this
}
if (this.nodeValueComparator.lessThan(value, this.value) && this.left) {
// Проверяем левое поддерево
return this.left.find(value)
}
if (this.nodeValueComparator.greaterThan(value, this.value) && this.right) {
// Проверяем правое поддерево
return this.right.find(value)
}
return null
}
// Определяет наличие узла
contains(value) {
return Boolean(this.find(value))
}
Вспомогательный метод поиска минимального значения:
// Ищет узел с минимальным значением (нижний левый)
findMin() {
if (!this.left) {
return this
}
return this.left.findMin()
}
Тесты
Запускаем тесты:
npm run test ./data-structures/tree/__tests__/binary-search-tree-node.test.js
Приступаем к реализации двоичного дерева поиска:
// data-structures/tree/binary-search-tree.js
export default class BinarySearchTree {
constructor(compareFn) {
// Корневой узел
this.root = new BinarySearchTreeNode(null, compareFn)
// Функция сравнения узлов
this.nodeComparator = this.root.nodeComparator
}
}
Все необходимые методы дерева нами уже реализованы на уровне узла, остались последние штрихи:
// Добавляет значение (узел)
insert(value) {
return this.root.insert(value)
}
// Удаляет узел по значению
remove(value) {
return this.root.remove(value)
}
// Определяет наличие узла
contains(value) {
return this.root.contains(value)
}
// Возвращает строковое представление дерева
toString() {
return this.root.toString()
}
Полный код узла двоичного дерева поиска и самого дерева
Тесты
Запускаем тесты:
npm run test ./data-structures/tree/__tests__/binary-search-tree.test.js
