В ряде приложений, где не требуется быстрый поиск и удаление произвольного элемента, и где ценны дополнительные преимущества, предоставляемые структурой списка, такой выбор представляется оптимальным. Однако весьма часто от словаря требуются гораздо лучшие основные характеристики. Хорошим выбором может послужить двоичное дерево поиска. Характеристики двоичного дерева поиска: (основные операции стоят одинаково) среднее худшее время O(logn) O(n) память два указателя на каждый элемент данных Реальное время выполнения операций зависит от формы дерева. Если оно похоже на список - имеем O(n), как в списке, если на дерево - то O(log n). Можно доказать, что при последовательном включении в дерево случайных данных получается именно среднее время выполнения операций. Однако, если входные данные, например, образуют возрастающую последовательность, то получается список и все преимущество дерева потеряно. На практике двоичные деревья поиска очень удобны во многих приложениях, где входные данные случайны или есть другие причины надеяться на сохранение деревом хорошей формы. Существуют способы добиться времени O(log n) на любых входах, они полезны, но дают небольшие накладные расходы на хранение специальной информации. Есть одна задача, которая не может быть эффективно решена с помощью двоичных деревьев поиска: для заданного элемента в двоичном дереве поиска найти ближайшие больший и меньший элементы. Хотя при симметричном обходе все элементы выстраиваются в порядке увеличения, это не позволяет эффективно определить предшественника и последователя для произвольного элемента. Проблема может быть эффективно решена с помощью пополнения структуры двоичного дерева. Классическим решением являются связанные двоичные деревья поиска, которые являются двоичными деревьями поиска со связным списком, охватывающим все узлы в порядке возрастания. SpeedSIP значительно снижает расходы на телефонную связь и сервисы: бесплатные звонки внутри сети, выгодные международные и междугородные звонки, СМС по всему миру, покупка прямого номер любой страны, видеосвязь и видеоконференции. В этом разделе : 8  Двоичные деревья поиска: начальные сведения Двоичные деревья представляют эффективный способ поиска. Двоичное дерево представляет собой структурированную коллекцию узлов. 8  Cвязанные двоичные деревья поиска Связанное дерево поиска реализуем в виде класса BraidedSearchTree. Этот класс отличается от класса SearchTree из описания двоичных деревьев поиска по трем существенным признакам. 8  Обходы бинарных деревьев Существует достаточно много алгоритмов работы с древовидными структурами, в которых часто встречается понятие обхода (traversing) дерева или "прохода" по дереву. При таком методе исследования дерева каждый узел посещается только один раз, а полный обход задает линейное упорядочивание узлов, что позволяет упростить алгоритм, так как при этом можно использовать понятие "следующий" узел. т.е. узел стоящий после данного при выбранном порядке обхода.

8  Двоичные деревья поиска: начальные сведения 8  Cвязанные двоичные деревья поиска 8  Обходы бинарных деревьев