Двоичное дерево поиска

Двоичное дерево поиска
Тип	дерево
Год изобретения	1960
Автор	Andrew Donald Booth
Сложность в О-символике
В среднем В худшем случае Расход памяти O(n) O(n) Поиск O(log n) O(n) Вставка O(log n) O(n) Удаление O(log n) O(n)
Медиафайлы на Викискладе

В информатике двоичное дерево поиска представляет собой комбинацию абстрактных структур данных дерево поиска и двоичное дерево.

Пример двоичного дерева поиска

Двоичное дерево поиска (англ. binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):

• Оба поддерева — левое и правое — являются двоичными деревьями поиска.
• У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
• У всех узлов правого поддерева произвольного узла X значения ключей данных больше либо равны, нежели значение ключа данных самого узла X.

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

Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако это касается реализации, а не природы двоичного дерева поиска.

Для целей реализации двоичное дерево поиска можно определить так:

• Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла — левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) — ссылки на родительский элемент.
• Данные (data) обладают ключом (key), на котором определена операция сравнения «меньше». В конкретных реализациях это может быть пара (key, value) — (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
• Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], то есть ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.

Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.

Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.

Двоичное дерево поиска применяется для построения более абстрактных структур, таких, как множества, мультимножества, ассоциативные массивы.

Мотивация

Поисковые деревья-это решения так называемой“словарной проблемы". Предположим, что большое количество ключей, каждый из которых имеет значение. В словаре немецко–английский немецкое слово является ключевым, а английские слова являются значением, которое вы ищете. Аналогично ведет себя телефонная книга с именем и адресом в качестве ключа, а номер телефона-в качестве искомого значения.

Математически словарь реализует (конечную) функцию с парами (ключ, значение). При поиске ключевое слово (аргумент функции) используется для покрытия одного из ключей. В случае успеха поисковому термину присваивается добавленное значение в качестве значения функции.

В обоих примерах ключи обычно сортируются. Это очень удобно, потому что позволяет перевернуть книгу посередине и проверить, найден ли поисковый запрос. Если он не найден и находится, например, в алфавитном порядке перед буквой «К», вы также знаете, что вам не нужно сравнивать дальше назад с «L»,«M» или «Z». Часть, оставшаяся для исследования, всегда является связным сегментом, который, как и вся книга, в самом начале снова разрезается пополам – и так далее до находки или до тех пор, пока не будет установлено, что поисковый термин не встречается.

Этот подход получил в информатике название "двоичный поиск". Она воссоздана очевидным образом с помощью очень известного метода поиска „двоичный поиск в массиве". Их поведение оптимально с точки зрения информации, а именно логарифмически.

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

Изменения, входы и выходы в словарных и телефонных книгах могут быть спорадическими, в программных системах они, как правило, должны отражаться непосредственно. Входы и выходы требуют переноса данных в массиве, усилие которого пропорционально длине массива, то есть линейно в n. Такое усилие полностью снижает эффективность бинарного поиска.

Процедура поиска в двоичном формате также может быть воспроизведена с помощью двоичного дерева. Первый ключ для сравнения с поисковым термином помещается в корень двоичного дерева. Следующий ключ, который нужно найти в результате сравнения «меньше» помещается в левый дочерний узел, а соответственно ключ «больше» - в правый дочерний узел. Так продолжается до тех пор, пока все ключи не будут размещены в двоичном дереве. (Это превращает двоичное дерево в двоичное дерево поиска.)

Удаление отдельных элементов из массива обеспечивает большую гибкость: затраты на вставку для выделения пространства и загрузки полей со значениями, А также на удаление для возврата пространства не зависят от количества n элементов. Однако в двоичном дереве теряется мера баланса, заданная в массиве путем формирования среднего значения между двумя индексами. Кроме того, двоичное дерево, которое когда – то было превосходно сбалансировано, может потерять баланс путем вставки и удаления и, в крайнем случае, если у каждого узла есть только один дочерний узел (вместо двух), вырождается в линейный список, что приводит к тому, что поиск равен последовательному поиску.

Компьютерные ученые разработали различные критерии баланса для двоичных деревьев. В большинстве случаев затраты на поиск, вставку и удаление являются логарифмическими, хотя и с различными постоянными факторами.

