38. Реализация нагруженного дерева (атд tree). Структура программы для проверки орфографии с помощью нагруженного дерева.

АТД TREE формально можно определить, как указатель на узел валяющимся корнем дерева, иначе говоря нагруженное дерево можно объявить так:

type

TREE =^ TREENODE

Следующая интерпретация как множество слов

var words: TREE;

Определим еще 1-н тип: WordType, как массив символов в составе которого есть хотя бы один символ конца слова «$», тогда любое x можно задать как переменную типа WordType, считая, что конкретное слово составляют те символы которые стоят до маркёра.

Соответствующую процедуру insert, т.е вставку x в дерево можно определить так:

procedure INSERT (x: WordType; var words: TREE);

var i: integer; t: TREE; //i – счетчик, t – указатель на поддеревья

begin

i=1;

t:=words;

while x [i] < > ‘$’ do begin

if VALUE of (t^, x [i]) = nil then //если текущий узел не имеет сына по ребру не соответствующий символу x [i]. VALUE of – возвращает указатель ассоциирующийся с символом x[i] в узле разыменования

GETNEW (t^, x [i]); //передача разыменования t индексированному указателю

t:=VALUEOF (t^, x [i]; //теперь в узле t разыменованное ребро помеченное символом x [i] обязательно будет указывать на сына, поэтому все это будет означать продвижение к сыну t разыменов.

i:=i+1; //перемещение по слову x

end;

По окончании while мы или дойдем до кольцевого ребра помеченного «$», или построим новую ветку.

ASSIGN (t^, ‘$’, t); //эта функция сделает петлю на $, т.е ребро помеченное $ превратится в петлю.

Аналогично для АТД TREE можно построить оператор DELETE

Предположим что необходимо проверить правильность слов в текстовом файле, символы конца строки, разделители, тогда схему программы можно написать так: сначала слова из input, после это читает файл dictionary, где правильные слова, каждое считанное слово исключается из множества А, если оно там есть. После окончания множества А будет содержать только неправильные слова.

Псевдокоды такой программы:

MAKENULL (A);

while not eof (input) do //цикл чтения входного файла

begin read (input, nextword);

INSERT (nextword, A);

end;

while not eof (dictionary) do //читаем словарь

begin read (dictionary, nextword);

DELETE (nextword, A)

end;

39. Структура 2-3 дерева. Поиск записи с заданным ключом в 2-3 дереве.

2-3 деревья обладают следующими свойствами:

• Каждый внутренний узел, в том числе корень должен иметь 2-3 сына

• Пустое дерево и дерево с одним листом 2-3 деревья

Предположим, что на множестве элементов «≤» задан линейный порядок.

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

На рис. 4.12 показана структура 2-3 дерева (ребра – прямоугольники, листья – овалы)

В соответствии с так определенной структурой 2-3 дерево имеющее k-уровней будет иметь от 2^k-1 до 3^k-1 листьев. Дерево в котором хранится n элементов будет иметь не более 1+ log₃(n) и не менее 1+log₂(n) уравнений, а значит длины от корня к листу будут иметь в худшем случае O(log₃(n)).

Поиск записи с ключом x будет осуществляться за время порядка O(log₂(n)), т.к при поиске нам придется переместиться от корня до листа.

Причем будет осуществляться:

• Обозначим через y и z значения ключей в промежуточном узле (node). В качестве node можно рассмотреть корень

• Тогда если x < y мы перемещаемся к 1-му сыну узла node

• Если x ≥ y и у узла node 2 сына, то перемещаемся ко 2-мы сыну

• Если у узла node 3 сына и x ≥ z, то перемещаемся к 3-му сыну, иначе ко 2-му

При достижении листа сравниваем x c ключом x` хранящимся в этом узле, и если x = x`, то элемент найден, а иначе констатируем отсутствие элемента в хранилище.