Включение узла в двоичное дерево

Добавление элемента (ДОБАВИТЬ)

Дано: дерево Т и пара (K,V – ключ и вершина).

Задача: добавить пару (K, V) в дерево Т.

Алгоритм включения узла в дерево

1. Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), ПУСТО, ПУСТО) и остановиться

Иначе сравнить K с ключом корневого узла X:

1.1. Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т

Иначе (если K<X) рекурсивно добавить (K,V) в левое поддерево Т.

Включение узла в в дерево

Введём определение: дерево потомков узла – это поддерево, состоящее из самого узла и его потомков.

Вначале определим функцию, которая добавляет элемент с ключом K к дереву потомков узла X. После выполнения функции во всех пройденных узлах, кроме, может быть, самого узла X, будет меньше 2t – 1, но не меньше t – 1 ключей. Величина t определяется из формулы:

m = 2(t – 1).

Алгоритм добавления элемента к дереву потомков

1. Если Х – не лист

1. Определяем интервал, где должен находиться K. Пусть Y – соответствующий сын.

2. Рекурсивно добавляем K к дереву потомков Y.

3. Если узел Y полон, то есть содержит 2t − 1 ключей, расщепляем его на два. Узел Y1 получает первые t − 1 ключей Y, и первые t его потомков, а узел Y2 – последние t − 1 ключей Y и последние t его потомков. Средний из ключей узла Y попадает в узел Х, а указатель на Y в узле X заменяется указателями на узлы Y1 и Y2.

1. Если X – лист, просто добавляем туда ключ K.

Теперь сформулируем алгоритм добавления элемента с ключом K ко всему дереву. Буквой R обозначим корневой узел.

Алгоритм добавления элемента к В дереву

1. Добавим K к дереву потомков R.

2. Если в результате R содержит 2t − 1 ключей, расщепляем его на два. Узел R1 получает первые t − 1 из ключей R и первые t его потомков, а R2 – последние t − 1 из ключей R и последние t его потомков. Средний из ключей узла R попадает вo вновь созданный узел, который становится корневым. Узлы R1 и R2 становятся его потомками.

Зачастую добавление элемента приводит к полному или частичному сдвигу всех узлов дерева. Таким образом, эта операция является одной из наиболее трудоемких.

Удаление узла из бинарного дерева

Удаление узла (УДАЛИТЬ)

Дано: дерево Т с корнем n и ключом K.

Задача: удалить из дерева Т узел с ключом K (если такой есть).

Алгоритм удаления узла из дерева

1. Если дерево T пусто, остановиться

Иначе сравнить K с ключом X корневого узла n.

1. Если K>X, рекурсивно удалить K из правого поддерева Т

2. Иначе если K<X, рекурсивно удалить K из левого поддерева Т.

3. Если K=X, то необходимо рассмотреть два случая.

   1. Если одного из детей нет, то значения второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m.

   2. Если оба потомка присутствуют, то

      1. найдём узел m, являющийся самым левым узлом правого поддерева;

      2. скопируем значения полей (ключ, значение) узла m в соответствующие поля узла n.

      3. у предка узла m заменим ссылку на узел m ссылкой на правого потомка узла m (который может быть равен ПУСТО).

      4. освободим память, занимаемую узлом m (на него теперь никто не указывает, а его данные были перенесены в узел n).