Язык С++ и программирование на нем. Рейзлин В.И. - 155 стр.

UptoLike

Составители:

Рубрика:

157

26.2. Таблицы

Построенное в последнем примере дерево часто называют дере-

вом поиска. Дерево поиска иногда используют для построения таблиц, в

которых хранятся различные сведения, обычно в виде структур. При

этом для упорядочения структур они обычно именуются и чтобы орга-

низовать эффективный поиск структуры по ее имени, нужно иметь воз-

можность сравнивать любые два имени и устанавливать, какое из них

“больше”, а какое –“меньше”. Имя структуры в таблице часто называют

ключом структуры. В качестве ключа часто используют целые числа

или строки одинаковой длины.

Над таблицей как структурой данных определены операции:

 поиск в таблице структуры с заданным ключом;

 включение в таблицу структуры с заданным ключом;

 исключение из таблицы структуры с заданным ключом.

Мы рассмотрим организацию таблиц в виде двоичного дерева. В

примере кодирования ключом служили сами числа из файла NUM.txt.

Фактически мы уже рассмотрели операции поиска в дереве и включения

элемента в дерево по заданному ключу. Сейчас оформим в виде функ-

ции операцию исключение элемента с заданным ключом из дерева.

Непосредственное удаление структуры реализуется просто, если

удаляемая вершина дерева является конечной или из нее выходит толь-

ко одна ветвь (рис. 11):

Рис. 11. Удаление элемента из дерева, когда удаляемая вершина

является конечной или из нее выходит только одна ветвь

Трудность состоит в удалении вершины, из которой выходят две

ветви. В этом случае нужно найти подходящее звено дерева, которое

можно было бы вставить на место удаляемого, причём это подходящее

звено должно просто перемещаться. Такое звено всегда существует: это

либо самый правый элемент левого поддерева, либо самый левый эле-