Вступление
Построение связанного списка — довольно простая задача. Связанные списки представляют собой линейную структуру, и элементы расположены один за другим, каждый из которых указывает на своего предшественника и его преемника. Почти каждая операция легко кодируется в несколько строк и не требует дополнительных навыков. Такие операции, как вставка, удаление и т. Д. Над связанными списками, выполняются за линейное время. Конечно, для небольших наборов данных это работает нормально, но по мере роста данных эти операции, особенно операция поиска, становятся слишком медленными.
Действительно, поиск в связанном списке имеет линейную сложность, и в худшем случае мы должны пройти весь список, чтобы найти нужный элемент. Худший случай, когда элемент не принадлежит списку, и мы должны проверить каждый элемент списка, даже последний, безуспешно. Этот подход очень похож на последовательный поиск по массивам. Конечно, это плохо, когда мы говорим о больших наборах данных.
Последовательный поиск по массивам очень похож на поиск в связанных списках, и это в основном неэффективная операция!
С точки зрения массивов, мы можем выполнить бинарный поиск и перейти прямо в середину массива, а затем перейти назад или вперед. Это потому, что мы можем получить доступ к элементам массива напрямую, используя их индекс. Однако, как мы увидели, связанные списки в отличие от массивов не могут получить прямой доступ, и мы должны переходить по пунктам.
Из-за этой естественной проблемы поиск связанных списков идет медленно, и, очевидно, мы не можем сделать его лучше. Единственный способ улучшить поиск по динамическим структурам данных — это использовать другую структуру данных.
Дерево — это структура данных, в которой каждый элемент, за исключением хранения некоторых данных, хранит ссылку (указатель) на своих потомков и своих родителей.
Древовидная структура данных. Каждый элемент указывает на своего родителя и его потомков. Однако родитель корня это NIL.
Конечно, если у элемента нет дочерних элементов, они равны NIL, тогда это считается листом в терминологии дерева. С другой стороны, если у элемента нет родительского элемента, он считается корневым.
Корень и листья
Если в дереве нет элемента, дерево считается пустым.
В этих терминах только корень не имеет родителя, и каждый элемент может иметь как можно больше дочерних элементов. Вот несколько деревьев в виде диаграмм.
Возможные деревья
Если мы посмотрим на корень дерева, мы можем предположить, что есть два поддерева — одно левое и одно правое. Однако если мы изолируем только одно из этих поддеревьев, мы можем снова думать о нем как о дереве и предполагать, что у него есть одно левое и одно правое поддеревья, и рекурсивно использовать это определение.
Левые и правые поддеревья
обзор
Бинарное дерево — это дерево, в котором каждый элемент может иметь не более двух дочерних элементов.
В двоичном дереве каждый узел имеет не более двух поддеревьев — левое и правое!
Двоичные деревья особенно важны, потому что они могут содержать упорядоченные данные определенным образом. Создание двоичного дерева совсем не сложно, и оно очень похоже на создание связанного списка.
Однако бинарное дерево не является более успешным в поиске, чем любое другое дерево или структура данных. Если элементы не размещены в определенном порядке, мы должны пройти через все дерево, чтобы найти искомый элемент. Это не очень хорошая оптимизация, поэтому мы должны сделать заказ, чтобы улучшить процесс поиска.
Двоичное дерево поиска
Бинарное дерево поиска — это особый вид бинарного дерева, где каждый элемент содержит большие элементы справа, а меньшие элементы — слева.
Двоичное дерево поиска — BST
Построить двоичное дерево поиска легко, потому что мы можем вставить каждый элемент, только сравнив его с корнем и решив, куда идти (влево или вправо), основываясь на его значении.
Вставить в двоичное дерево поиска довольно просто
Реализация
Следующий код в PHP описывает основные принципы бинарного дерева поиска.
class Node
{
public $parent = null;
public $left = null;
public $right = null;
public $data = null;
public function __construct($data)
{
$this->data = $data;
}
public function __toString()
{
return $this->data;
}
}
class BinaryTree
{
protected $_root = null;
protected function _insert(&$new, &$node)
{
if ($node == null) {
$node = $new;
return;
}
if ($new->data <= $node->data) {
if ($node->left == null) {
$node->left = $new;
$new->parent = $node;
} else {
$this->_insert($new, $node->left);
}
} else {
if ($node->right == null) {
$node->right = $new;
$new->parent = $node;
} else {
$this->_insert($new, $node->right);
}
}
}
protected function _search(&$target, &$node)
{
if ($target == $node) {
return 1;
} else if ($target->data > $node->data && isset($node->right)) {
return $this->_search($target, $node->right);
} else if ($target->data <= $node->data && isset($node->left)) {
return $this->_search($target, $node->left);
}
return 0;
}
public function insert($node)
{
$this->_insert($node, $this->_root);
}
public function search($item)
{
return $this->_search($item, $this->_root);
}
}
$a = new Node(3);
$b = new Node(2);
$c = new Node(4);
$d = new Node(7);
$e = new Node(6);
$t = new BinaryTree();
$t->insert($a);
$t->insert($b);
$t->insert($c);
$t->insert($d);
$t->insert($e);
echo $t->search($e);
Сложность поиска
Предполагается, что поиск в двоичных деревьях поиска будет быстрее, чем поиск в связанном списке. Однако процесс поиска в BST может быть очень быстрым, но также может быть таким же медленным, как в связанном списке. Это потому, что в зависимости от ввода элементов они могут быть размещены только на одной стороне корня.
Вставляя только большие элементы, вы получаете только правильные поддеревья — дерево не отличается от связанного списка, и поиск идет медленно!
Это делает поиск в худшем случае медленным, как в связанном списке, который является линейным O (n). Однако, если дерево каким-то образом сбалансировано, мы можем искать очень быстро с O (log (n)) временем.
Дальнейшая оптимизация
Теперь мы видим, насколько неэффективными могут быть деревья бинарного поиска, поэтому нам нужно заботиться только о том, как сохранить их сбалансированными, чтобы поиск был быстрее. Ответ заключается в поддержании (во время вставки) сбалансированного бинарного дерева поиска, которое является еще одной очень удобной структурой данных.
Сбалансированное двоичное дерево поиска или только сбалансированное дерево — это структура данных, в которой высота левого и правого поддеревьев может изменяться не более чем на один уровень.
Поиск в сбалансированном дереве значительно быстрее, чем в некоторых двоичных деревьях поиска!
заявка
Деревья бинарного поиска легко создавать и поддерживать. Самое замечательное, что если данные хорошо сбалансированы, они могут быть очень полезны для поиска. Единственная проблема заключается в том, что эти структуры могут быть неэффективными в зависимости от порядка вставки. Однако если мы каким-то образом уверены, что элементы не упорядочены на входе, мы можем ожидать некоторого оптимизированного поиска по сравнению со связанным списком. По сравнению со сбалансированными бинарными деревьями поиска, BST требует гораздо меньше времени для сборки и поддержки (вставка, удаление).
Деревья очень полезны при работе с графиками. На самом деле, одна из самых распространенных задач — пройти по всему дереву, что можно сделать несколькими способами. Сначала мы можем перейти к левому поддереву, затем к корню и затем к правому поддереву. Или право-корень-лево. Или корень-левый-правый.
Однако мы можем углубиться в глубину, которую часто называют поиском по глубине или поиском по ширине.
Эти два метода предназначены для обхода элементов в определенном порядке, что очень удобно для некоторых конкретных задач — по крайней мере, каждое дерево также является графиком.