Структуры данных и модели вычислений

         

Общие сведения


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

  • Search — поиск элемента с заданным ключом.
  • Minimum — поиск элемента с минимальным ключом.
  • Maximum — поиск элемента с максимальным ключом.
  • Predecessor — поиск элемента с предыдущим ключом.
  • Successor — поиск элемента со следующим ключом.
  • Insert — вставка элемента со своим ключом.
  • Delete — удаление указанного элемента.

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

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

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



Содержание    Вперед