2-3 деревья (задания) (1114536)

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла

4

2-3 деревья

1. Пустое дерево и дерево с одной вершиной являются 2-3 деревьями.

2. Каждая внутренняя вершина (не корень) имеет два или три сына.

3. Листья содержат ключи и связанную с ними информацию.

4. Все листья упорядочены слева направо в отношении строгого порядка (<). Ключ любого листа меньше его правого брата, и больше его левого.

5. В каждом внутреннем листе есть три ссылки на его сыновей (возможно nil); а также ключ наименьшего элемента, являющегося потомком его второго сына, и ключ наименьшего элемента, являющегося потомком его третьего сына.

Н апример:

рис. 1

Таким образом, 2-3 дерево с k уровнями имеет от 2^k-1 до 3^k-1 листьев. Или 2-3 дерево с n вершинами имеет не менее 1 + log₃n уровней и не более 1 + log₂n уровней. Таким образом, длина любого пути от корня до листа имеет порядок 0(log₂n).

Поиск. Пусть имеем ключ х, найдем связанную с ним информацию (она находится вместе с ключом в некотором листе). Начиная с корня, входим во внутреннюю вершину с ключами y, z (возможно nil, если сыновей нет). Если x < y, необходимо перейти к первому сыну вершины; если y ≤ x < z, то перейти ко второму; наконец, если x ≥ z, то перейти к третьему, и так до листа.

Вставка элемента. Пусть нам необходимо поместить новый элемент с ключом х.

Мы двигаемся как и при поиске до внутренней вершины, предшествующей листьям. Если эта вершина имеет 2 сыновей, (то нам повезло) добавляем третий лист с соответствующей коррекцией вершин. Заметим, однако, что эта коррекция охватывает только вершины от листа до корня (в худшем случае). Пусть мы заносим ключ 18 в дерево на рис. 1.

И меем:

рис. 2

Хуже, однако, когда пытаемся занести во внутреннюю вершину уже имеющую трех сыновей (листьев). Итак, элемент х – четвертый. Добавим его к этой вершине node. Получим четыре листа. Теперь расщепим вершину node на две: node и node¹. Два наименьших ключа войдут в node, два других – в node¹. Далее процесс продолжается к родителю node – p. Если р имела два сына, то в node¹ будет третьим с коррекцией ключей в вершинах. Если же р имела трех сыновей, то расщепляем р на р и р¹ и т.д. до корня. Корень – особый случай. В этом случае корень р расщепляем на р и р¹ и создаем новый корень с двумя сыновьями р и р¹. Количество уровней в последнем случае увеличится на 1.

Н апример: добавление ключа 10 к 2-3 дереву на рис. 2.

рис. 3

Мы расщепили эту пару. Однако нужно расщепить и родителя этой пары. Родитель – корень.

рис. 4

Итак, при занесении нового ключа может возникнуть расщепление вершин, если у родителя появилось 4 вершины (серия рисунков 2, 3, 4). Однако, посмотрим на рис. 2 при добавлении ключа 10. В вершине четыре листа, но его левый брат имеет два сына. Тогда можно отдать ему наименьший ключ. Аналогично с правым братом. Это – переливание из одной вершины в другую.

Тогда при добавлении к дереву рис. 2 ключа 10 мы получим следующее дерево:

рис. 5

Удаление:

при удалении листа его родитель node может остаться с одним сыном. Если вершина node – корень, то он остается с единственным сыном. Если же node – не корень, то пусть его родитель р. Если родитель имеет другого сына, расположенного слева или справа от node, и этот сын имеет трех сыновей – то переливание, эта вершина с тремя сыновьями отдает одного своему брату node, и обе они теперь будут иметь двух сыновей.

Если же брат node имеет двух сыновей, то сын node становится сыном брата node. Брат node теперь будет иметь трех сыновей (слияние), а вершина node освобождается.

