Основная причина использования бинарного дерева поиска заключается в том, что оно расширяет возможности обычного массива.

Массив — это тип данных, в котором точки данных хранятся в непрерывной последовательности. Каждый элемент в массиве имеет индекс, и таким образом к ним можно получить очень быстрый доступ, например, с помощью A[0] для получения первого элемента или A[103] для 104-го элемента. Массивы имеют доступ за постоянное время или O(1). (Подробнее об обозначении Big O здесь.)

Но хотя индексирование придает массиву силу, оно также является и его слабостью.

Например, если вы хотите добавить элемент в существующий массив длиной 100 на 50-й позиции, вам придется обновить индекс элементов в позициях 50–100 (добавляя 1 к каждой из них). Это происходит за кулисами. В худшем случае, как в случае добавления нового элемента в начало массива, это будет операция с линейным временем (временная сложность O(n)).

var foodArray = ['hollandaise', 'fish', ..., 'cracker'];
console.log(foodArray.length);  // 100

foodArray.splice(50, 0, 'egg');
console.log(foodArray.length);  // 101

Когда приведенный выше фрагмент кода выполняется, все элементы после вновь вставленного элемента должны быть повторно проиндексированы. Эта операция времени O(n) не очень медленная, но другая структура данных (угадайте, какая?) может работать лучше.

Двоичное дерево поиска не хранит индекс своих элементов данных. Вместо этого он полагается на свою неявную структуру (слева или справа от каждого узла), чтобы вести учет того, где находится каждый элемент. Результатом является вставка и удаление за логарифмическое время, или O(log n).

Вот как звучит красноречивый ответ на Quora:

Двоичное дерево поиска «может эффективно поддерживать динамически изменяющийся набор данных в отсортированном порядке для некоторого «сортируемого» типа».

Я описываю это в своей голове как подход «всегда вставлять в нужное место». Этот подход гарантирует, что мы можем выполнять бинарный поиск по всему бинарному дереву поиска в любое время без необходимости что-либо переупорядочивать.

Из-за этой структуры вставка и удаление узлов могут быть достигнуты очень быстро. Вместо последовательного обхода каждого элемента до тех пор, пока не будет найден нужный, как мы работаем с массивами, нам нужно пройти только половину дерева, затем половину половины дерева, затем половину половины половины дерева… Я думаю, вы получите изображение — в результате вставка/удаление выполняется намного быстрее, чем массив, и почти ни один из недостатков. Очень скоро мы коснемся основной слабости BST.

Итак, каковы некоторые варианты использования? Основной вариант использования, который я считаю подходящим, — это индексация записей базы данных. Если в вашей базе данных есть таблица пользователей с 1 миллионом записей, и вам нужно найти пользователя с электронной почтой [email protected], вы можете добраться туда с помощью сбалансированного двоичного дерева поиска не более чем за 21 итерация.

Если бы это был массив, отсортированный по строке электронной почты (если бы он был отсортирован), вероятно, все равно потребовалась бы 1/5 миллиона итераций, чтобы добраться до электронных писем, начинающихся с «h». Это 21 против 200 000.

Основная слабость бинарного дерева поиска

Ранее я упоминал о «сбалансированном» бинарном дереве поиска. Давайте разберем эту идею сейчас.

Бинарное дерево поиска может выйти из равновесия. Это первое, что нужно понять о бинарном дереве поиска.

Например, если мы попытаемся вставить следующий отсортированный массив в двоичное дерево поиска, мы получим сильно несбалансированное дерево.

[1, 3, 4, 7, 10, 13]

… в результате получится дерево, похожее на это…

Некрасивость — не единственная проблема такого дерева — производительность, как вы понимаете, тоже будет негативно сказываться.

Например, для поиска по такому дереву нам пришлось бы последовательно пройти практически все узлы. В этой ситуации, которая является наихудшим сценарием бинарного дерева поиска, мы могли бы также использовать обычный массив!

Это интересно — некоторые называют ужасно несбалансированное дерево «дегенеративным». Чем больше несбалансированность, тем более он вырожден и тем ближе он ведет себя как массив.

Вот почему необходим механизм для балансировки дерева. Думайте об этом как о регуляторе, гарантирующем, что дерево будет реорганизовано так, что мы никогда не получим дерево, тяжелое слева или справа.

Чем более сбалансирована древовидная структура, тем быстрее выполняется поиск, вставка и удаление элементов — основное преимущество использования структуры данных двоичного дерева поиска.

В следующем (будущем) посте мы рассмотрим, как создать самобалансирующееся дерево.

Резюме

  • BST будет работать только при сохранении сортируемого типа данных (?)
  • BST может искать, получать доступ, вставлять и удалять элементы данных за логарифмическое время O(log n)
  • BST намного быстрее, чем массив при поиске, вставке и удалении (O(log n) против O(n))
  • BST немного медленнее, чем массив при доступе (O(log n) против O(1))
  • Основная слабость BST заключается в его склонности к дисбалансу, если его не регулировать каким-либо самобалансирующимся механизмом.

Чтобы узнать больше о подобных сообщениях, ознакомьтесь с разделом Программирование размера прикуса. Если вы хотите получать самые интересные посты из этого блога, подпишитесь, и я буду присылать вам еженедельный кураторский список прямо на ваш почтовый ящик. Это бесплатно. До скорой встречи!

Первоначально опубликовано на сайте Nick Ang.