В этой статье рассмотрим двоичное или банарное дерево, как оно строится и варианты обходов. Материал подойдёт для новичков.
В этой статье рассмотрим двоичное дерево, как оно строится и варианты обходов.
Двоичное дерево в первую очередь дерево. В программировании – структура данных, которая имеет корень и дочерние узлы, без циклических связей. Если рассмотреть отдельно любой узел с дочерними элементами, то получится тоже дерево. Узел называется внутренним, если имеет хотя бы одно поддерево. Cамые нижние элементы, которые не имеют дочерних элементов, называются листами или листовыми узлами.
Дерево обычно рисуется сверху вниз.
В узлах может храниться любая информация, от примитивных типов до объектов. В этой статье, мы рассмотрим реализацию, когда в узле также хранятся ссылки на дочерние элементы. Кроме такого подхода, возможен альтернативный подход для двоичного дерева — хранение в массиве.
Первая особенность двоичного дерева, что любой узел не может иметь более двух детей. Их называют просто — левый и правый потомок, или левое и правое поддерево.
Вторая особенность двоичного дерева, и основное правило его построения, заключается в том что левый потомок меньше текущего узла, а правый потомок больше. Отношение больше/меньше имеет смысл для сравниваемых объектов, например числа, строки, если в дереве содержатся сложные объекты, то для них берётся какая-нибудь процедура сравнения, и она будет отрабатывать при всех операциях работы с деревом.
Создание дерева, вставка
Рассмотрим существующее двоичное дерево. Корень содержит число 3, все узлы в левом поддереве меньше текущего, в правом — больше. Такие же правила действуют для любого рассматриваемого узла и его поддеревьев.
Попробуем вставить в это дерево элемент -1.
Из корня идем в левое поддерево, так как -1 меньше 3. Из узла со значением 1 также идём в левое поддерево. Но в этом узле левое поддерево отсутствует, вставляем в эту позицию элемент, создавая новый узел дерева.
Вставим в получившееся дерево элемент 3.5.
Проходим по дереву, сравнивая на каждом из этапов вставляемое значение с элементом в узле, пока не дойдем до узла, в котором следующий узел для сравнения отсутствует, в эту позицию и вставляем новый узел.
Если дерево не существует, то есть root равен null, то элемент вставляется в корень, после этого проводится вставка по описанному выше алгоритму.
Напишем класс для создания двоичного дерева:
// дополнительный класс для хранения информации узла
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementExistMessage =
"The element has already in the tree";
class BinaryTree {
// в начале работы дерево пустое, root отсутствует
constructor() {
this.root = null;
}
insertItem(newItem) {
// создание нового узла дерева
const newNode = new BinaryTreeItem(newItem);
// проверка на пустой root, если пустой, то заполняем
// и завершаем работу
if (this.root === null) {
this.root = newNode;
return;
}
// вызов рекурсивного добавления узла
this._insertItem(this.root, newNode);
}
_insertItem(currentNode, newNode) {
// если значение в добавляемом узле
// меньше текущего рассматриваемого узла
if (newNode.value < currentNode.value) {
// если меньше и левое поддерево отсутствует
// то добавляем
if (currentNode.left === null) {
currentNode.left = newNode;
} else {
// если левое поддерево существует,
// то вызываем для этого поддерева
// процедуру добавления нового узла
this._insertItem(currentNode.left, newNode);
}
}
// для правого поддерева алгоритм аналогичен
// работе с левым поддеревом, кроме операции сравнения
if (newNode.value > currentNode.value) {
if (currentNode.right === null) {
currentNode.right = newNode;
} else {
this._insertItem(currentNode.right, newNode);
}
}
// если элемент равен текущему элементу,
// то можно реагировать по разному, например просто
// вывести предупреждение
// возможно стоит добавить проверку на NaN,
// зависит от потребностей пользователей класса
if (newNode.value === currentNode.value) {
console.warn(elementExistMessage);
}
}
}
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);
console.log(binaryTree);
На скриншоте ниже то, какую информацию хранит в себе binaryTree:
Обход
Рассмотрим несколько алгоритмов обхода/поиска элементов в двоичном дереве.
Мы можем спускаться по дереву, в каждом из узлов есть выбор куда можем пойти в первую очередь и какой из элементов обработать сначала: левое поддерево, корень или право поддерево. Такие варианты обхода называются обходы в глубину (depth first).
Какие возможны варианты обхода (слово поддерево опустим):
Также используется вариант для обхода деревьев по уровням. Уровень в дереве — его удалённость от корня. Сначала обходится корень, после этого узлы первого уровня и так далее. Называется обход в ширину, по уровням, breadth first, BFS — breadth first search или level order traversal.
Выбирается один из этих вариантов, и делается обход, в каждом из узлов применяя выбранную стратегию.
Обычно для обходов в глубину применяется рекурсия. Реализуем один из вариантов, например симметричный: левое поддерево, корень, правое поддерево.
При этом мы обработаем первым самый левый узел, где левое поддерево окажется пустым, но правое может присутствовать. То есть в каждом из узлов будем спускаться ниже и ниже, пока левое поддерево не окажется пустым.
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementExistMessage =
"The element has already in the tree";
class BinaryTree {
constructor() {
this.root = null;
}
insertItem(newItem) {
// .....
}
inorder(handlerFunction) {
// просто вызываем функцию с другими параметрами,
// добавляя текущий обрабатываемый узел
// в рекурсивные вызов
this._inorderInternal(this.root, handlerFunction);
}
_insertItem(currentNode, newNode) {
// .....
}
_inorderInternal(currentNode, handlerFunction) {
// если узла нет, то его обрабатывать не нужно
if (currentNode === null) return;
// порядок обхода, для каждого из поддеревьев:
// 1. проваливаемся в левое поддерево
// 2. вызываем обрабатывающую функцию
// 3. проваливаемся в правое поддерево
this._inorderInternal(currentNode.left,
handlerFunction);
handlerFunction(currentNode.value);
this._inorderInternal(currentNode.right,
handlerFunction);
}
}
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.inorder(console.log);
// вызов inorder(console.log) выведет
// -1
// 1
// 3
// 3.5
// 4
// 6
// 8
Для реализации других вариантов обхода просто меняем порядок вызова функций в функции _inorderInternal. И нужно не забыть переименовать функцию, чтобы название соответствовало содержимому.
Рассмотрим inorder алгоритм обхода на примере дерева, созданного в предыдущем блоке кода.
Сначала мы спустимся в самое левое поддерево — узел -1. Зайдем в его левое поддерево, которого нет, первая конструкция выполнится, ничего не сделав внутри функции. Вызовется обработчик handlerFunction, на узле -1. После этого произойдёт попытка войти в правое поддерево, которого нет. Работа функции для узла -1 завершится.
В вызов для узла -1 мы пришли через вызов функции _inorderInternal для левого поддерева узла 1. Вызов для левого поддерева -1 завершился, вызовется обработчик для значения узла 1, после этого — для правого поддерева. Правого поддерева нет, функция для узла 1 заканчивает работу. Выходим в обработчик для корня дерева.
Для корня дерева левое поддерево полностью отработало, происходит переход ко второй строке процедуры обхода — вызов обработчика значения узла. После чего вызов функции для обработчика правого поддерева.
Аналогично продолжая рассуждения, и запоминая на какой строке для определенного узла мы вошли в рекурсивный вызов, можем пройти алгоритм «руками», лучше понимая его работу.
Для обходов в ширину используется дополнительный массив.
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementExistMessage =
"The element has already in the tree";
class BinaryTree {
constructor() {
this.root = null;
}
insertItem(newItem) {
// .....
}
breadthFirstHandler(handlerFunction) {
if (this.root === null) return;
// массив, в который будем добавлять элементы,
// по мере спускания по дереву
const queue = [this.root];
// используем позицию в массиве для текущего
// обрабатываемого элемента
let queuePosition = 0;
// можем убирать обработанные элементы из очереди
// например функцией shift
// для обработки всегда брать нулевой элемент
// и завершать работу, когда массив пуст
// но shift работает за линейное время, что увеличивает
// скорость работы алгоритма
// while (queue.length > 0) {
// const currentNode = queue.shift();
while (queuePosition < queue.length) {
// текущий обрабатываемый элемент в queuePosition
const currentNode = queue[queuePosition];
handlerFunction(currentNode.value);
// добавляем в список для обработки дочерние узлы
if (currentNode.left !== null) {
queue.push(currentNode.left);
}
if (currentNode.right !== null) {
queue.push(currentNode.right);
}
queuePosition++;
}
}
_insertItem(currentNode, newNode) {
// ......
}
}
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.breadthFirstHandler(console.log);
// вызов breadthFirstHandler(console.log) выведет
// 3 корень
// 1 узлы первого уровня
// 6
// -1 узлы второго уровня
// 4
// 8
// 3.5 узел третьего уровня
Поиск
Операция поиска — вернуть true или false, в зависимости от того, содержится элемент в дереве или нет. Может быть реализована на основе поиска в глубину или ширину, посмотрим на реализацию на основе алгоритма обхода в глубину.
search(value) {
return this._search(this.root, value);
}
_search(currentNode, value) {
// дополнительные проверки,
// обрабатывающие завершение поиска
// либо проваливание в несуществующий узел
// либо найденной значение
if (currentNode === null) return false;
if (currentNode.value === value) return true;
// this._search проваливаются в дерево
// когда поиск завершен
// то по цепочке рекурсивных вызовов
// будет возвращен результат
if (value < currentNode.value) {
return this._search(currentNode.left, value);
}
if (value > currentNode.value) {
return this._search(currentNode.right, value);
}
}
Функция сравнения или получение ключа
До этого мы рассматривали простые данные, для которых определена операция сравнения между ключами. Не всегда возможно реализовать сравнение таким простым образом.
Можно сделать функцию, которая будет получать ключ из данных, которые хранятся в узле.
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementExistMessage =
"The element has already in the tree";
class BinaryTree {
// параметр при создании дерева -
// функция получения ключа
// ключи должны быть сравнимы
constructor(getKey) {
this.root = null;
this.getKey = getKey;
}
insertItem(newItem) {
const newNode = new BinaryTreeItem(newItem);
if (this.root === null) {
this.root = newNode;
return;
}
this._insertItem(this.root, newNode);
}
breadthFirstHandler(handlerFunction) {
// .....
}
_insertItem(currentNode, newNode) {
// отличие во всех процедурах сравнения
// вместо просто сравнивания value
// перед этим применяем функцию получения ключа
if (this.getKey(newNode.value) <
this.getKey(currentNode.value)) {
if (currentNode.left === null) {
currentNode.left = newNode;
} else {
this._insertItem(currentNode.left, newNode);
}
}
if (this.getKey(newNode.value) >
this.getKey(currentNode.value)) {
if (currentNode.right === null) {
currentNode.right = newNode;
} else {
this._insertItem(currentNode.right, newNode);
}
}
if (this.getKey(newNode.value) ===
this.getKey(currentNode.value)) {
console.warn(elementExistMessage);
}
}
}
const getKey = (element) => element.key;
const binaryTree = new BinaryTree(getKey);
binaryTree.insertItem({ key: 3 });
binaryTree.insertItem({ key: 1 });
binaryTree.insertItem({ key: 6 });
binaryTree.insertItem({ key: 4 });
binaryTree.insertItem({ key: 8 });
binaryTree.insertItem({ key: -1 });
binaryTree.insertItem({ key: 3.5 });
binaryTree.breadthFirstHandler(console.log);
Можно передать в конструктор специальную функцию сравнения. Эту функцию можно сделать как обычно делают функции сравнения в программировании, возвращать 0, если ключи равны. Значение больше нуля, если первый переданный объект больше второго, и меньше нуля если меньше. Важно не перепутать когда что возвращается и правильно передать параметры. Например, текущий узел, уже существующий в дереве, первым параметром, а тот, с которым производится текущая операция — вторым.
Для реализации такой возможности потребуется во всех местах сравнения использовать эту функцию
class BinaryTreeItem {
constructor(itemValue) {
this.value = itemValue;
this.left = null;
this.right = null;
}
}
const elementExistMessage =
"The element has already in the tree";
class BinaryTree {
// в конструкторе передаем функцию сравнения
constructor(compareFunction) {
this.root = null;
this.compareFunction = compareFunction;
}
insertItem(newItem) {
const newNode = new BinaryTreeItem(newItem);
if (this.root === null) {
this.root = newNode;
return;
}
this._insertItem(this.root, newNode);
}
breadthFirstHandler(handlerFunction) {
// .....
}
_insertItem(currentNode, newNode) {
// вместо сравнения value
// вызываем функцию сравнения
// и проверяем больше или меньше нуля
// получился результат сравнения
if (this.compareFunction(currentNode.value,
newNode.value) > 0) {
if (currentNode.left === null) {
currentNode.left = newNode;
} else {
this._insertItem(currentNode.left, newNode);
}
}
// текущий узел меньше нового,
// значит новый узел должен быть отправлен
// в правое поддерево
if (this.compareFunction(currentNode.value,
newNode.value) < 0) {
if (currentNode.right === null) {
currentNode.right = newNode;
} else {
this._insertItem(currentNode.right, newNode);
}
}
if (this.compareFunction(currentNode.value,
newNode.value) === 0) {
console.warn(elementExistMessage);
}
}
}
const compare = (object1, object2) => {
return object1.key - object2.key;
};
const binaryTree = new BinaryTree(compare);
binaryTree.insertItem({ key: 3 });
binaryTree.insertItem({ key: 1 });
binaryTree.insertItem({ key: 6 });
binaryTree.insertItem({ key: 4 });
binaryTree.insertItem({ key: 8 });
binaryTree.insertItem({ key: -1 });
binaryTree.insertItem({ key: 3.5 });
binaryTree.breadthFirstHandler(console.log);
