Древовидные структуры (деревья бинарные, сбалансированные, сильноветвящиеся). Основные операции (поиск, вставка, удаление).

Деревом называется орграф для которого: Существует узел, в которой не входит ни одной дуги. Этот узел называется корнем. В каждую вершину, кроме корня, входит одна дуга.

С точки зрения представления в памяти важно различать два типа деревьев: бинарные и сильноветвящиеся. В бинарном дереве из каждой вершины выходит не более двух дуг. В сильноветвящемся дереве количество дуг может быть произвольным.

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

Бинарное дерево называется сбалансированным или АВЛ-деревом, если для любой вершины дерева, высота левого и правого поддеревьев отличается не более чем на единицу.

Поиск элемента (FIND) Дано: дерево Т и ключ K. Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел. Алгоритм:

• Если дерево пусто, сообщить, что узел не найден, и остановиться.
• Иначе сравнить K со значением ключа корневого узла X.
• Если K=X, выдать ссылку на этот узел и остановиться.
• Если K>X, рекурсивно искать ключ K в правом поддереве Т.
• Если K<X, рекурсивно искать ключ K в левом поддереве Т.

Добавление элемента (INSERT) Дано: дерево Т и пара (K,V). Задача: добавить пару (K, V) в дерево Т. Алгоритм:

• Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
• Иначе сравнить K с ключом корневого узла X.
• Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
• Если K<X, рекурсивно добавить (K,V) в левое поддерево Т.

Удаление узла (REMOVE) Дано: дерево Т с корнем n и ключом K. Задача: удалить из дерева Т узел с ключом K (если такой есть). Алгоритм:

• Если дерево T пусто, остановиться;
• Иначе сравнить K с ключом X корневого узла n.
• Если K>X, рекурсивно удалить K из правого поддерева Т;
• Если K<X, рекурсивно удалить K из левого поддерева Т;
• Если K=X, то необходимо рассмотреть три случая.
• Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
• Если одного из детей нет, то значения полей второго ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
• Если оба ребёнка присутствуют, то
• найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
• скопируем данные (кроме ссылок на дочерние элементы) из m в n;
• рекурсивно удалим узел m.