Н апример: Удаление ключа 10 из дерева на рис. 4. За счет слияния получим:

рис. 6

Пусть теперь из дерева на рис. 6 удалим ключ 7. См. рис. 7.

рис. 7

рис. 7

ЗАДАНИЕ

Во входном текстовом файле PROCS.TXT содержится таблица со сведениями о современных микропроцессорах.

Ограничения на входные данные:

Каждая запись таблицы занимает в файле одну строку следующего вида:

ключ записи, название процессора, тактовая частота, размер кеш-памяти, частота системной шины, результат теста SPECint, результат теста SPECfp

ключ записи – натуральное число < maxint;

название процессора – строка длиной не более 30 символов (название не содержит запятых!);

тактовая частота (в ГГц) – положительное вещественное число, представимое real;

размер кеш-памяти (в Кб) – неотрицательное целое < maxint;

частота системной шины (в ГГц) – положительное вещественное число, представимое real;

результаты тестов – натуральные числа < maxint. Данные в файле записаны без ошибок.

Программа считывает содержимое файла и строит 2-3 дерево, в листьях которого содержатся записи таблицы. После этого она ждет от пользователя команду и выполняет ее.

Команды (буквы в командах латинские малые или заглавные):

L – вывести на экран вершины дерева, как определено вариантом задания. Для листовой вершины выводится ключ. Для остальных вершин выводится один ключ и символ '–' (если у вершины 2 сына), либо оба ключа (если у вершины 3 сына).

D n – (где n – ключ записи) удалить из дерева запись с ключом n, если такой записи нет, предупредить об этом пользователя;

A n – (где n – ключ записи) добавить в дерево запись с ключом n, если запись с таким ключом уже есть, предупредить об этом пользователя. Содержимое полей записи программа запрашивает у пользователя.

S – записать в файл PROCS.TXT все записи из дерева.

E – выйти из программы.

После выполнения одной команды ожидается следующая, и так до тех пор, пока не будет выполнена команда E (выход).

ВАРИАНТЫ:

В каком порядке печатать вершины (цифра варианта):

1. Печатать вершины по уровням слева направо, начиная с нижнего уровня.

2. Печатать вершины по уровням слева направо, начиная с верхнего уровня.

3. Порядок печати: левое поддерево, среднее поддерево, правое поддерево (если есть), а затем корень. Правило печати применяется рекурсивно ко всем поддеревьям в дереве.

4. Порядок печати: корень, левое поддерево, среднее поддерево, правое поддерево (если есть). Правило печати применяется рекурсивно ко всем поддеревьям в дереве.

5. См. вариант 3) + для каждой вершины выводится дополнительная информация – номер уровня дерева, на котором расположена вершина.

6. См. вариант 4) + для каждой вершины выводится дополнительная информация – номер уровня дерева, на котором расположена вершина.

Ограничения на реализацию обхода дерева при печати (буква варианта):

Р) можно использовать рекурсивные вызовы процедур и/или функций;

С) рекурсивные вызовы запрещены, использовать стек.

Пример входного файла и дерева, построенного по нему:

P ROCS.TXT

2, Intel Pentium 4, 2.0, 256, 0.400, 664, 734

5, Intel Itanium, 0.800, 96, 0.266, 365, 701

6, AMD Athlon XP, 1.6, 256, 0.266, 701, 634

1, IBM Power 4, 1.3, 16384, 0.400, 814, 1169

(Данные взяты с www.parallel.ru)

Распечатка дерева по варианту 1:

1, 2, 5, 6,

2 –, 6 –,

5 –

Распечатка дерева по варианту 3:

1, 2, 2 –, 5, 6, 6 –, 5 –

Распечатка дерева по варианту 6:

5 – (уровень 1), 2 – (уровень 2), 1 (уровень 3), 2 (уровень 3), 6 – (уровень 2), 5 (уровень 3), 6 (уровень 3)

Характеристики

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

Список файлов ответов (шпаргалок)