Терминология

Понятие „сосед“ (и „окрестности“ и т. д.) используется в этой статье (и в поисковых деревьев вообще) иначе, чем обычно в теории графов, а именно смысл исключительно в порядке клеймения реляции: „правый“ сосед говорит следующий узел в восходящем направлении, „левый“ в порядке убывания.

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

Иерархическое расположение узлов в древовидной структуре дерева двоичного поиска считается вторичным и более или менее случайным – на первый план выходит правильное представление порядка.

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

С другой стороны, фиксированный адрес указателя к корню может быть принят как идентификация дерева, но значение указателя затем также поддерживается операциями дерева.

Отношение порядка

Индуцированное отношение порядка < - строгий слабый порядок, в английском языке strict weak ordering. Она индуцирует строгий тотальный порядок на классах эквивалентности этой реляции, точнее-на классах эквивалентности дублирующей реляции.

Очевидно, каждый такой порядок можно отразить, т. е. +1 с -1 поменять местами, результат снова строгий слабый порядок. Добрососедские отношения сохранятся.

Примечания:

Для чистого поиска в основном достаточно 2-полосной функции сравнения, которая указывает, равны ли два "ключа" или нет. Но при такой функции сравнения эффективные, например, в средне-логарифмические, часы поиска недоступны.

Для работы сортировки и двоичного поиска не имеет значения, является ли разделение неравного пути 2-ходовой функции сравнения на меньшее и большее пути артефактом, например, расположение букв в алфавите, или же в игре есть более близкая/дальняя или логическая связь.

Если отношение порядка также отражает соседство, оно может быть использовано для эффективного „нечеткого поиска“.

Узел-ориентированное хранилище точно соответствует поиску с 3-полосной функцией сравнения.

Основные операции в двоичном дереве поиска

Базовый интерфейс двоичного дерева поиска состоит из трёх операций:

• FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
• INSERT(K, V) — добавление в дерево пары (key, value) = (K, V).
• REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.

Этот абстрактный интерфейс является общим случаем, например, таких интерфейсов, взятых из прикладных задач:

• «Телефонная книжка» — хранилище записей (имя человека, его телефон) с операциями поиска и удаления записей по имени человека и операцией добавления новой записи.
• Domain Name Server — хранилище пар (доменное имя, IP адрес) с операциями модификации и поиска.
• Namespace — хранилище имён переменных с их значениями, возникающее в трансляторах языков программирования.

По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.

Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.

Поиск элемента (FIND)

Дано: дерево Т и ключ K.

Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.

Алгоритм:

• Если дерево пусто, сообщить, что узел не найден, и остановиться.
• Иначе сравнить K со значением ключа корневого узла X.
  • Если K=X, выдать ссылку на этот узел и остановиться.
  • Если K>X, рекурсивно искать ключ K в правом поддереве Т.
  • Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Добавление элемента (INSERT)

Дано: дерево Т и пара (K, V).

Задача: вставить пару (K, V) в дерево Т (при совпадении K, заменить V).

Алгоритм:

• Если дерево пусто, заменить его на дерево с одним корневым узлом ((K, V), null, null) и остановиться.
• Иначе сравнить K с ключом корневого узла X.
  • Если K>X, рекурсивно добавить (K, V) в правое поддерево Т.
  • Если K<X, рекурсивно добавить (K, V) в левое поддерево Т.
  • Если K=X, заменить V текущего узла новым значением.

Удаление узла (REMOVE)

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм:

• Если дерево T пусто, остановиться;
• Иначе сравнить K с ключом X корневого узла n.
  • Если K>X, рекурсивно удалить K из правого поддерева Т;
  • Если K<X, рекурсивно удалить K из левого поддерева Т;
  • Если K=X, то необходимо рассмотреть три случая.
    • Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
    • Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
    • Если оба ребёнка присутствуют, то
      • Если левый узел m правого поддерева отсутствует (n->right->left)
        • Копируем из правого узла в удаляемый поля K, V и ссылку на правый узел правого потомка.
      • Иначе
        • Возьмём самый левый узел m, правого поддерева n->right;
        • Скопируем данные (кроме ссылок на дочерние элементы) из m в n;
        • Рекурсивно удалим узел m.

