Коснёмся удаления, рассмотрим как при этом перестраивается дерево, и обсудим скорость работы двоичного дерева в лучшем и худшем случае.
В предыдущей статье мы рассмотрели операции для создания и обхода двоичного дерева.
Но таких операция недостаточно для полноценной работы с двоичным деревом поиска, кроме добавления элементов, иногда, элементы нужно удалять. В этой статье коснёмся этого вопроса, рассмотрим как при этом перестраивается дерево. Также обсудим скорость работы двоичного дерева в лучшем и худшем случае.
Скорость работы алгоритма и вырожденный случай
Рассмотрим идеальный случай формирования двоичного дерева.
Все элементы распределены равномерно между левыми и правыми поддеревьями. Такое дерево называется сбалансированным. Есть строгое определение этого: двоичное дерево сбалансировано по высоте, если для каждой его вершины высота её двух поддеревьев различается не более чем на 1.
Если рассмотреть сбалансированное дерево и операции с ним, то на каждом из переходов в поддерево, мы как бы отсекаем половину значений, понимая что в них точно не содержится нужное нам значение.
Алгоритмы с таким отсечением в несколько раз на каждом шаге, называют логарифмическими, или говорят что они работают за время log(N). Где N — количество узлов в дереве. По этому же принципу работает математический фокус по угадыванию числа от 0 до 100 за 7 попыток.
Можем заметить что при обходе в глубину (рассматривался в предыдущей статье) с использованием симметричного варианта обхода получаем отсортированный массив, и двоичное дерево можно было бы использовать для сортировки за время N * log(N) (N элементов, каждому находится место для вставки за log(N) время). К сожалению, вырожденный случай портит этот вариант, и построение двоичного дерева может занимать N * N (квадратичное) время. То есть каждый элемент вставляется за время N, то есть приходится проходить по всем элементам, чтобы найти нужное место для вставки нового элемента.
Посмотрим как будет выглядеть двоичное дерево, например при построении из возрастающего массива чисел 1, 3, 6, 9, 10.
Получаем просто односвязный список, все операции в которым занимают линейное время, или, что то же самое, выполняются за время O(N).
Для исправления этой ситуации существуют более сложные, сбалансированные, вариации двоичного дерева, например АВЛ дерево, красно-черное дерево, Б-деревья.
Также время работы может портить реализация, например при обходе в ширину, мы можем использовать метод shift, который сам по себе работает за линейное время. Что увеличивает время работы обхода с O(N) — обходим все элементы без дополнительных затрат на поиск элементов, до O(N*N) — на каждый элемент добавляется операция смещения всех элементов в массиве, который используется для хранения необработанных узлов.
Удаление элемента
Идея удаления элемента делится на несколько случаев:
у узла нет дочерних узлов;
у узла есть левый дочерних узлов;
у узла есть правый дочерних узлов;
у узла есть оба ребёнка.
В случае 1 просто удаляем узел, дополнительная работа не требуется.
В случае 2 и 3 заменяем удаляемый узел на его потомка, на этом удаление заканчивается. Случай 4 самый сложный, но концепция такого удаления довольно проста — найти в правом поддереве минимальный элемент и переместить его на место удаляемого узла.
Идейно удаление довольно просто, но мы знаем что работа с деревом обычно происходит через рекурсивные вызовы. И как удалить какой-то узел, если мы уже находимся в потомке не очень понятно.
Идея реализации удаления следующая. Спускаемся на уровень ниже, вызывая функцию рекурсивно, при этом присваивая обрабатываемому элементу, то что вернёт функция удаления.
Начало алгоритма удаления — поиск в дереве удаляемого элемента. При этом идея присваивания возвращаемого элемента из функции _deleteNode применяется сразу.
// при первом вызове не знаем куда пойдём, просто вызываем функцию для корня
// из этого вызова _deleteNode
// вернётся первый параметр(this.root), если удаляем не корень
this.root = this._deleteNode(this.root, nodeValue);
// при следующих вызовах у нас такой код, в зависимости от того
// в какое поддерево мы проваливаемся, до начала процедуры удаления
currentNode.left = this._deleteNode(currentNode.left, itemValue);
Когда нашли удаляемый элемент, то проверяем 4 случая описанные выше.
Если нет потомков, то просто возвращаем null, который в предыдущей вызове функции присвоится вместо элемента.
Если случаи 2 или 3, возвращаем один дочерний элемент, как бы убирая из дерева текущий узел.
Если у узла два потомка, то находим минимальный элемент в правом поддереве этого узла.
Можно встретить альтернативное описание поиска минимального элемента, более формальное, но имеющее тот же смысл, что описание выше:
если в первом узле правого поддерева нет левого узла, то используем его (это минимальный элемент, в правом узле все значение больше);
либо находим самый левый элемент в правом поддереве
Ниже в коде, для этого есть отдельная функция _findMinElement. После нахождения такого элемента, заменяем у текущего удаляемого узла значение (value). И вызываем функцию удаления правого поддерева, для найденного минимального узла в правом поддереве, так как мы его уже перенесли на место удаляемого, и на его старом место его нужно удалить. Код этого переноса и вызова удаления перенесенного элемента:
const minNodeInRightSubtree = this._findMinElement(currentNode.right);
// переносим элемент на место текущего — удаляемого
// перенос элемента это просто копирование его данных
currentNode.value = minNodeInRightSubtree.value;
currentNode.right = this._deleteNode(
// в правом поддереве
currentNode.right,
// удаляем найденный минимальный элемент
minNodeInRightSubtree.value
);
Код удаления элемента с комментариями:
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementNotFoundMessage = "The element wasn't found in the binary tree";
class BinaryTree {
constructor() {
this.root = null;
}
insertItem(newItem) {
const newNode = new BinaryTreeItem(newItem);
if (this.root === null) {
this.root = newNode;
return;
}
this._insertNode(this.root, newNode);
}
breadthFirstHandler(handlerFunction) {
const queue = [this.root];
let queuePosition = 0;
while (queuePosition < queue.length) {
const currentNode = queue[queuePosition];
handlerFunction(currentNode.value);
if (currentNode.left !== null) queue.push(currentNode.left);
if (currentNode.right !== null) queue.push(currentNode.right);
queuePosition++;
}
}
deleteItem(nodeValue) {
// если дерево пустое - ничего не делаем, можно выдать предупреждение
if (this.root === null) return null;
this.root = this._deleteNode(this.root, nodeValue);
}
_insertNode(currentNode, newNode) {
if (newNode.value < currentNode.value) {
if (currentNode.left === null) {
currentNode.left = newNode;
} else {
this._insertNode(currentNode.left, newNode);
}
}
if (newNode.value >= currentNode.value) {
if (currentNode.right === null) {
currentNode.right = newNode;
} else {
this._insertNode(currentNode.right, newNode);
}
}
}
_deleteNode(currentNode, itemValue) {
// если нашли нужный элемент, начинаем процедуру удаления
if (currentNode.value === itemValue) {
// обработка самого простого случая, вместо узла возвращается null
if (currentNode.left === null && currentNode.right === null) {
return null;
}
// обработка двух случаев, с только одним из поддеревьев
if (currentNode.left === null) {
return currentNode.right;
}
if (currentNode.right === null) {
return currentNode.left;
}
// если у ноды есть оба потомка
const minNodeInRightSubtree = this._findMinElement(currentNode.right);
// заменили текущий элемент минимальным из правого поддерева
currentNode.value = minNodeInRightSubtree.value;
// ищем в правом поддереве минимальный элемент,
// значение которого уже вставлено на место текущего
currentNode.right = this._deleteNode(
currentNode.right,
minNodeInRightSubtree.value
);
return currentNode;
}
// попадаем сюда, если элемент не был найден,
// просто проваливаемся в дерево глубже и глубже
// производится рекурсивный вызов этой же функции,
// при этом если элемент не будет найден,
// то алгоритм просто будет возвращать существующую ссылку на поддерево,
// которая присвоится в ту же позицию
if (itemValue < currentNode.value) {
if (currentNode.left === null) {
console.warn(elementNotFoundMessage);
return currentNode;
}
// проваливаемся в левое поддерево,
// после рекурсивной отработки функции _deleteNode
// будет возвращен текущий элемент,
// который в предыдущем вызове будет присвоен
currentNode.left = this._deleteNode(currentNode.left, itemValue);
// присваивание на рекурсивный уровень выше,
// может быть как в левое поддерево,так и в правое,
// на текущем уровне мы не знаем какое поддерево обрабатываем
return currentNode;
}
// аналогичная обработка для правого поддерева
if (itemValue > currentNode.value) {
if (currentNode.right === null) {
console.warn(elementNotFoundMessage);
return currentNode;
}
currentNode.right = this._deleteNode(currentNode.right, itemValue);
return currentNode;
}
}
_findMinElement(node) {
if (node.left === null) return node;
return this._findMinElement(node.left);
}
}
const binaryTree = new BinaryTree();
binaryTree.insertItem(3);
binaryTree.insertItem(1);
binaryTree.insertItem(6);
binaryTree.insertItem(4);
binaryTree.insertItem(8);
binaryTree.insertItem(-1);
binaryTree.insertItem(3.5);
binaryTree.insertItem(3.1);
binaryTree.insertItem(3.9);
binaryTree.deleteItem(3);
binaryTree.breadthFirstHandler(console.log);
Рассмотрим дерево
Удалим из этого дерева элемент 8.
Рассмотрим цепочку вызовов, сверху вниз:
// начало рекурсивных вызовов из функции deleteNode
this.root = this._deleteNode(this.root, nodeValue);
// первый вызов функции _deleteNode
// currentNode - root, узел со значением 3
currentNode.right = this._deleteNode(currentNode.right, itemValue);
// из _deleteNode вернется узел со значением 6,
// присвоится в правое поддерево root, как и было до работы этой функции
// второй вызов функции _deleteNode
// currentNode - узел со значением 6
currentNode.right = this._deleteNode(currentNode.right, itemValue);
// из функции this._deleteNode вернется null
// присвоится в правое поддерево узла со значением 6
// третий вызов функции _deleteNode
// currentNode - узел со значением 8
// сработает if с проверкой удаляемого элемента
if (currentNode.value === itemValue) {
// узел со значением 8 не имеет потомков
// из этой функции вернется null
if (currentNode.left === null && currentNode.right === null) {
return null;
}
Удалим из дерева элемент со значением 3.5.
Рассмотрим цепочку вызовов, сверху вниз:
// начало рекурсивных вызовов из функции deleteNode
this.root = this._deleteNode(this.root, nodeValue);
// первый вызов функции _deleteNode
// currentNode - root, узел со значением 3
currentNode.left = this._deleteNode(currentNode.left, itemValue);
// из _deleteNode вернется узел со значением 6,
// присвоится в левое поддерево root, как и было до работы этой функции
// второй вызов функции _deleteNode
// currentNode - узел со значением 6
currentNode.left = this._deleteNode(currentNode.left, itemValue);
// из _deleteNode вернется узел со значением 4
// присвоится в левое поддерево узла со значением 6
// третий вызов функции _deleteNode
// currentNode - узел со значением 4
currentNode.left = this._deleteNode(currentNode.left, itemValue);
// из _deleteNode вернется узел с измененным значением,
// т.к. дочерний элемент 3.5 мы удаляем
// (после прохода рекурсивных вызовов до одного из листов дерева)
// новое значение - 3.9
// четвертый вызов функции _deleteNode
// currentNode - узел со значением 3.5, начинается процедура удаления
// находится минимальный элемент - в правом поддереве 3.9
const minNodeInRightSubtree = this._findMinElement(currentNode.right);
// текущему элементу, вместо 3.5 присваивается 3.9
currentNode.value = minNodeInRightSubtree.value;
// запускается процедура удаления из правого поддерева элемента 3.9
currentNode.right = this._deleteNode(
currentNode.right,
minNodeInRightSubtree.value
);
// из функции _deleteNode вернется null, т.к. следующий элемент - удаляемый
// и у него нет потомков
// (может быть также случай с одним потомком, два потомка не может быть, т.к.
// тогда в левом поддереве элемент меньше текущего)
// возвращается currentNode, ссылки на правое и левое поддерево те же
// поменялось только значение в узле
return currentNode;
// пятый вызов функции _deleteNode
// currentNode - узел со значением 3.9
// совпадает value с удаляемым элементом -
// наш разыскиваемый минимальный элемент
// из функции вернется null
Полный код двоичного дерева
Здесь приводится полный код простейшего двоичного дерева (без getKey и compare функций) из двух статей, чтобы не пришлось собирать из разных частей, и можно было позапускать, для лучшего понимания.
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementNotFoundMessage = "The element wasn't found in the binary tree";
class BinaryTree {
constructor() {
this.root = null;
}
insertItem(newItem) {
const newNode = new BinaryTreeItem(newItem);
if (this.root === null) {
this.root = newNode;
return;
}
this._insertNode(this.root, newNode);
}
inorder(handlerFunction) {
this._inorderInternal(this.root, handlerFunction);
}
breadthFirstHandler(handlerFunction) {
if (this.root === null) return;
const queue = [this.root];
let queuePosition = 0;
while (queuePosition < queue.length) {
const currentNode = queue[queuePosition];
handlerFunction(currentNode.value);
if (currentNode.left !== null) queue.push(currentNode.left);
if (currentNode.right !== null) queue.push(currentNode.right);
queuePosition++;
}
}
deleteItem(nodeValue) {
if (this.root === null) {
console.warn(elementNotFoundMessage);
return null;
}
this.root = this._deleteNode(this.root, nodeValue);
}
_insertNode(currentNode, newNode) {
if (newNode.value < currentNode.value) {
if (currentNode.left === null) {
currentNode.left = newNode;
} else {
this._insertNode(currentNode.left, newNode);
}
}
if (newNode.value >= currentNode.value) {
if (currentNode.right === null) {
currentNode.right = newNode;
} else {
this._insertNode(currentNode.right, newNode);
}
}
}
_inorderInternal(currentNode, handlerFunction) {
if (currentNode === null) return;
this._inorderInternal(currentNode.left, handlerFunction);
handlerFunction(currentNode.value);
this._inorderInternal(currentNode.right, handlerFunction);
}
_deleteNode(currentNode, itemValue) {
if (currentNode.value === itemValue) {
if (currentNode.left === null && currentNode.right === null) {
return null;
}
if (currentNode.left === null) {
return currentNode.right;
}
if (currentNode.right === null) {
return currentNode.left;
}
// если у ноды есть оба потомка
const minNodeInRightSubtree = this._findMinElement(currentNode.right);
currentNode.value = minNodeInRightSubtree.value;
currentNode.right = this._deleteNode(
currentNode.right,
minNodeInRightSubtree.value
);
return currentNode;
}
if (itemValue < currentNode.value) {
if (currentNode.left === null) {
console.warn(elementNotFoundMessage);
return currentNode;
}
currentNode.left = this._deleteNode(currentNode.left, itemValue);
return currentNode;
}
if (itemValue > currentNode.value) {
if (currentNode.right === null) {
console.warn(elementNotFoundMessage);
return currentNode;
}
currentNode.right = this._deleteNode(currentNode.right, itemValue);
return currentNode;
}
}
_findMinElement(node) {
if (node.left === null) return node;
return this._findMinElement(node.left);
}
}
const binaryTree = new BinaryTree();
binaryTree.insertItem(3);
binaryTree.insertItem(1);
binaryTree.insertItem(6);
binaryTree.insertItem(4);
binaryTree.insertItem(8);
binaryTree.insertItem(-1);
binaryTree.insertItem(3.5);
binaryTree.deleteItem(3);
binaryTree.inorder(console.log);
binaryTree.breadthFirstHandler(console.log);
Заключение
Мы познакомились с концепцией двоичных деревьев — структурой данных, позволяющей работать с данными за логарифмическое время, вместо линейного. Все операции, кроме реализации удаления, интуитивно понятны. Эта структура данных является отправной точкой для знакомства с более сложными деревьями, такими как сбалансированные двоичные деревья.
