До сих пор я реализовывал стеки, очереди, связанные списки и хэш-карты. Сегодня я собираюсь рассмотреть бинарные деревья поиска или BST.
Бинарные деревья поиска
Двоичные деревья поиска — это структуры данных, используемые для хранения данных в отсортированном порядке. Дерево начинается с корневого узла и разветвляется на другие узлы по мере того, как дерево становится все больше и больше.Однако есть пара загвоздок.
- Каждый узел может иметь не более двух дочерних элементов.
- Узлы слева от узла всегда меньше самого узла.
- Узлы справа от узла всегда больше, чем сам узел.
Сегодня мы реализуем три основные операции:
- вставлять()
- получить()
- Удалить()
Выполнение
Как видно из диаграммы выше, каждый узел имеет множество свойств: ключ, значение, родительский, левый и правый. Эти свойства позволят нам отслеживать, где находится каждый узел по отношению к корневому узлу или узлу в верхней части дерева.
let BinarySearchTree = function(key, value, parent) {
this.key = key || null;
this.value = value || null;
this.parent = parent || null;
this.left = null;
this.right = null;
};
Этот конструктор представляет один узел в нашем BST. Наш BST будет отсортирован в соответствии со свойством key каждого узла, и мы будем использовать свойства left и right для размещения наших узлов в правильный порядок.
Далее идет наша функция вставки, которая вставит элемент в наш BST.
BinarySearchTree.prototype.insert = function(key, value) {
if (this.key == null) {
this.key = key;
this.value = value;
} else if (key < this.key) (
if (this.left == null) {
this.left = new BinarySearchTree(key, value, this);
} else {
this.left.insert(key, value)
}
} else {
if (this.right == null) {
this.right = new BinarySearchTree(key, value, this);
} else {
this.right.insert(key, value);
}
}
};
Сначала мы проверяем, пуст ли BST. Если это так, то мы можем просто установить корневой узел на ключ и значение. Если дерево не пусто, то сначала проверяем, не меньше ли оно корня. Если это так, мы проверяем, является ли левый дочерний узел нулевым, и вставляем узел в левый дочерний узел, если он не нулевой, то мы рекурсивно вызываем вставку, чтобы двигаться дальше вниз влево. Это также происходит для правой стороны, но идет справа от корня.
Далее идет наша функция get(). Все, что нам нужно сделать, это вернуть значение узла, если наши ключи совпадают.
BinarySearchTree.prototype.get = function(key) {
if (this.key == key) {
return this.value;
} else if (key < this.key && this.left) {
return this.left.get(key);
} else if (key > this.key && this.right) {
return this.right.get(key);
} else {
throw new Error('Key error');
}
};
Сначала мы проверяем, равен ли корень нашему ключу. Если нет, то мы проверяем, меньше или больше наш ключ, чем наш корень. В зависимости от того, какому условию оно соответствует, мы рекурсивно вызываем get() для левого или правого дерева. Если ключ не больше и не меньше корня и не является корнем, то у нас есть ошибка ключа.
Наша функция удаления потребует гораздо больше размышлений. Если мы удаляем корневой узел, мы сначала проверяем, есть ли у него потомки.
- Если у корня есть и левый, и правый, нам нужно найти преемника корня, найдя наименьшее значение правого потомка.
- Если у корня есть только левый дочерний элемент, используйте левого дочернего элемента в качестве преемника.
- Если у корня есть только правильный дочерний элемент, используйте правильный дочерний элемент в качестве преемника.
- Если у него нет детей, используйте null в качестве преемника.
Это наши четыре условия только для замены корневого узла. Если мы заменяем узел, который не является корневым, то мы должны рекурсивно вызывать удаление для левого или правого дочернего узла до тех пор, пока наши ключи не совпадут, а затем вызвать функцию замены.
BinarySearchTree.prototype.remove = function(key) {
if (this.key == key) {
if (this.left && this.right) {
let successor = this.right._findMin();
this.key = successor.key;
this.value = successor.value;
successor.remove(successor.key);
} else if (this.left) {
this._replaceWith(this.left);
} else if (this.right) {
this._replaceWith(this.right);
} else {
this._replaceWith(null);
}
} else if (key < this.key && this.left) {
this.left.remove(key);
} else if (key > this.key && this.right) {
this.right.remove(key);
} else {
throw new Error('Key Error');
}
};
Давайте теперь поработаем над нашими функциями _replaceWith и _findMin. Для _replaceWith мы сначала проверяем, есть ли у него родитель, если да, то мы исправляем ссылки от родителя к заменяемому узлу. Если мы заменяем корневой узел, мы просто копируем свойства заменяющего узла.
BinarySearchTree.prototype._replaceWith = function(node) {
if (this.parent) {
if (this == this.parent.left) {
this.parent.left = node;
} else if (this == this.parent.right) {
this.parent.right = node;
}
if (node) {
node.parent = this.parent;
}
} else {
if (node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
} else {
this.key = null;
this.value = null;
this.left = null;
this.right = null;
}
}
};
Для нашей функции _findMin все, что нам нужно сделать, это рекурсивно пройти слева по дереву, пока мы не достигнем того места, где левый дочерний элемент равен нулю, что означает, что мы достигли минимума.
BinarySearchTree.prototype._findMin = function() {
if (!this.left) {
return this;
}
return this.left._findMin();
};
И это охватывает все наши функции для BST! Вот все функции вместе с конструктором.
let BinarySearchTree = function(key, value, parent) {
this.key = key || null;
this.value = value || null;
this.parent = parent || null;
this.left = null;
this.right = null;
};
BinarySearchTree.prototype.insert = function(key, value) {
if (this.key == null) {
this.key = key;
this.value = value;
} else if (key < this.key) (
if (this.left == null) {
this.left = new BinarySearchTree(key, value, this);
} else {
this.left.insert(key, value)
}
} else {
if (this.right == null) {
this.right = new BinarySearchTree(key, value, this);
} else {
this.right.insert(key, value);
}
}
};
BinarySearchTree.prototype.get = function(key) {
if (this.key == key) {
return this.value;
} else if (key < this.key && this.left) {
return this.left.get(key);
} else if (key > this.key && this.right) {
return this.right.get(key);
} else {
throw new Error('Key error');
}
};
BinarySearchTree.prototype.remove = function(key) {
if (this.key == key) {
if (this.left && this.right) {
let successor = this.right._findMin();
this.key = successor.key;
this.value = successor.value;
successor.remove(successor.key);
} else if (this.left) {
this._replaceWith(this.left);
} else if (this.right) {
this._replaceWith(this.right);
} else {
this._replaceWith(null);
}
} else if (key < this.key && this.left) {
this.left.remove(key);
} else if (key > this.key && this.right) {
this.right.remove(key);
} else {
throw new Error('Key Error');
}
};
BinarySearchTree.prototype._replaceWith = function(node) {
if (this.parent) {
if (this == this.parent.left) {
this.parent.left = node;
} else if (this == this.parent.right) {
this.parent.right = node;
}
if (node) {
node.parent = this.parent;
}
} else {
if (node) {
this.key = node.key;
this.value = node.value;
this.left = node.left;
this.right = node.right;
} else {
this.key = null;
this.value = null;
this.left = null;
this.right = null;
}
}
};
BinarySearchTree.prototype._findMin = function() {
if (!this.left) {
return this;
}
return this.left._findMin();
};
Сложности времени
Insert() принимает O(log(n)), потому что наша высота логарифмически растет с количеством узлов, поскольку каждая строка содержит в два раза больше узлов, чем предыдущая строка в BST.
Remove()занимает O(log(n)) времени, учитывая тот же процесс мышления, что и наша временная сложность вставки().
Get() занимает O(log(n)), так как мы проходим через высоту нашего дерева.
Для получения дополнительной информации о временных сложностях посмотрите на эту Большую шпаргалка.
