Методы программирования. Громов Ю.Ю - 113 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

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

Рубрика: 

113
будет получен список ключей в алфавитном порядке: AQUARIUS, ARIES,
CANCER, CAPRICORN, GEMINI, LEO, …, VIRGO.
Ниже приводится подробное описание процесса поиска со вставкой.
Алгоритм Т. (Поиск по дереву со вставкой.)
Алгоритм предназначен для поиска заданного аргумента K в табли-
це записей, образующей бинарное дерево. Если ключ K в таблице отсут-
ствует, то новый узел, содержащий этот ключ, вставляется в дерево в
надлежащее место. Предполагается, что узлы дерева содержат по край-
ней мере следующие поля:
KEY(P) – ключ, хранящийся в узле NODE(P);
LLINK(P) – указатель на левое поддерево узла NODE(P);
RLINK(P) – указатель на правое поддерево узла NODE(P).
Пустые поддеревья (внешние узлы на рис. 39) представляются пус-
тыми указателями Λ. Переменная ROOT указывает на корень дерева. Для
удобства полагаем, что дерево не пусто, т.е. ROOT ≠ Λ, так как при
ROOT = Λ необходимые операции тривиальны.
T1. [Инициализация.] Присвоить Р ← ROOT. (Переменная-указатель
Р будет перемещаться вниз по дереву.)
T2. [Сравнение.] Если K < KЕY(Р), то перейти к шагу Т3; если
K > KEY(P), перейти к шагу Т4; и если K = KЕY(P), поиск успешно завершён.
T3. [Перемещение влево.] Если LLINK(P) ≠ Λ, то присвоить
Р ← LLINK(P) и вернуться к шагу Т2; в противном случае перейти к шагу Т5.
T4. [Перемещение вправо.] Если RLINK(P) ≠ Λ, то присвоить
Р ← RLINK(P) и вернуться к шагу Т2.
T5. [Вставка в дерево.] (Поиск оказался неудачным и требуется по-
местить ключ K в дерево.) Q
⇐
AVAIL (выделить новый узел). Присво-
ить KEY(Q) ← K, LLINK(Q) ← RLINK(Q) ← Λ. (На практике следует ини-
циализировать и другие поля нового узла.) Если K < KEY(P), то выпол-
нить присваивание LLINK(P) ← Q; в противном случае – присваивание
RLINK(P) ← Q. (Теперь можно присвоить Р ← Q и считать поиск ус-
пешно завершившимся.) ■
Среднее время работы алгоритма составляет величину, равную при-
мерно (7.5С – 2.5S + 4)
u, где С – количество выполненных сравнений;
S = 1 при успешном и 0 при неудачном поиске. Следовательно, это луч-
шее значение, чем при бинарном поиске с неявными деревьями.
Упражнения
1. Выполните алгоритм T в условиях последовательной вставки в
пустое дерево ключей JANUARY, FEBRUARY, MARCH, APRIL, MAY,
JUNE, JULY, AUGUST, SEPTEMBER, OCTOBER, NOVEMBER,
DECEMBER и постройте бинарное дерево (подобное изображённому на
рис. 39), которое при этом получится.

Страницы