Стивен Прата - Язык программирования C. Лекции и упражнения (6-е изд.) 2015

Например, в списке, состоящем из 100 элементов, первый индекс равен 0, а последний — 99, и начальным предположением является (0 + 99)/2, или 49 (целочисленное деление). Если элемент с индексом 49 располагается слишком далеко по алфавиту, искомый элемент должен находиться в диапазоне 0-48, поэтому вторым предположением становится индекс (0 + 48)/2, или 24. Если 24-й элемент в алфавитном порядке расположен слишком близко, то следующим предположением будет индекс (25 + 48)/2, или 36. Именно здесь в игру вступает возможность произвольного доступа к элементам массива. Она позволяет переходить от одного элемента к другому, не посещая все расположенные между ними элементы. Связные списки, которые поддерживают только последовательный доступ, не предоставляют средства для перехода к точке в середине списка, поэтому прием двоичного поиска нельзя применять к связным спискам.

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

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

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

Двоичное дерево поиска — это связная структура, которая включает в себя поддержку стратегии двоичного поиска. Каждый узел дерева содержит элемент и два указателя на другие узлы, называемые дочерними узлами. Связь между узлами в двоичном дереве поиска показана на рис. 17.12. Основная идея этой структуры состоит в том, что каждый узел имеет два дочерних узла — левый и правый. Порядок элементов определяется тем, что элемент в левом узле предшествует элементу в родительском узле, а элемент в правом узле следует за элементом родительского узла. Э го отношение сохраняется для всех узлов среди дочерних узлов. Более того, все элементы, чья родословная может быть прослежена до левого узла родительского узла, содержат элементы, которые предшествуют родительскому элементу, а все элементы, являющиеся потомками правого узла, содержат элементы, следующие за родительским элементом. Слова в дереве на рис. 17.12 хранятся именно таким образом. Верхняя часть дерева, в отличие от ботаники, называется корнем. Дерево представляет собой иерархическую организацию данных, т.е. данные организованы по рангам, или уровням, причем в общем случае каждому рангу соответствуют ранги, расположенные над и под ним. Если двоичное дерево поиска полностью заполнено, каждый уровень содержит вдвое больше узлов, чем уровень, расположенный над ним.

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

Расширенное представление данных 765

Например, на рис. 17.12 узлы, содержащие слова fate, carpet и llama, образуют левое поддерево всего дерева, а слово voyage является правым поддеревом поддерева style- plmum-voyage.

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

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

Давайте применим этот метод, чтобы выяснить, присутствует ли слово рирру в дереве, показанном на рис. 17.12. Сравнивая слово puppy с melon (элементом корневого узла) мы видим, что слово puppy, если оно присутствует, должно располагаться в правой половине дерева. Поэтому мы переходим к правому дочернему узлу корневого узла и сравниваем puppy со словом style. В данном случае целевой элемент предшествует элементу узла, поэтому следует двигаться по связи к левому узлу. Здесь находится слово plenum, которое предшествует слову puppy. Теперь необходимо следовать правой ветвью для этого узла, но она пуста. Таким образом, три операции сравнения позволили установить, что слово puppy в дереве отсутствует.