На этом шаге мы обсудим особенности реализации такой функции.

Цель этой задачи - вставить элемент с заданным ключом к в двоичное дерево так, чтобы получающееся дерево тоже удовлетворяло основному свойству двоичного дерева. Метод представляет собой процедуру, которая получает два параметра:

(1) кортеж x из ключа и значения элемента и
(2) двоичное дерево T.

Он должен, в частности, расширить список T, добавив в него новый лист.

И здесь можно считать, что размер задачи - это высота дерева. Самое простое начальное условие выполняется для пустого дерева. В этом случае алгоритм должен расширить дерево, включив в него один узел, у которого, очевидно, нет дочерних записей. При декомпозиции задачи мы будем придерживаться схемы на рисунке 1 86 шага. Очевидно, если дерево не пусто и k меньше ключа корневого узла, то процедура вставит узел в левое поддерево. Иначе она вставит его в правое поддерево. Сразу предположим, что k < k_root.

Есть два возможных сценария, приводящих к начальному и рекурсивному условиям. Если у корневого узла нет левого поддерева, то процедура может просто заменить соответствующий пустой список узлом, содержащим ключ и элемент (и два пустых поддерева). Но если у корневого узла есть непустое левое поддерево, то метод должен вставить в него новый узел, что, естественно, приводит к рекурсивному вызову. То же справедливо и для правого поддерева. В примере 5.10 приведена возможная реализация процедуры.

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14

def insert_binary_tree(x, T):
    if T == []:
        T.extend([x[0], x[1], [], []])
    else:
        if x[0] < T[0]:
            if T[2] == []:
                T[2].extend([x[0], x[1], [], []])     
            else:
                insert_binary_tree(x, T[2])
        else:
            if T[3] == []:
                T[3].extend([x[0], x[1], [], []])
            else:
                insert_binary_tree(x, T[3])

Архив с файлом можно взять здесь.

Со следующего шага мы начнем знакомиться со схемами разбиения.

Предыдущий шаг Содержание Следующий шаг