Д. Кнут - Искусство программирования том 3 (2-е издание) - 2001 (Часть 2) (1119371), страница 53
Текст из файла (страница 53)
Н!пг!сЬв, ВГГ 25 (1985), 569-592). Характеристики сеточных файлов со случайными данными проанализированы в работах М. Йвйп!ег, ВГХ 25 (1985), 335-357; Р. Р!а)о!е! апб С. РцесЬ, зАСМ 33 (1986), 371-407, 14.2. Прн простол1 способе работы с ортогональнымн запросами диапазонов, предложенном Дж. Л, Бентли (3. Б. Вепг!еу) н Р. А. Финкелем (Н. А.
Р!и!се!), используются структуры, которые назьяваютсл чеглрсесмьмие (биа41геее) (Асга 1пуогщас!са 4 (1974), 1-9). В двумерном случае каждый узел такого дерева представляет прямоугольник и содержит одну нз точек в этом прямоугольнике. Имеется четыре поддерева, соответствующих четырем квадрантам исходного прямоугольника относительно координат данной точки. Аналогично для трех измерений существует восьмипутевое ветвление, и деревья соответственно называются еосьмиревьями (ос!геев). й-мерные четревья, естественно, порождаются ветвлением по 2 путям. е Математический анализ случайных четревьев является весьма сложным, однако в 1988 году независимо двумя группами исследователей (1..
Оеугоуе апд 1,. 1,а(огеэс, * Переводя хекяе термины, поневоле чувствуешь себя Алксей в Звэерквлье, слушыошей объясяевяе Шелтая-Болтвя о слсжвх, похожих яв бумажник; открышюшь его, в твм двв отделеявя. Надеюсь, читатель простят яе слишком научно звучащие, зато оживляющие сухой текст термввы. — Прель верее. Б1СОМР 19 (1990), 821-832; Р. Р1а)о!ег, О. Сопле!„С. РпесЬ, апг! 3.
М. ВоЬзоп, А!лоПГЬппса 10 (1993), 473-500) была определена асимптотическая форма ожидаемого времени вставки Ж-го узла в случайное й-мерное четрево: — 1и Х+ О(1). 2 й (3) Обратите внимание, что при й = 1 этот результат согласуется с хорошо известной формулой для вставки в бинарное дерево поиска 6.2.2-(5). Дальнейшие разработки Ф. Флажоле (Р. Г!а)о!ег), Ж. Лабелля (С.
1аЬейе), Л. Лафоре (Ь. Ьа(огеэг) и Б. Салли (В. Ба!ху) показали, что в действительности средняя внутренняя длина пути может быть выражена в удивительно элегантной форме." (4) Таким образом, дальнейший анализ случайных четревьев возможен при помощи гипергеометрических функций (см. Влас(ош Бггисгпгеэ апд А)яопгИшэ 7 (1995), 117-144]. Бентли (Вепг!еу) еще болыпе упростил представления четревьев, введя "Й-ф деревья" (1-г! !геев), которые имеют только двойное ветвление в каждом узле [САСМ 18 (1975), 509-517; ЖЕЕ Тгапласг!опз ЯЕ-5 (1979), 333-340), 1-фдерево представляет собой обычное бинарное дерево поиска, рассмотренное в разделе 6,2.2.
2-~1-дерево подобно ему, но при ветвлении на четных уровнях сравниваются координаты х, а на нечетных — у. В общем случае Ь-фдерево имеет узлы с й координатами и ветвление на каждом уровне базируется на сравнении одной из координат. Например, на уровне ! происходит ветвление по координате (Йшог(!) + 1. Для гарантии того, что никакие две записи не будут иметь никаких озвпадающих координат.
можно использовать правило разрыва узлов (г(е-ЬгеаЫпй), основываясь на номерах записей или их положении в памяти компьютера. Случайно растущее й-фдерево будет иметь то же значение средней длины пути и то же распределение ветвей, что и обычное бинарное дерево поиска, потому что предположения, лежащие в основе их роста, те же, что и в одномерном случае (см, упр. 6.2.2-6). Если файл не изменяется динамически, можно сбалансировать любое Й-д-дерево с Ж узлами так, чтобы его высота составляла ю )8 Ю, выбрав среднее значение для ветвления в каждом узле. После этого можно быть уверенным в эффективности обработки запросов различных фундаментальных типов. Например, Бентли доказал, что можно найти все записи, имеющие г определенных координат, за О(Х 7 ) шагов.
Кроме того, можно найти все записи, лежащие в заданной прямоугольной области, не более чем за 0(!Х' '~а+ о) шагов, если всего имеется о таких записей, а Г координат лежат в некоторых подобластях (О. Т. Ьее апг! С. К, %опй, АсГа 1п!Ьггпаг!са 23 (1977), 23-29). В действительности, если данная область близка к кубической и д малб и если выбранные для ветвления координаты в каждом узле имеют наибольший разброс значений атрибутов, то, как показано в работе Рг!ейпап, Вел!!еу, апб Г!пйе1, АСМ Т!апа Магй. Бог!кате 3 (1977), 209 — 226, среднее время обработки запроса к такой области будет составлять всего лишь О(!ой !!! + д).
Эта же формула применима прн поиске в таком Й-Й-дереве ближайших соседей данной точки в Й-мерном пространстве. При использовании случайных, а не идеально сбалансированных А-с(-деревьев среднее время работы для частичных совпадений по 1 определенным координатам несколько увеличивается до 8(Х' '~"+70~э!). Функция 7' неявно определяется уравнением (Дх) + 3 — х) * (!'(х) + 2 — х) ' * = 2 (5) и весьма мала: имеем 0 <,1(х) < 0.06329 33881 2373885718 1401 1 27797 33590 58170-. (6) При этом максимум достигается при х, близком к 0.585371 (см.
Р. Р!а1о!ес апс! С. Рцес!с, ХАСМ 33 (1986), 371-407, 13). Рост популярности геометрических алгоритмов (и их эстетическая привлекательность) вызвали ускоренное развитие технологий решения многомерных задач и смежных вопросов разных видов. Фактически в 70-х годах появилось новое направление в математике и информатике, именуемое вычислительной геометрией.
Отличным справочным пособием, в котором подробно излагается текущее состояние дел в этой отрасли знаний, является Нале(!юок ос ПЬсгесе алс) Сопэрлсабалз1 Сеошесгу под редакцией д. В. Спас!лсап алс! 1. Р'Воцг1се (Васа Иасап, Г!агЫа: СВС Ргезз, 1997). Всесторонний обзор структур данных и алгоритмов для важных случаев двухи трехмерных объектов можно найти в двух взаимодополняющих книгах Хапала Самета (Напал Башес) ТЬе Пез!Ял алд Апа!уз!з оГ Брала! Паса Бсгоссцгез и Аррйсас!олз оГ Брас!а! Паса Бсхлссигез (Ас!6!зол-Ууез!еу, 1990). Самет обратил внимание на то, что исходные четревья Вентли и Финкеля более корректно было бы именовать "точечными четревьями" (ро!пс ссцас1сгеез). Название четревьл теперь стало общим термином для любой иерархической декомпозиции геометрических данных. Составные атрибуты. Два или более атрибутов могут быть скомбинированы в один суператрибут.
Например, атрибут "(КУРС, СПЕЦИАЛИЗАЦИЯ)" может быть создан путем комбинирования полей КУРС и СПЕЦИАЛИЗАЦИЯ в университетском файле регистрации. Таким образом, запрос зачастую можно выполнить, объединяя короткие списки вместо пересечения длинных. Идея комбинирования атрибутов была развита В. Ю. Луман (1'. У. Ьлпс) (САСМ 13 (1970), 660-665), который предложил упорядочение инвертированных списков комбинированных атрибутов в лексикографическом порядке слева направо и создание нескольких копий с перестановкой индивидуальных атрибутов надлежащим способом.
Например, предположим, что имеется три атрибута — А, В и С. Можно сформировать составные атрибуты (А,В,С), (В,С,А), (С,А,В) (7) и построить упорядоченные инвертированные списки для каждого из них. (Так, в первом списке записи упорядочены по их значениям А; записи с одинаковыми значениями А упорядочены по значениям В, а затем — по С.) Такая организация позволяет выполнять запросы, основанные на комбинации этих трех атрибутов; например, все записи, имеющие определенные значения А и С, будут располагаться в третьем списке последовательно.
Аналогично из атрибутов А, В, С и 0 можно сформировать шесть составных атрибутов: (А, В, С, 0), (В, С,0, А), (В, О, А, С), (С, А, О, В), (С,0, А, В), (О, А, В, С). (8) Они позволяют выполнять все комбинации простых запросов с фиксированными значениями одного, двух, трех или четырех атрибутов, Существует общая процедура построения (") комбинированных атрибутов из и отдельных атрибутов при А < -и, такая, что все записи, имеющие определенные комбинации не более чем из А или не менее и- Й значений атрибутов, будут последовательно расположены в одном из списков комбинированных атрибутов (см.
упр. 1). Можно обойтись и меньшим количеством комбинаций, если некоторые атрибуты имеют ограниченное множество значений. Например, если 0 представляет собой атрибут с двумя возможными значениями, то комбинации (В) (0,А,В,С), (0,В,С,А), (0,С,А,В), полученные в результате помещения 0 в (7), будут так же хороши, как и (В), с половинной избыточностью, поскольку запросы, не зависящие от О, могут быть обработаны путем просмотра в двух местах одного из списков.
Бинарные атрибуты. Поучительно рассмотреть частный случай, когда все атрибуты могут иметь только два значения. По сути, это противоположносшь комбинированных атрибутов, поскольку любое значение можно представить как двоичное число и рассматривать индивидуальные биты этого числа как отдельные атрибуты. В табл. 1 показан типичный файл с атрибутами "Да"-"Нет'! В этом примере записи содержат рецепты домашнего печенья, а атрибуты определяют используемые ингредиенты. Например, миндальные вафли с ромом сделаны из масла, муки, молока, орехов и сахарного песка.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
