Включение и исключение в дереве

Рассмотрим некоторые особенности операций включения и исключения в любом m‑арном дереве.

9.5.1 Включение в дереве

Включаемым в дерево объектом является некоторое (другое) дерево, которое затем станет поддеревом. При выполнении операции включения должны быть заданы:

1) включаемое поддерево (т. е. в памяти должна существовать соответствующая древовидная структура),

2) та вершина исходного дерева, к которой «подвешивается» в качестве ветви включаемое дерево и

3) индекс, назначаемый поддереву и определяющий старшинство его корня среди сыновей вершины подключения.

В результате операции включения поддерева Y в вершину Х исходного дерева степень исхода вершины Х увеличивается на единицу и у этой вершины появляется еще один сын. При этом в общем случае потребуется заново перенумеровать вершины-сыновья узла X.

9.5.2 Исключение в дереве

Исключаемым объектом, применительно к произвольному дереву, является некоторое поддерево. В операции исключения следует указать вершину исходного дерева, играющую роль корня исключаемого поддерева, и номер (или индекс) исключаемого поддерева, поскольку одна вершина в зависимости от ее степени исхода может играть роль корня для разных поддеревьев.

Пусть Х - некоторая вершина произвольного дерева, а вершины, Y₁ ..., Y_n - ее сыновья. Тогда исключение i-ого поддерева вершины Х означает уменьшение степени исхода Х на единицу и удаление из исходного дерева ветви Х ® Y_i , и поддерева, корнем которого служит вершина Y_i. В результате такого удаления вершина Х может стать листом.

Поиск

10.1 Поиск: определение и общая терминология

Любая таблица (словарь) содержит информацию, которая может быть полезна при решении каких-либо информационных задач. Часто для решения задачи требуется не вся содержащаяся в таблице информация, а лишь несколько записей или даже одна запись. И для того чтобы получить доступ к требуемой записи, необходимо ее найти, т. е. выполнить поиск в таблице.

Дадим определение. Поиск (searching, retrieval) - это алгоритм, который воспринимает некоторый аргумент ArgSearch и пытается локализовать (найти, определить) запись, ключ которой равен ArgSearch. Значение ArgSearch называется аргументом поиска.

Алгоритм поиска может возвратить всю найденную запись или чаще всего может возвратить некоторый указатель на эту запись. Поиск, по завершении которого найдена запись с ключом, равным аргументу поиска, называется успешным или результативным. Успешный поиск часто завершаетсяизвлечением. Однако возможно, что поиск некоторого конкретного аргумента в таблице является неудачным (безрезультатным), т. е. в данной таблице не существует записи с этим аргументом в качестве ключа. В этом случае такой алгоритм может возвратить некоторую специальную «пустую запись» или некоторый пустой указатель. Однако чаще такое условие приводит к появлению некоторой ошибки или к установке во флаге некоторого конкретного значения, которое указывает, что искомая запись отсутствует. Если поиск закончился неудачно, то часто бывает желательно добавить некоторую новую запись с аргументом ArgSearch в качестве ключа. Алгоритм, который выполняет эту функцию, называетсяалгоритмомпоискаивставки.

В некоторых случаях бывает желательно вставить некоторую запись с первичным ключом Key в некоторую таблицу без первоначального поиска другой записи с этим же самым ключом. Такая ситуация могла бы возникнуть, если бы уже было определено, что такой записи нет в файле. В таких случаях необходимо различать ситуации, относящиеся к поиску, к вставке или к поиску со вставкой.

Как указывалось ранее, таблица может быть физически организована по-разному. Это может быть массив записей, связанный список, дерево или даже граф. Поскольку различные методы поиска могут соответствовать различным организациям таблиц, то таблица часто строится, исходя из соображений конкретного метода поиска. Такая таблица может полностью располагаться в оперативной памяти, или во вспомогательной памяти, или там и там. Ясно, что для разных организаций таблиц необходимы различные методы поиска. Методы поиска, при которых вся таблица постоянно находится в оперативной памяти, называются методамивнутреннегопоиска, а те методы, для которых большая часть таблицы хранится во вспомогательной памяти (такой, как диск или лента), называются методами внешнегопоиска. Мы будем рассматривать только внутренний поиск.

Ниже рассматриваются алгоритмы (методы) операций в таблицах. Некоторые алгоритмы поясняются программными текстами, написанными на алгоритмическом языке Pascal. Поэтому необходимо определить некоторые переменные и структуру таблицы.

В языке Pascal имеется тип, подходящий для описания типа элементов таблицы, – это тип Record (запись), следовательно, тип элемента таблицы может быть задан, например, как

Type

Key: Word;

{описания других полей}

end;

где Key - это поле-ключ, в котором размещается значение ключа, идентифицирующее элемент,

«другие поля» - поля для размещения тех полезных данных, которые должны содержаться в записи.

Излагаемые ниже методы оперируют с отдельными записями таблицы, используя единственно возможный способ доступа к записям – доступ по ключу. Значит ключ «с точки зрения» этих методов - единственная существенная компонента, и нет необходимости как-то описывать остальные поля. Выбор в качестве типа ключа целого типа (Word) достаточно произволен; точно так же можно использовать и любой тип, на котором задано отношение порядка.

Тип таблицы определим как

TTable = Array [0.. HighIndex] Of TElement; (10.2а)

Тогда сама таблица может быть определена как

Var a: TTable; (10.2б)

иначе говоря, таблица представляется как последовательность элементов а[0], a[1],…, a[HighIndex], каждый из которых является записью типа TElement. Представление таблицы в виде массива необязательно; для нас важен порядок следования элементов, который задается с помощью индекса.

Зададим некоторые переменные:

N, HighIndex: Integer;

где N - количество активных элементов, HighIndex - максимальное значение индекса активного элемента. Индексы вектора а начинаются с нуля, поэтому HighIndex = N - 1.