Бинарное дерево поиска (БДП, Binary Search Tree, BST) — это нелинейная структура данных, в которой данные представляются в виде дерева с узлами, содержащими определенные значения. Каждый узел может иметь максимум двух потомков, при этом один из них располагается в левом поддереве, а второй — в правом. Основное правило этой структуры данных заключается в том, что значения в левом поддереве данного узла должны быть меньше, чем значение этого узла, а в правом — наоборот, больше. Этим свойством обусловлена возможность быстрого поиска, вставки и удаления элементов из БДП.
Бинарное дерево поиска может иметь следующий вид:
8
/ \
3 10
/ \ \
1 6 14
/ \ /
4 7 13
Здесь количество потомков у каждого элемента не превышает двух, также соблюдается правило распределения потомков по левому и правому поддеревьям.
Ниже представлен вариант дерева, который не соответствует правилам, поэтому его назвать бинарным деревом поиска нельзя:
10
/ | \
5 7 15
/ \ / \
4 6 16 17
Основные элементы бинарного дерева поиска
Для лучшего понимания концепции бинарных деревьев стоит изучить основные термины:
- корневой узел/корень (Root) — это первый узел дерева, он не имеет родителя, при этом все остальные узлы являются его потомками;
- узел (Node) — это основная часть дерева, каждый из них содержит данные (значение) и имеет связь с потомками;
- листовой узел (Leaf Node) — это узел, у которого нет потомков: его правое и левое поддерево равно null;
- родительский узел (Parent Node) — это узел, имеющий потомков, а дочерний (Child Node) — который сам является потомком;
- путь (Path) — это последовательность узлов, начиная от корня до заданного узла (в бинарном дереве может быть только один путь от корня до определенного элемента);
- сиблинги (Siblings) — это элементы, которые имеют общего родителя;
- глубина узла (Depth of a Node) — это количество ребер от корня до заданного узла (глубина корня равна 0);
- высота дерева (Height of a Binary Tree) — это максимальное количество узлов от корня до листового узла.
Принцип работы двоичного дерева поиска
БДП имеют два основных правила:
- каждый элемент может иметь максимум двух потомков;
- значения, которые меньше узла, должны располагаться в его левом поддереве, а которые больше — в правом.
Соблюдение этих правил позволяет выполнять операции в БДП быстро (в лучшем случае со скоростью O(log n), где n — количество узлов) и сортировать значения. Также из них можно выделить несколько свойств БДП:
- максимальное количество элементов на уровне l равно 2l;
- максимальное количество элементов в сбалансированном БДП с высотой h равно 2h - 1.
Построение бинарного дерева поиска с нуля
Для того чтобы построить БДП, нужно опираться на правила. Во-первых, ни один элемент не может иметь более двух потомков. Во-вторых, в левом поддереве необходимо располагать все значения меньше значения данного элемента, а в правом — все значения больше него.
Допустим, нужно построить БДП, состоящее из чисел 10, 5, 15, 4, 7, 13 и 17. Тогда построение будет выглядеть так:
- Начать нужно с числа 10, так как оно является корнем.
- Дальше нужно добавить значение 5, оно меньше 10, поэтому добавляется в левое поддерево корня. Значение 15, наоборот, больше 10, поэтому оно добавляется справа. На этом шаге получается такое дерево:
10
/ \
5 15
- Следующее значение — 4, оно меньше 10, поэтому нужно перейти к элементу со значением 5. 4 также меньше 5, поэтому это значение добавляется в левое поддерево. Далее идет значение 7, оно тоже меньше 10, но больше 5, поэтому будет добавлено в правое поддерево:
10
/ \
5 15
/ \
4 7
- Дальше рассматривается значение 13 — оно больше 10, но меньше 15, поэтому будет записано в левое поддерево узла со значением 15. Последнее число 17 больше 10 и больше 15, поэтому его нужно добавить в правое поддерево:
10
/ \
5 15
/ \ / \
4 7 13 17
Таким образом, чтобы добавить элемент, сначала нужно сравнить его с корнем — так определяется, в какое поддерево он будет добавлен. Далее нужно перейти к соответствующему узлу и сравнить значение элемента с ним: если оно меньше значения узла, то элемент добавляется в левое поддерево, а если больше — в правое.
В коде реализация БДП на JavaScript может выглядеть так:
class TreeNode {
constructor(value, parent) {
this.left = null;
this.right = null;
this.parent = parent;
this.value = value;
}
}Основные операции в бинарном дереве поиска
К операциям в бинарном дереве поиска относятся:
- поиск узла. Эта операция основана на сравнении искомого значения с текущим узлом и начинается с корня. Когда значение, которое нужно найти, меньше текущего элемента, оно может быть только в левом поддереве, а в обратной ситуации — только в правом. Операция поиска длится, пока не будет найден нужный элемент, либо пока не станет возможна констатация его отсутствия. Поиск может быть реализован следующим образом:
class TreeNode {
// Конструктор
find(value) {
let currentNode = this;
while (currentNode) {
if (value === currentNode.value) return currentNode;
if (value < currentNode.value) {
currentNode = currentNode.left;
} else {
currentNode = currentNode.right;
}
}
return null;
}
}- вставка узла. Основной инструмент для этой операции — тоже сравнение значений. Если значение нового элемента меньше текущего узла, то он должен быть вставлен в левое поддерево, в обратном случае — в правое. Также при добавлении нового элемента проверяется, пуст ли текущий элемент — в зависимости от этого есть два сценария:
class TreeNode {
// Конструктор
insert(value) {
this.#insertRecursively(value, this);
}
#insertRecursively(value, currentNode) {
if (value < currentNode.value) {
if (currentNode.left === null) {
currentNode.left = new TreeNode(value, currentNode);
} else {
this.#insertRecursively(value, currentNode.left);
}
} else if (value > currentNode.value) {
if (currentNode.right === null) {
currentNode.right = new TreeNode(value, currentNode);
} else {
this.#insertRecursively(value, currentNode.right);
}
}
}
}- удаление узла. Это самая сложная операция, так как ее реализация зависит от наличия и количества потомков элемента. Если потомков нет, то узел можно просто удалить. Если имеется один дочерний узел, то удаляемый элемент можно заменить этим дочерним узлом. При наличии двух потомков необходим поиск преемника — элемента, который заменит удаленный. Это может быть либо минимальный узел из правого поддерева, либо максимальный из левого. Реализация метода удаления узла может выглядеть так:
class TreeNode {
// Конструктор
remove(value) {
return this.#removeNode(value, this);
}
#removeNode(value, currentNode) {
if (currentNode === null) return null;
if (value < currentNode.value) {
currentNode.left = this.#removeNode(value, currentNode.left);
if (currentNode.left !== null) {
currentNode.left.parent = currentNode;
}
} else if (value > currentNode.value) {
currentNode.right = this.#removeNode(value, currentNode.right);
if (currentNode.right !== null) {
currentNode.right.parent = currentNode;
}
} else {
if (currentNode.left === null && currentNode.right === null) {
return null;
}
if (currentNode.right === null) {
currentNode.left.parent = currentNode.parent;
return currentNode.left;
}
if (currentNode.left === null) {
currentNode.right.parent = currentNode.parent;
return currentNode.right;
}
let heir = this.#findMin(currentNode.right);
currentNode.value = heir.value;
currentNode.right = this.#removeNode(heir.value, currentNode.right);
if (currentNode.right !== null) {
currentNode.right.parent = currentNode;
}
}
return currentNode;
}
#findMin(node) {
let current = node;
while (current.left !== null) {
current = current.left;
}
return current;
}
}- обход дерева — это еще одна операция, которая заключается в последовательном посещении всех узлов дерева. Она будет более подробно рассмотрена в следующем разделе.
Алгоритмы обхода бинарного дерева
Для обхода могут использоваться следующие методы:
- прямой обход (Preorder Traversal) — сначала посещается корень, затем левое поддерево, потом правое:
class TreeNode {
// Конструктор
preorderTraversal() {
if (this === null) {
return;
}
console.log(this.value + " ");
if (this.left) {
this.left.preorderTraversal();
}
if (this.right) {
this.right.preorderTraversal();
}
}
}- центрированный обход (Inorder Traversal) — сначала посещается левое поддерево, затем корень, потом правое:
class TreeNode {
// Конструктор
inorderTraversal() {
if (this === null) {
return;
}
if (this.left) {
this.left.inorderTraversal();
}
console.log(this.value);
if (this.right) {
this.right.inorderTraversal();
}
}
}- обратный обход (Postorder Traversal) — сначала посещается левое поддерево, затем правое, потом корень:
class TreeNode {
// Конструктор
postorderTraversal() {
if (this === null) {
return;
}
if (this.left) {
this.left.postorderTraversal();
}
if (this.right) {
this.right.postorderTraversal();
}
console.log(this.value);
}
}- все вышеперечисленные методы относятся к поиску в глубину, но также существует поиск в ширину (Level Order Traversal) — в таком случае посещаются все узлы, находящиеся на одном уровне, затем происходит переход на следующий уровень и так далее:
class TreeNode {
// Конструктор
levelOrderTraversal() {
if (!this) {
return;
}
let queue = [];
queue.push(this);
while (queue.length > 0) {
let node = queue.shift();
console.log(node.value + " ");
if (node.left) {
queue.push(node.left);
}
if (node.right) {
queue.push(node.right);
}
}
}
}Преимущества и недостатки двоичного дерева поиска
Преимущества:
- БДП имеют высокую скорость выполнения операций: их временная сложность в лучшем случае составляет O(log n), где n — количество узлов;
- структура БДП устроена таким образом, что элементы можно посещать в определенном порядке, как это описано в пункте об алгоритмах обхода деревьев. Это свойство позволяет сортировать элементы, например, если использовать центрированный обход, то можно вывести элементы в порядке возрастания;
- БДП просты в понимании и реализации, а также могут использоваться для решения разнообразных задач.
Недостатки:
- БДП заранее ограничены — один элемент не может иметь более двух потомков — иногда такая структура неэффективна;
- при построении БДП всегда нужно учитывать вероятность получения несбалансированного дерева. Наихудший сценарий — это становление дерева вырожденным: так называют деревья, каждый узел которого имеет только одного потомка. Выглядеть это может так:
1
\
2
\
3
\
4
\
5
Время выполнения операций (поиск, вставка, удаление) в таком случае равно O(n).
Примеры практического использования бинарного дерева поиска
- Алгоритмы поиска и сортировки — применение БДП для этих целей обусловлено высокой скоростью выполнения операций.
- Файловые системы с эффективной системой навигации и поиска. В таком случае каждый узел может представлять каталог или файл.
- Поисковые системы — здесь БДП может применяться для индексации страниц.
- Базы данных. БДП имеют подходящую структуру для хранения данных, а также позволяют быстро извлекать нужные элементы.
- Реализация функции автодополнения, например, автодополнение в поисковой строке браузера на основе введенной пользователем части запроса.
- Алгоритмы шифрования, в которых БДП могут выполнять роль генератора ключей.
Сбалансированные двоичные деревья и их отличие от БДП
Сбалансированное бинарное дерево — это, можно сказать, усовершенствованная версия обычного бинарного дерева поиска.
Двоичное дерево можно назвать сбалансированным, если его высота равна/близка к O(log n), где n — количество узлов. Соблюдение этого правила гарантирует высокую производительность во время выполнения операций: вставки, поиска и удаления. Существует несколько видов такой структуры данных, каждый из которых по-своему реализует указанное правило:
- AVL-дерево, в котором разница между высотой правого и левого поддерева для каждого угла не превышает единицу, то есть равна либо 0, либо 1. Оно может выглядеть так:
2
/ \
1 3
/ \
4 5
Здесь высота левого поддерева равна 1, а правого — 2. Разность значений высоты равна 1.
- красно-черное дерево, в котором каждый узел либо красного, либо черного цвета. Основное правило такой структуры заключается в том, что каждый путь от корня до листового узла содержит одинаковое количество черных элементов.
Есть и другие виды сбалансированных двоичных деревьев, например, B- или AA-дерево.
Сравнение бинарного дерева поиска с другими структурами данных
- БДП и список. Список — это линейная структура данных, элементы в нем расположены последовательно, а операции выполняются путем перебора каждого из них. Из-за этого скорость выполнения операций в списках ниже, чем в БДП.
- БДП и хеш-таблица. Операции в хеш-таблицах могут проводиться быстрее, чем в БДП — со скоростью O(1) в лучшем случае. Однако, в отличие от БДП, хеш-таблицы не хранят данные упорядоченно.
- БДП и куча. Кучи эффективны для быстрого извлечения элементов, но не позволяют сортировать их.
Оптимизация и балансировка двоичных деревьев поиска
Балансировать БДП нужно для того, чтобы оно не стало вырожденным, тогда операции с деревом становятся неэффективными. Это делается с помощью различных алгоритмов балансировки, реализация простейшего из которых представлена ниже:
class TreeNode {
// Конструктор
// storeInorder выполняет центрированный обход БДП и добавляет отсортированные элементы в массив
storeInorder(nodes) {
if (this === null) {
return;
}
if (this.left) {
this.left.storeInorder(nodes);
}
nodes.push(this.value);
if (this.right) {
this.right.storeInorder(nodes);
}
}
// buildBalancedTree использует полученный массив для построения сбалансированного БДП
static buildBalancedTree(nodes, start, end) {
if (start > end) {
return null;
}
// Вычисление среднего по значению элемента — он станет корнем
let mid = Math.floor((start + end) / 2);
let root = new TreeNode(nodes[mid]);
root.left = TreeNode.buildBalancedTree(nodes, start, mid - 1);
root.right = TreeNode.buildBalancedTree(nodes, mid + 1, end);
return root;
}
balanceBST() {
let nodes = [];
this.storeInorder(nodes);
return TreeNode.buildBalancedTree(nodes, 0, nodes.length - 1);
}
// Функция для вывода элементов
inorder() {
if (this === null) {
return;
}
if (this.left) {
this.left.inorder();
}
console.log(this.value);
if (this.right) {
this.right.inorder();
}
}
}Этот алгоритм не является методом создания самобалансирующегося БДП — к ним относятся AVL-, красно-черные деревья и другие. Он позволяет сбалансировать дерево однократно: при вставке новых элементов БДП может стать несбалансированным.