Cтраница 4
Для того чтобы в дереве бинарного поиска выписать все имена в естественном порядке, мы просто используем симметричный порядок обхода бинарных деревьев ( см. разд. [46]
Найдите значения N, для которых бинарный поиск в таблице символов размером TV становится в 10, 100 и 1000 раз быстрее последовательного поиска. Предскажите значения аналитически и проверьте их экспериментально. [47]
Несмотря на простоту идеи, реализовать бинарный поиск без ошибок не так просто. [48]
Итак, и последовательный, и бинарный поиск имеют и свои достоинства и недостатки. Выигрыш в скорости при бинарном поиске достигнут, образно говоря, за счет того, что мы пожертвовали добавлением и удалением, которые теперь стали массовыми. Кроме того, несмотря на жертвы, сам бинарный поиск также остался массовой операцией - количество действий с вектором по-прежнему зависит от п, хотя теперь эта зависимость логарифмическая, а не линейная. Естественно, возникает вопрос: а существует ли вообще реализация множества, при которой поиск не является массовой операцией. [49]
Реализуйте нерекурсивную функцию вставки в RB-дерево бинарного поиска ( см. программу 13.6), которая соответствует вставке в сбалансированное 2 - 3 - 4-де-рево в течение одного прохода. Совет: введите связи gg, g и р, которые указывают, соответственно, на прадеда, деда и родителя текущего узла в дереве. Все эти связи могут Потребоваться для выполнения двойной ротации. [50]
Мы заинтересованы в отыскании оптимального дерева бинарного поиска над множеством имен с данными частотами. [51]
Мы уже видели, как при бинарном поиске определяются направление дальнейшего просмотра и ячейка рубежа для следующего обращения. При этом на каждом шаге необходимо выполнить определенный объем вычислений. Рассмотрим теперь организацию файла, при которой промежуточные вычисления не требуются, поскольку направление просмотра при поиске определяется с помощью указателей. [52]
Если в таблице присутствуют дублированные ключи, бинарный поиск можно расширить до поддержки операций на таблице символов для подсчета количества элементов с данным ключом или возврата их в виде группы. Несколько элементов, ключи которых совпадают с искомым, образуют в таблице непрерывный блок ( поскольку таблица упорядочена), и в программе 12.7 успешный поиск завершится где-то внутри этого блока. Если приложению требуется доступ ко всем элементам подобного рода, в программу можно добавить код для выполнения просмотра в обоих направлениях от точки завершения поиска, а также код для возврата двух индексов, ограничивающих элементы, ключи которых равны искомому ключу. [53]
Если для определения второго рубежа применяется алгоритм бинарного поиска, то результат его работы зависит от результата сравнения искомого ключа с ключом Макс. При конструировании дерева рассматриваются оба возможных результата и ищутся оба рубежа. [54]
Алгоритм 6.7 использует немногие свойства оптимальных деревьев бинарного поиска: фактически только специальный вид выражений в правой части присваивающего предложения зависит от свойств деревьев. Ключом к такому улучшению является теорема, доказательство которой выходит за пределы этой книги. Согласно этой теореме, самый внутренний цикл ( по К) выполняется не / - i раз, как мы предположили при анализе алгоритма 6.7, а меньше. [55]
В разделах 12.5 - 12.9 рассматриваются деревья бинарного поиска, которые обеспечивают определенную гибкость в том, что время поиска и вставки становится пропорциональным IgW, но только в среднем. В главе 13 будут исследоваться деревья типа красное черное ( red-black tree) и рандомизованные деревья бинарного поиска, которые, соответственно, гарантируют логарифмическую зависимость времени от количества элементов либо существенно увеличивают вероятность этого. В главе 14 изучаются вопросы хеширования, которое в среднем обеспечивает постоянство времени поиска и вставки, но не обеспечивает эффективную поддержку операции sort и ряда других операций. В главе 15 будут рассматриваться методы поразрядного поиска, которые аналогичны методам поразрядной сортировки, описанным в главе 10; в главе 16 исследуются методы, применимые к файлам, которые хранятся внешне. [56]
Разработайте реализацию таблицы символов, в которой используется бинарный поиск и ленивая вставка, а также поддерживаются операции construct, count, search, insert и sort, прибегнув к следующей стратегии. [57]