Размышления студента веб-разработки
Часто при изучении нового предмета вы снова и снова сталкиваетесь с терминами и, возможно, получаете некоторое понимание из контекста, но никогда не понимаете его полностью. Этот термин будет появляться снова и снова, пока, наконец, вы не решите копнуть глубже и попытаться понять, что он означает. Этот пост пытается найти один из этих терминов, структуры данных и, в частности, древовидную структуру данных. Я пролью немного света на это и, в частности, на двоичное дерево поиска.
Итак, что такое структура данных? Согласно Британской энциклопедии:
структура данных, способ хранения данных для эффективного поиска и извлечения.
(https://www.britannica.com/technology/data-structure)
Хорошо, давайте с этим. Структура данных — это способ хранения данных для эффективного поиска и извлечения. Звучит так, как будто у этого должно быть окончательное решение, потому что кому нужен неэффективный способ хранения данных, кроме тех, кто продает носители? Но, как оказалось, структуры данных — это целая область исследований с множеством различных способов хранения данных со своими плюсами и минусами.
Некоторыми распространенными структурами данных являются связанные списки, кучи, стеки, хэши, графики и, конечно же, дерево. Дерево — это тип структуры данных, в которой каждый элемент (чаще называемый узлом) может иметь один родительский узел и ни одного или несколько дочерних узлов. Узел в верхней части дерева без родителей называется корневым узлом.
Двоичное дерево поиска — это особый тип древовидной структуры, в котором каждый узел может иметь 0, 1 или 2 дочерних узла. Дочерний элемент слева всегда имеет значение меньше, чем его родитель, а дочерний элемент справа всегда имеет значение больше, чем его родитель. Вот пример:
В этом примере корневой узел имеет значение 10. Его левый дочерний узел имеет значение 6, что меньше 10, а его правый дочерний узел имеет значение 13, что больше 10. Каждый шаг вниз по дереву от корня другой уровень. Корневой узел находится на уровне 1, а его дочерние узлы — на уровне 2. Дочерние узлы на уровне 2, как вы уже догадались, находятся на уровне 3.
Это все хорошо и хорошо, но какой смысл? В чем смысл этой штуки? Что ж, я рад, что вы спросили! Помните в начале определение структуры данных из Британской энциклопедии, в котором упоминалась эффективность поиска и поиска? Что ж, хорошо построенное двоичное поисковое дерево неплохо справляется с этой задачей. Настолько, что это даже в его названии.
Давайте сравним его с массивом. Если бы у нас были все эти узлы, хранящиеся в массиве, и вы хотели бы найти конкретный узел. Вам придется перебирать массив, посещая каждый узел по одному, пока не достигнете целевого значения. В худшем случае вам придется посетить каждый элемент в массиве, прежде чем либо найти цель, либо понять, что цель не существует в массиве. Массив имеет среднюю временную сложность для поиска O(n).
В среднем бинарное дерево поиска позволяет исключать половину узлов каждый раз, когда вы перемещаетесь вниз по уровню. Это дает среднюю временную сложность O (log n), что намного быстрее. К сожалению, это не все единороги и радуги для двоичного дерева поиска, поскольку они могут стать несбалансированными, что приведет к наихудшей временной сложности даже с массивом в O (n). Предыдущий пример был идеально сбалансированным двоичным деревом поиска, вот пример наихудшего двоичного дерева поиска:
Существуют типы бинарных деревьев поиска, которые являются самобалансирующимися, но они выходят за рамки этого поста. Для дальнейшего чтения по ним вы можете выполнить поиск:
- 2–3 дерева
- Дерево АА
- Дерево АВЛ
- Б-дерево
- Красно–черное дерево
- Дерево козла отпущения
- Раскидистое дерево
- Танго-дерево
- Треп
- Сбалансированное по весу дерево
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
Теперь я поделюсь базовой реализацией двоичного дерева поиска в JavaScript. Вот конструктор. У каждого узла есть значение, глубина и левый и правый дочерние элементы.
class BinarySearchTree {
constructor(value, depth = 1) {
// Default depth of 1 indicates inital node added to tree is the root
this.value = value;
this.depth = depth;
this.left = null;
this.right = null;
}
}
Чтобы создать корневой узел и запустить двоичное дерево поиска:
const tree = new BinarySearchTree(12);
Это создаст новое дерево с корневым узлом, имеющим значение 12. Но одиночный узел не делает большого дерева, поэтому нам понадобится способ добавить в это дерево еще несколько узлов. Следующий метод находится в классе BinarySearchTree:
insert(value) {
// "this" refers to the node that called insert().
// Typically the root node on initial call
if (value < this.value) {
// The new node goes to the left of the current node
if (this.left === null) {
// Create new node and add as left child of current node
this.left = new BinarySearchTree(value, this.depth + 1);
console.log(`Tree node ${value} added to the left of ${this.value} at depth ${this.depth + 1}`);
return;
}
// Call insert() with current node's left child as "this"
this.left.insert(value);
return;
}
// The new node goes to the right of the current node
if (value > this.value) {
if (this.right === null) {
// Create new node and add as right child of current node
this.right = new BinarySearchTree(value, this.depth + 1);
console.log(`Tree node ${value} added to the right of ${this.value} at depth ${this.depth + 1}`);
return;
}
// Call insert() with current node's right child as "this"
this.right.insert(value);
return;
}
// Values that are already in the tree are ignored
}
Чтобы добавить еще несколько узлов в дерево, мы могли бы сделать что-то вроде этого:
const arr = [8, 4, 10, 7, 1, 30, 20, 50, 43, 26]; arr.forEach(el => tree.insert(el));
Теперь у нас есть корень и еще десять узлов в нашем дереве. Это больше походит на это! Вот что будет отображаться в консоли после запуска:
Tree node 8 added to the left of 12 at depth 2 Tree node 4 added to the left of 8 at depth 3 Tree node 10 added to the right of 8 at depth 3 Tree node 7 added to the right of 4 at depth 4 Tree node 1 added to the left of 4 at depth 4 Tree node 30 added to the right of 12 at depth 2 Tree node 20 added to the left of 30 at depth 3 Tree node 50 added to the right of 30 at depth 3 Tree node 43 added to the left of 50 at depth 4 Tree node 26 added to the right of 20 at depth 4
А вот как это выглядит визуально:
Итак, теперь у нас есть дерево, но как насчет его тезки, всей поисковой части вещей? Как мы можем искать это дерево? Рад, что вы спросили, вот метод поиска для класса BinarySearchTree:
getNodeByValue(value) {
// "this" refers to the node that called getNodeByValue().
// Typically the root node on initial call
if (this.value === value) {
return this;
}
if (this.left !== null && value < this.value) {
return this.left.getNodeByValue(value);
}
if (this.right !== null && value > this.value) {
return this.right.getNodeByValue(value);
}
return null;
}
Этот метод позволит нам найти любое значение в дереве и вернуть null, если значение не существует. Вот пример использования, который будет проходить по дереву и возвращать узел со значением 20:
tree.getNodeByValue(20)
Еще одна полезная вещь, которую мы можем сделать с помощью двоичного дерева поиска, — это быстро найти минимальное и максимальное значения. Эти методы также находятся в классе BinarySearchTree:
findMinValue() {
// "this" refers to the node that called findMinValue().
// Typically the root node on initial call
if (this.left === null) {
// If there is no left child, this is the minimum node
return this;
}
return this.left.findMinValue();
}
findMaxValue() {
// "this" refers to the node that called findMaxValue().
// Typically the root node on initial call
if (this.right === null) {
// If there is no right child, this is the maximum node
return this;
}
return this.right.findMaxValue();
}
Использование будет:
tree.findMinValue() tree.findMaxValue()
Самая сложная часть двоичного дерева поиска — это удаление узла. Если у удаляемого узла есть дочерние элементы, эти дочерние элементы необходимо будет переместить, чтобы они не остались сиротами. Если узел имеет двух дочерних элементов, правый дочерний элемент занимает его место. Если у него есть только один ребенок, этот ребенок занимает его место. После того, как эти приготовления были сделаны, мы также не можем забыть уведомить родителя теперь удаленного узла, что теперь у него есть новый дочерний узел. Вот метод в классе BinarySearchTree для этого:
delete(value) {
// "this" refers to the node that called delete().
// Typically the root node on initial call
if (this.value === null) {
return this;
}
if (value < this.value) {
this.left = this.left.delete(value);
}
if (value > this.value) {
this.right = this.right.delete(value);
}
if (value === this.value) {
if (this.left === null) {
let temp = this.right;
this.value = null;
return temp;
}
if (this.right === null) {
let temp = this.left;
this.value = null;
return temp;
}
let temp = this.right.findMaxValue();
this.value = temp.value;
this.right.delete(temp);
}
return this;
}
Это использует преимущества предыдущего метода findMaxValue(). Вот пример использования:
tree.delete(20);
Еще одна важная вещь, которую нужно иметь в нашем классе BinarySearchTree, — это возможность обхода дерева по порядку и получения распечатки всего дерева. Вот метод для этого:
depthFirstTraversal() {
if (this.left !== null) {
this.left.depthFirstTraversal();
}
console.log(`Depth: ${this.depth}, Value: ${this.value}`);
if (this.right !== null) {
this.right.depthFirstTraversal();
}
}
Пример использования этого метода:
tree.depthFirstTraversal();
С нашим исходным деревом перед удалением каких-либо элементов это даст следующий результат:
Depth: 4, Value: 1 Depth: 3, Value: 4 Depth: 4, Value: 7 Depth: 2, Value: 8 Depth: 3, Value: 10 Depth: 1, Value: 12 Depth: 3, Value: 20 Depth: 4, Value: 26 Depth: 2, Value: 30 Depth: 4, Value: 43 Depth: 3, Value: 50
Наконец, вероятно, было бы полезно иметь возможность отображать узел в каком-то удобочитаемом формате. Итак, вот метод для этого:
printNode() {
return (`
Value: ${this.value}
Depth: ${this.depth}
Left Child: ${this.left ? this.left.value : null}
Right Child: ${this.right ? this.right.value : null}
`);
}
Пример использования и вывода, объединяющий метод findMinValue():
console.log('Minimum value: ', tree.findMinValue().printNode());
и вывод:
Minimum value:
Value: 1
Depth: 4
Left Child: null
Right Child: null
Таким образом, двоичные деревья поиска — это тип структуры данных, специализирующийся на поиске. См. ниже весь класс BinarySearchTree.
class BinarySearchTree {
constructor(value, depth = 1) {
// Default depth of 1 indicates inital node added to tree is the root
this.value = value;
this.depth = depth;
this.left = null;
this.right = null;
}
insert(value) {
// "this" refers to the node that called insert().
// Typically the root node on initial call
if (value < this.value) {
// The new node goes to the left of the current node
if (this.left === null) {
// Create new node and add as left child of current node
this.left = new BinarySearchTree(value, this.depth + 1);
console.log(`Tree node ${value} added to the left of ${this.value} at depth ${this.depth + 1}`);
return;
}
// Call insert() with current node's left child as "this"
this.left.insert(value);
return;
}
// The new node goes to the right of the current node
if (value > this.value) {
if (this.right === null) {
// Create new node and add as right child of current node
this.right = new BinarySearchTree(value, this.depth + 1);
console.log(`Tree node ${value} added to the right of ${this.value} at depth ${this.depth + 1}`);
return;
}
// Call insert() with current node's right child as "this"
this.right.insert(value);
return;
}
// Values that are already in the tree are ignored
}
getNodeByValue(value) {
// "this" refers to the node that called getNodeByValue().
// Typically the root node on initial call
if (this.value === value) {
return this;
}
if (this.left !== null && value < this.value) {
return this.left.getNodeByValue(value);
}
if (this.right !== null && value > this.value) {
return this.right.getNodeByValue(value);
}
return null;
}
findMinValue() {
// "this" refers to the node that called findMinValue().
// Typically the root node on initial call
if (this.left === null) {
// If there is no left child, this is the minimum node
return this;
}
return this.left.findMinValue();
}
findMaxValue() {
// "this" refers to the node that called findMaxValue().
// Typically the root node on initial call
if (this.right === null) {
// If there is no right child, this is the maximum node
return this;
}
return this.right.findMaxValue();
}
delete(value) {
// "this" refers to the node that called delete().
// Typically the root node on initial call
if (this.value === null) {
return this;
}
if (value < this.value) {
this.left = this.left.delete(value);
}
if (value > this.value) {
this.right = this.right.delete(value);
}
if (value === this.value) {
if (this.left === null) {
let temp = this.right;
this.value = null;
return temp;
}
if (this.right === null) {
let temp = this.left;
this.value = null;
return temp;
}
let temp = this.right.findMaxValue();
this.value = temp.value;
this.right.delete(temp);
}
return this;
}
depthFirstTraversal() {
if (this.left !== null) {
this.left.depthFirstTraversal();
}
console.log(`Depth: ${this.depth}, Value: ${this.value}`);
if (this.right !== null) {
this.right.depthFirstTraversal();
}
}
printNode() {
return (`
Value: ${this.value}
Depth: ${this.depth}
Left Child: ${this.left ? this.left.value : null}
Right Child: ${this.right ? this.right.value : null}
`);
}
}
