Анализ вставки элемента в бинарное дерево поиска

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

Вставка

Для вставки нового значения v в бинарное дерево поиска Т мы воспользуемся процедурой Tree_Insert. Процедура получает в качестве параметра узел z, у которого key [z] = v, left [z] = NIL и right [z] = NIL, после чего она таким образом изменяет Т и некоторые поля z, что z оказывается вставленным в соответствующую позицию в дереве.

TreeJnsert(T, z)

1 у *- NIL

2 х *- root[T]

3 while x ф nil

4 do у <— x

5 if key[z] < key[x]

6 then x <— left[x]

7 else x <— right[x]

8 p[z]<r-y

9 if у = NIL

10 then root[T] <— z > Дерево Г — пустое

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

12 then left[y] <- z

13 else right[y] <— z

На рис. 12.3 показана работа процедуры Tree_Insert. Подобно процедурам Tree_Search и Iterative_Tree_Search, процедура TreeInsert начинает работу с корневого узла дерева и проходит по нисходящему пути. Указатель х отмечает проходимый путь, а указатель у указывает на родительский по отношению к х деревья поиска 325

Рис. 12.3. Вставка элемента с ключом 13 в бинарное дерево поиска. Светлые узлы указывают путь от корня к позиции вставки; пунктиром указана связь, добавляемая при вставке нового элемента узел. После инициализации цикл while в строках 3-7 перемещает эти указатели вниз по дереву, перемещаясь влево или вправо в зависимости от результата сравнения ключей key [x] и key [z)9 до тех пор пока х не станет равным NIL. Это значение находится именно в той позиции, куда следует поместить элемент z. В строках 8-13 выполняется установка значений указателей для вставки z. Так же, как и другие примитивные операции над бинарным деревом поиска, процедура Tree_Insert выполняется за время О (h) в дереве высотой h.