Обход дерева (TRAVERSE)

Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.

Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f, операндом которой является адрес узла. Эта функция обычно работает только с парой (K, V), хранящейся в узле. Операция INFIX_TRAVERSE может быть реализована рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.

• INFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево). Элементы по возрастанию
• PREFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево). Элементы, как в дереве
• POSTFIX_TRAVERSE (tr) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево', вершина). Элементы в обратном порядке, как в дереве

В других источниках эти функции именуются inorder, preorder, postorder соответственно

INFIX_TRAVERSE

Дано: дерево Т и функция f

Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей

Алгоритм:

• Если дерево пусто, остановиться.
• Иначе
  • Рекурсивно обойти левое поддерево Т.
  • Применить функцию f к корневому узлу.
  • Рекурсивно обойти правое поддерево Т.

В простейшем случае функция f может выводить значение пары (K, V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующем описанию дерева, приведённого в начале статьи.

Разбиение дерева по ключу

Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами <K₀ и ≥K₀.

Объединение двух деревьев в одно

Обратная операция: есть два дерева поиска, у одного ключи <K₀, у другого ≥K₀. Объединить их в одно дерево.

У нас есть два дерева: T₁ (меньшее) и T₂ (большее). Сначала нужно решить, откуда взять корень: из T₁ или T₂. Стандартного метода нет, возможные варианты:

• Взять наугад (см. декартово дерево).
• Если в каждом узле дерева поддерживается размер всей ветви (см. дерево с неявным ключом), легко можно оценить дисбаланс для того и другого варианта.

алг ОбъединениеДеревьев(T1, T2)
если T1 пустое, вернуть T2
если T2 пустое, вернуть T1
если решили сделать корнем T1, то
  T = ОбъединениеДеревьев(T1.правое, T2)
  T1.правое = T
  вернуть T1
иначе
  T = ОбъединениеДеревьев(T1, T2.левое)
  T2.левое = T
  вернуть T2

Балансировка дерева

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

В вырожденном случае может оказаться, что всё левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Поиск (а значит, и удаление и добавление) в таком дереве по скорости равен поиску в списке и намного медленнее поиска в сбалансированном дереве.

Для балансировки дерева применяется операция «поворот дерева». Поворот налево выглядит так:

• было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R
• поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R
• также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.

Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно. Достаточно очевидно, что поворот не нарушает упорядоченность дерева и оказывает предсказуемое (+1 или −1) влияние на глубины всех затронутых поддеревьев. Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как «красно-чёрное дерево» и АВЛ. Оба они требуют дополнительной информации в узлах — 1 бит у красно-чёрного или знаковое число у АВЛ. Красно-чёрное дерево требует не более двух поворотов после добавления и не более трёх после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого). АВЛ-дерево требует не более двух поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1).

Вставка

Предположим, что навигация к точке вставки уже выполнена. Точка вставки означает узел и направление (вправо или влево). Прямая точка вставки в бинарное дерево правый (или левый) всегда наполовину листа (т. е. без узлов правой (или левой) малыш узлы) вместе с этом направлении. (В представлении рис. 1B это точно соответствует внешнему узлу, адреса которого, однако, должны быть разными, и, например. не должны быть реализованы как Sentinel.) Посредник является непосредственным соседом в указанном направлении и вместе с противоположным указывает то же место в двоичном дереве – но для реальной вставки функция вставки должна еще спуститься до половины листа, представляющего собой непосредственную точку вставки. Приведенные выше функции Find, FindDupGE и FindDup обеспечивают (немедленную) точку вставки (Find не на „Equal“) в результате.

Чтобы вставить, нужно указать ближайшую точку вставки на новый элемент, чтобы он был правильно вставлен в соответствии с общим Квазиупорядочением. Таким образом, сложность операции вставки (без операции поиска) постоянна. При добавлении операции поиска (как это часто встречается в литературе) она доминирует над сложностью.

После вставки новый элемент является листом дерева поиска.

Повторная вставка ключей, отсортированных по возрастанию (или по убыванию), может привести к тому, что дерево вырождается в линейный список.

Реализация

Итеративное Программирование

