Дискретная математика (998286), страница 44
Текст из файла (страница 44)
д.). 3. Банковские счета: ключом является номер счета, а записью — финансовая информация (которая может быть очень сложной). Таким образом, ассоциативная намять должна поддерживать по меньшей мере трн основные операции: 1. добавить (ключ, запись); 2. найти (ключ): запись; 3. удалить (ключ). Эффективность каждой операции зависит от структуры данных, используемой для представления ассоциативной памяти. Эффективность ассоциативной памяти в целом зависит от соотношения частоты выполнения различных операций в данной конкретной программе. 24Т взи деревья сортировки ЗАМЕЧАНИЕ Таким образом, невозможно указать способ организации ассоциативной памяти, который оказался бы наилучшим во всех возможных случаях.
9.4.2. Способы реализации ассоциативной памяти Для представления ассоциативной памяти используются следующие основные структуры данных: 1. неупорядоченный массив; 2. упорядоченный массив; 3. дерево сортиротси — бинарное дерево, каждый узел которого содержит ключ и обладает следующим свойством: значения ключа во всех узлах левого поддерева меньше, а во всех узлах правого поддерева больше, чем значение ключа в узле; 4, таблица расслгановки (или хзш-таблица). При использовании неупорядоченного массива алгоритмы реализации операций ассоциативной памяти очевидны: 1. операция «добавить (ключ, запись)» реализуется добавлением записи в конец массива; 2.
операция «найти (ключ): запись» реализуется проверкой в цикле всех записей в массиве; -3. операция «удалить (ключ)» реализуется поиском удаляемой записи, а затем перемещением всех последующих записей на одну позицию вперед. Для упорядоченного массива имеется эффективный алгоритм поиска, описанный в следующем подразделе. Реализация остальных операций очевидна.
Основное внимание в этом разделе уделено алгоритмам выполнения операций с деревом сортировки. ОТСТУПЛЕНИЕ Таблицы расстановки являются чрезвычайно важным практическим приемом программирования, подробное описание которого выходит за рамки »того учебника.
Вкратце основная идея заключается в следуюгцем. Подбирается специальная функция, которая называется хэш-функцией, переводящая значение ключа в адрес хранения записи (адресом может быть индекс в массиве, номер кластера на диске и т. д.), Таким образом, имея ключ, с помощью хэш-функции сразу определяется место хранения записи и открывается доступ к ней. Хэш-функция подбирается таким образом, чтобы разным ключам соответствовали, по возможности, разные адреса из диапазона возможных адресов записей. Как правило, мощность множества ключей существенно больше размера пространства адресов.
которое, в свою очередь, больше количества одновременно хранимых записей. Поэтому при использовании хэшнрования возможны коллизии — ситуации, когда хэш-функцня сопоставляет один и тот же адрес двум актуальным записям с различными ключами. Различные методы хэширования отличаются друг от друга способамн разрешения коллизий и приемами вычисления хэш-функцнй. 248 Глава 9. Деревья 9.4.3. Алгоритм бинарного (двоичного) поиска При использовании упорядоченного массива для представления ассоциативной памяти операция поиска записи по ключу может быть выполнена за время 0(1ойз и) (где н — количество записей) с помощью следующего алгоритма, известного как алгоритм бинарного.
(или двоичного) поиска. Алгоритм 9.2. Бинарный поиск Вход: упорядоченный массив А: аггау [1..н] о1 гесогг1 Ьк Ьер;1: ги/о епб гесого; ключ а: Йер. Выход: индекс записи с искомым ключом а в массиве А или О, если записи с таким ключом нет, Ь: = 1 ( начальный индекс части массива для поиска ) е: = о ( конечный индекс части массива для поиска ) тг)н)е Ь К е до с: =(Ь+ е)/2 ( индекс проверяемого элемента (округленный до целого) ) К А]с].Ь > а г)геп е: = с — 1 ( продолжаем поиск в первой половине ) е1ае 1Г А]с].Ь < а ейеп Ь: =с + 1 ( продолжаем поиск во второй половине ) е1ве геспгп с ( нашли искомый ключ ) епб К епд чЬНе гесцгп О ( искомого ключа нет в массиве ) овосиование Для обоснования этого алгоритма достаточно заметить, что на каждом шаге основного цикла искомый элемент массива (если он есть) находится между (включительно) элементами с индексами Ь и е.
Поскольку диапазон поиска на каждом шаге уменьшается вдвое, общая трудоемкость не превосходит 1ок и. С) 9.4.4. Алгоритм поиска в дереве сортировки Следующий алгоритм находит в дереве сортировки узел с указанным ключом, если он там есть. Алгоритм 9.3. Поиск узла в дереве с<фтировки Вход: дерево сортировки Т, заданное указателем на корень; ключ а. Выход: указатель р на найденный узел нли пй, если в дереве нет такого ключа. р: = Т ( указатель на проверяемый узел ) нй11е р эа п11 по К а < рл' гйеп р. = рд ( продолжаем поиск слева ) е1ве Ы а > ря 1)геп Р: =Р г ( продолжаем поиск справа ) е)зе 249 9.4.
Деревья сортировки гетагп р ( нашли узел ) епй !Е епй ИЕВ!е ОБОСНОВАНИЕ Этот алгоритм работает в точном соответствии с определением дерева сортировки: если текущий узел не искомый, то в зависимости от того, меньше или больше искомый ключ по сравнению с текущим, нужно продолжать поиск слева или справа, соответственно. П 9.4.5. Алгоритм вставки в дерево сортировки Следующий алгоритм вставляет в дерево сортировки узел с указанным ключом. Если узел с указанным ключом уже есть в дереве, то ничего не делается. Вспомогательная функция Хе~Хойе описана в подразделе 9.4,7.
Алгоритм 9.4. Вставка узла в дерево сортировки Вход: дерево сортировки Т, заданное указателем на корень; ключ а. Выход: модифицированное дерево сортировки Т. В Т = пй Йеп Т: =Хен(чайе(а) ( первый узел в дереве ) гетагп Т епй ЕЕ р: = Т ( указатель на текущий узел ) М:,( анализ текущего узла ) !Е а ( рл' Йеп ЕЕ р ! = гй! Йеп 9: = !ЧеачЧойе(а) ( создаем новый узел ) рй: = 9 ( и подцепляем его к р слева ) гегшп Т еЬе р: =рй ( продолжаем поиск места для вставки слева ) доео М епй гЕ епй К В а > рл' Йеп !Е рй = ш! Йеп 9: = !чечг!чойе(а) ( создаем новый узел ) р.г: =д т и подцепляем его к р справа ) гегпгп Т еЬе р: = р.г ( продолжаем поиск места для вставки справа ) иого М епй ЕЕ епй В ге!ага Т ( сюда попали, если уже есть такой ключ! ) Глава 9.
Деревья 250 ОБОСНОВАНИЕ Алгоритм вставки, в сущности, аналогичен алгоритму поиска: в дереве ищется такой узел, имеющий свободную связь для подцепления нового узла, чтобы не нарушалось условие дерева сортировки. А именно, если новый ключ меньше текущего, то либо его можно подцепить слева (если левая связь свободна), либо нужно найти слева подходящее место.
Аналогично, если новый ключ больше текущего, П 9.4.6. Алгоритм удаления из дерева сортировки Следующий алгоритм удаляет из дерева сортировки узел с указанным ключом. Если узла с указанным ключом нет в дереве, то ничего не делается. Вспомогательные процедуры Рик1 и Ре1ете описаны в следующем подразделе. Алгоритм 9.5.
Удаление узла из дерева сортировки Вход: дерево сортировки Т, заданное указателем на корень; ключ в Выход: модифицированное дерево сортировки Т. гто(Т,а,р, е,я) ( поиск удаляемого узла ) К р = вй твеп гетега Т ( нет такого узла — ничего делать не нужно ) евй й 1г р.г = пй твеп Ве1еье(р,д,рЛ,я) ( случай 1, см. рнс. 9.11 слева ) еЬе и:=рю 11 иЛ = вй Гаев иЛ:=рЛ Ве1е1е(Р, Гь и, Я) ( слУчай 2, см. Рнс. 9.11 в центйе ) еЬе ю:=и;и:=иЛ и Ые иЛ ,-Е вй оо ю:=и;и:=иЛ евй юййе рл:=ю1 11е1е1е(и, ю, юг, -1) ( случай 3, см. рпс. 9.11 справа ) ево 11 епд 11 гегигп т ОБОСНОВАНИЕ Удаление узла производится перестройкой дерева сортировки.
При этом возможны три случая (не считая тривиального случая, когда удаляемого узла нет в дереве и ничего делать не нужно). 1. Правая связь удаляемого узла р пуста (см. рис. 9.11 слева). В этом случае левое поддерево 1 узла р подцепляется к родительскому узлу д с той же стороны, с которой был подцеплен узел р. Условие дерева сортировки, очевидно, выполняется. .«. деревья сортировки !. Правая связь удаляемого узла Р не пуста и ведет в узел и, левая связь которого пуста (см.
Рис. 9.11 в центре). В этом случае левое поддерево 1 узла р подцепляется к узлу и слева, а сам узел и подцепляется к родительскому узлу о с той же стороны, с которой был подцеплен узел р. Нетрудно проверить, что условие дерева сортировки выполняется и в этом случае. Рис. 9.11. Иллюстрация к алгоритму удаления узла из дерева сортировки 3. Правая связь удаляемого узла р не пуста и ведет в узел и, левая связь которого не пуста. Поскольку дерево сортировки конечно, можно спуститься от узла и до узла с, левая связь которого пуста (см.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
