Двоичный поиск очень хорошо решает проблему поиска, уменьшая временную сложность с O(n) до O(logn). Но предпосылка бинарного поиска заключается в том, что данные должны быть упорядочены и иметь линейные индексы. Для линейных таблиц можно хорошо применять бинарный поиск, но при операциях вставки и удаления вся линейная таблица может быть турбулентной, а временная сложность достигает O(n) Связанные списки нельзя использовать для бинарного поиска.
Таким образом, при представленном ниже алгоритме временная сложность поиска, вставки и удаления может достигать O(logn)——бинарное дерево поиска
Как известно из названия, его структура данных основана на бинарном дереве, и когда я впервые столкнулся с бинарным деревом, я не почувствовал, что в нем есть что-то выдающееся. Но когда я увидел схему бинарного дерева поиска, построенную по бинарному дереву, я был глубоко потрясен.
определение
Двоичное дерево поиска (английский язык: Binary Search Tree), также известное как двоичное дерево поиска, упорядоченное двоичное дерево (английский язык: упорядоченное двоичное дерево), отсортированное двоичное дерево (английский язык: отсортированное двоичное дерево), относится к пустому дереву или имеет следующие свойства. Бинарное дерево:
Если левое поддерево любого узла не пусто, значение всех узлов левого поддерева меньше значения его корневого узла; Если правое поддерево любого узла не пусто, значение всех узлов в правом поддереве больше, чем значение его корневого узла; Левое и правое поддеревья любого узла также являются соответственно бинарными деревьями поиска; Нет узлов с одинаковыми ключами.
В соответствии с приведенными выше правилами сначала определим бинарное дерево
Правила можно легко увидеть здесь, и они не нуждаются в особых пояснениях.
вставлять
Теперь вставьте еще один элемент 13. 13>12, поэтому идите вправо к 14, 13
найти
В соответствии с изложенными выше идеями операция поиска может быть легко реализована. И установлено, что временная сложность его поиска равна глубине дерева.
Согласно свойствам полного бинарного дерева, глубина полного бинарного дерева с n узлами равна
[logn] + 1
игнорировать+1Сложность времени поиска бинарного дерева поиска получается какO(logn), но это не так, разберем позже.
траверс
Существует три способа обхода двоичного дерева: обход в предварительном порядке, по порядку и обход в обратном порядке.Здесь мы сосредоточимся на обходе в обратном порядке.
При последовательном обходе бинарного дерева поиска разностей можно получитьascрезультаты сортировки. Результат упорядоченного обхода дерева выше:3, 8, 9, 12, 13, 14.中序遍历从一颗子树最左的节点开始输出，既该树的最小值. Для реализации обхода по порядку достаточноточка сбора данныхПомещенный между левой рекурсивной точкой и правой рекурсивной точкой, это все еще немного расплывчато, посмотрите на код
/**
* 中序遍历
* @param $root
* @return array
*/
public function inorder($root)
{
$data = [];
if ($root->left) {
$data = array_merge($data, $this->inorder($root->left)); //左孩子递归点
}
$data[] = $root->data; // 这里是中序遍历的数据收集点
if ($root->right) {
$data = array_merge($data, $this->inorder($root->right)); // 右孩子递归点
}
return $data;
}
Предшественник и преемник, взяв в качестве примера 9 узлов, 12 принадлежат преемнику 9, а 8 принадлежит предшественнику 9.
Удалить
Добавим в это дерево еще несколько узлов
Узлы в дереве удаления делятся на множество ситуаций. Например, удаленный узел не имеет дочерних узлов, существует только левое/правое поддерево, а также левое и правое поддеревья. Здесь левое и правое поддеревья с самой широкой освещение было Есть примеры.
Мы хотим написать, сколько случаев нет большого спроса в случае анализа спроса. Но если проанализировать взаимосвязь между случаями, есть ли дублирование или отношения принадлежности, программист должен извлечь суть требования и стремиться к достижению наиболее лаконичного
Теперь мы собираемся удалить узел 25, что бы вы сделали? Если вы просто замените исходные 25 на 18, вам нужно перенастроить дочерние элементы 18-го поддерева. 18 Это нормально иметь только троих детей, но когда их тысячи, это, очевидно, вызывает большую корректировку. Поэтому я надеюсь найти лучший узел для замены 25. Согласно описанию во введении к алгоритму, мы должны искать предшественника или преемника этого узла, чтобы заменить его.Например, 24 и 27 на рисунке являются предшественниками и преемник 25 соответственно.
Зачем вместо этого использовать префикс или суффикс? Я не уверен в этом, причина, по которой я назвал себя, была
- Узел — это специальное значение, принадлежащее максимальному или минимальному значению поддерева, оно детерминировано и может быть хорошо определено и найдено.
- Поскольку узел принадлежит предшественнику или преемнику удаленного узла, влияние удаления узла на структуру данных минимально.Я не уверен, какая структура данных оказывает наименьшее влияние
Иллюстрация описанной выше ситуации выглядит следующим образом ↓
Существуют и другие ситуации для удаления, например следующие ↓
В этом случае можно напрямую увеличить 30 до 25. Далее давайте посмотрим на реализацию кода php:
public function delete($root, $data)
{
if (!$root) {
return null;
}
if ($root->data === $data) {
if ($root->left) {
// 左转
$node = $root->left;
$parent = $root;
$toward = 'left';
while ($node->right) {
$parent = $node;
$toward = 'right';
$node = $node->right;
}
$root->data = $node->data;
$parent->{$toward} = $this->delete($node, $node->data);
} else {
return $root->right;
}
} elseif ($root->data > $data) {
// 如果root的左孩子没有被删除,那就原样返回回来, 如果被删除了,那就找个孩子代替
$root->left = $this->delete($root->left, $data);
} else {
$root->right = $this->delete($root->right, $data);
}
return $root;
}
Поскольку в php есть механизм рециркуляции памяти, у нас нет возможности напрямую модифицировать память, как в c, поэтому здесь мы используем рекурсивную функцию для решения этой проблемы.$root->left = $this->delete($root->left, $data);Выполнение такого процесса может быть несколько трудным для понимания. Но я все еще могу понять~
В дополнение к рекурсивным решениям также могут быть использованы следующие методы. То есть определить родителя и направление в качестве руководства, что также отражено в приведенном выше коде.Этот метод больше подходит для итеративной обработки.
$parent = $root;
$toward = 'left';
while ($node->right) {
$parent = $node;
$toward = 'right';
$node = $node->right;
}
Обратитесь к модульным тестам для получения более подробной информации о интернировании и примерах вызова.
Реализация алгоритма
Пополнить
Поскольку в php нет буквального объекта, такого как js, или структуры, такой как c. Поэтому объекты используются непосредственно для представления узлов в дереве.
class BiTNode
{
public $data;
public $left;
public $right;
public function __construct($data, $left = null, $right = null)
{
$this->data = $data;
$this->left = $left;
$this->right = $right;
}
}
При поиске было указано, что временная сложность запроса бинарного дерева поиска не является строго O(logn), поскольку существует такая ситуация, предполагая, что вам нужно вставить12, 10, 9, 5, 4, 1Этих немного данных, то мы получим вот такое дерево с кривошеей
Конечно, бинарное дерево поиска по-прежнему является основой различных деревьев, пожалуйста, внимательно изучите его.