В литературе операции часто представлены в рекурсивном программировании. Тем не менее, пользователь имеет ряд преимуществ, если реализатор заменил рекурсии с помощью простых итераций, поскольку это экономит вызовы и отступы процедур h (высота) и сохраняет постоянную память для стека программ. Но дело не только в экономии ресурсов. Например, операция обхода значительно упрощает Программирование приложения. Для сохранения обратного пути к корню и головке, который используется при обходе, а также часто для модификаций для поддержания изменений дерева (критерий AVL или красно - черный), и который находится в рекурсивном программировании, помимо прочего, в памяти программы, необходимо выбрать другую, явную конструкцию, которая может быть суммирована в курсоре.

Это позволяет отделить модифицирующие операции от навигации.

Отделение навигационных от модифицирующих операций

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

Такая Модуляризация навигационных от модифицирующих операций освобождает при необходимости подлогарифмические усилия последних, ибо подъем до корня, например, у дерева AVL и дерева красно-черного, необходим лишь в исключительных случаях. В приложениях с сильной последовательной долей это может положительно повлиять на время выполнения.

Курсор

При поиске создается пара (узел, направление), которая подходит для указания точки вставки при вставке. При удалении узел, который необходимо удалить, называется компонентом узла, и компонент направление может указать, куда курсор должен двигаться после удаления. При обходе узел указывает отправную точку и направление, необходимое направление навигации, чтобы в результате вернуться к такой паре. Таким образом, все важные операции создают и/или потребляют конструкцию, которая (по аналогии, например, с базами данных) называется курсором.

Критерии отбора

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

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

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

Важным критерием для выбора является то, является ли двоичное дерево статическим, что обеспечивает оптимальное построение, или же важны такие изменения, как вставка и удаление. Для первых рассмотрены взвешенные деревья поиска, среди которых также алгоритм Беллмана. Для последних интерес представляют деревья поиска, сбалансированные по высоте, такие как дерево AVL и красно-черное дерево, но также и деревья склеивания.

Сопоставление сложностей различных алгоритмов поиска можно найти в статье дерево поиска; измерения времени выполнения на основе реалистичных примеров можно найти в Pfaff 2004b.

При этих соображениях обычно считалось, что все дерево находится в оперативной памяти (основной памяти). Если доступ к внешним носителям имеет значение, к нему добавляются совершенно другие критерии. Уже B-дерево, которое учитывает такие точки зрения, хотя и является деревом поиска, но уже не двоичным.

Немного истории

Очень известная структура поиска бинарный поиск в массиве, упомянутая в разделе мотивация, считается предшественником дерева динамического поиска. Как очевидная реализация справочника в (отсортированном) словаре, он, вероятно, был разработан и реализован несколько раз и без знания других реализаций. Но в динамическом случае использования он не может конкурировать с новыми разработками, хотя в статическом случае он является отличным решением. Существуют макросы, которые заставляют компилятор генерировать исходный код в заданную (отсортированную) таблицу пар (ключей, значений) для итерационного или циклического двоичного поиска.

В 1962 году впервые появилось динамическое дерево поиска в виде дерева AVL. Его изобретателями являются советские математики Георгий Адельсон-Вельский и Евгений Ландис. Ее сообщение в журнале Доклады Академия Наук СССР было переведено на английский язык в том же году. Перевод носит (как и в оригинале) весьма амбициозное название “An algorithm for the organization of information". Название дерева AVL не встречается в этом переводе.

В 1970 году Рудольф Байер опубликовал свою первую работу о дереве Б. Оно не является двоичным деревом, поддерживает разнородные хранилища, такие как основная память и фоновая память, и используется в системах баз данных.

Splay деревья были представлены в 1985 году Даниэль Слиатор и Робертом Тарьян под названием „Самонастраивающиеся Бинарные Деревья Поиска“. Они еще более динамичны, чем вышеупомянутые, изменяясь и в ходе поисковых операций.

См. также

• Ассоциативный массив
• Декартово дерево
• Сортировка с помощью двоичного дерева
• Список структур данных (деревья)

Сбалансированные деревья:

• B-дерево
• АВЛ-дерево
• Красно-чёрное дерево

Ссылки

• Binary Tree Visualizer (JavaScript animation of various BT-based data structures)