Рис. 13.3 Добавление элемента с ключом 13. Светло-серые вершины находятся на пути от корня до позиции нового элемента. Пунктир связывает новый элемент со старыми.

Tree-Insert (Г, z)

1у <- nil

2х <- root[T]

3while х ф nil

4do у <- x

5if key[z] < key[x]

6then x <- left[x]

7else x <- right[x]

8f- у

9if у = nil

10then гоо[Г] <- z

11else if key[z] < fcejy[y]

12then left[y] +- z

13else right[y] <- 2:

На рисунке 13.3 показано, как работает процедура Tree-Insert. Подобно процедурам Tree-Search и Iterative-Tree-Search, она двигается вниз по дереву, начав с его корня. При этом в вершине у сохраняется указатель на родителя вершины х (цикл в строках 3-7). Сравнивая key[z] с кеу[х], процедура решает, куда идти - налево или направо. Процесс завершается, когда х становится равным nil. Этот nil стоит как раз там, куда надо поместить z, что и делается в строках 8-13.

Как и остальные операции, добавление требует времени 0(h) для дерева высоты h.

Удаление

Параметром процедуры удаления является указатель на удаляемую вершину. При удалении возможны три случая, показанные на рисунке 13.4. Если у z нет детей, для удаления z достаточно поместить nil в соответствующее поле его родителя (вместо z). Если у z есть один ребёнок, можно «вырезать» z, соединив его родителя

Рис. 13.4 Удаление вершины z из двоичного дерева поиска, (а) Если вершина z не имеет детей, её можно удалить без проблем, (б) Если вершина z имеет одного ребёнка, помещаем его на место вершины z. (в) Если у вершины z двое детей, мы сводим дело к предыдущему случаю, удаляя вместо неё вершину у с непосредственно следующим значением ключа (у этой вершины ребёнок один) и помещая ключ кеу[у] (и связанные с ним дополнительные данные) на место вершины z.

напрямую с его ребёнком. Если же детей двое, требуются некоторые приготовления: мы находим следующий (в смысле порядка на ключах) за z элемент у; у него нет левого ребёнка (упр. 13.3-4). Теперь можно скопировать ключ и дополнительные данные из вершины у в вершину z, а саму вершину у удалить описанным выше способом.

Примерно так и действует процедура Tree-Delete (хотя рассматривает эти три случая в несколько другом порядке).

Tree-Delete (Г, z)

1if left[z] = nil или right[z] = nil

2then у <- z

3else у <- Tree-Successor(2:)

4if left[y] ф nil

5then ж <- left[y]

6else ж <- right[y]

7if ж / nil

8then p[x] <-

9if p[y] = nil

10then root[T] <- ж

11else if у = left[p[y]]

12then left\p[y]] f- ж

13else right[p[y]] <- ж

14if у ф z

15then key[z] <- fcet/[y]

16> копируем дополнительные данные, связанные с у

17return у

В строках 1-3 определяется вершина у, которую мы потом вырежем из дерева. Это либо сама вершина z (если у z не более одного ребёнка), либо следующий за z элемент (если у z двое детей). Затем в строках 4-6 переменная ж становится указателем на существующего ребёнка вершины у, или равной nil, если у у нет детей. Вершина у вырезается из дерева в строках 7-13 (меняются указатели в вершинах р[у] и ж). При этом отдельно рассматриваются граничные случаи, когда ж = nil и когда у является корнем дерева. Наконец, в строках 14-16, если вырезанная вершина у отлична от z, ключ (и дополнительные данные) вершины у перемещаются в z (ведь нам надо было удалить z, а не у). Наконец, процедура возвращает указатель у (это позволит вызывающей процедуре впоследствии освободить память, занятую вершиной у). Время выполнения есть 0(h) на дереве высоты h. Итак, мы доказали следующую теорему.

Теорема 13.2. Операции Insert и Delete могут быть выполнены за время 0(h), где h - высота дерева.

Упражнения

13.3-1 Напишите рекурсивный вариант процедуры Tree-Insert.

13.3-2 Начиная с пустого дерева, будем добавлять элементы с различными ключами один за другим. Если после этого мы проводим поиск элемента с ключом ж, то число сравнений на единицу