А. Шень ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание седьмое, дополненное Москва
жүктеу/скачать 1,66 Mb. Pdf көрінісі
|
теория
разделителями для 𝑘 + 1 поддеревьев. Пусть фиксировано некоторое число 𝑡 > 1. Будем рассматривать деревья, обладающие такими свойст- вами: 1) Каждая вершина содержит от 𝑡 до 2𝑡 элементов (за исключени- ем корня, который может содержать любое число элементов от 0 до 2𝑡). 2) Вершина с 𝑘 элементами либо имеет 𝑘 + 1 сыновей, либо не имеет сыновей вообще (является листом). 3) Все листья находятся на одной и той же высоте. 14.2. Сбалансированные деревья 267 Добавление элемента происходит так. Если лист, в который он по- падает, неполон (т. е. содержит менее 2𝑡 элементов), то нет проблем. Если он полон, то 2𝑡 + 1 элемент (все элементы листа и новый элемент) разбиваем на два листа по 𝑡 элементов и разделяющий их серединный элемент. Этот серединный элемент надо добавить в вершину предыду- щего уровня. Это возможно, если в ней менее 2𝑡 элементов. Если и она полна, то её разбивают на две, выделяют серединный элемент и т. д. Ес- ли в конце концов мы захотим добавить элемент в корень, а он окажет- ся полным, то корень расщепляется на две вершины, а высота дерева увеличивается на 1. Удаление элемента, находящегося не в листе, сводится к удалению непосредственно следующего за ним, который находится в листе. По- этому достаточно научиться удалять элемент из листа. Если лист при этом становится слишком маленьким, то его можно пополнить за счёт соседнего листа | если только и он не имеет минимально возможный размер 𝑡. Если же оба листа имеют размер 𝑡, то на них вместе 2𝑡 эле- ментов, вместе с разделителем | 2𝑡 + 1. После удаления одного эле- мента остаётся 2𝑡 элементов | как раз на один лист. Если при этом вершина предыдущего уровня становится меньше нормы, процесс по- вторяется и т. д. 14.2.7. Реализуйте описанную схему хранения множеств, убедив- шись, что она также позволяет обойтись 𝐶 log 𝑛 действий для операций включения, исключения и проверки принадлежности. 14.2.8. Можно определять сбалансированность дерева иначе: требо- вать, чтобы для каждой вершины её левое и правое поддеревья имели не слишком сильно отличающиеся количества вершин. (Преимущество такого определения состоит в том, что при вращениях не нарушается сбалансированность в вершинах, находящихся ниже точки вращения.) Реализуйте на основе этой идеи способ хранения множеств, гаранти- рующий оценку в 𝐶 log 𝑛 действий для включения, удаления и проверки принадлежности. [Указание. Он также использует большие и малые вращения. По- дробности см. в книге Рейнгольда, Нивергельта и Део «Комбинаторные алгоритмы».] 15. КОНТЕКСТНО-СВОБОДНЫЕ ГРАММАТИКИ 15.1. Общий алгоритм разбора Чтобы определить то, что называют контекстно-свободной грам- матикой (КС-грамматикой), надо: • указать конечное множество 𝐴, называемое алфавитом; его эле- менты называют символами; конечные последовательности сим- волов называют словами (в данном алфавите); • жүктеу/скачать 1,66 Mb. Достарыңызбен бөлісу:
|