5.2-3-4 Деревья

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

Опр. Сбалансированное 2-3-4 дерево поиска - это 2-3-4 дерево, все пустые поддеревья которого расположены на одинаковом расстоянии от корня.

Вставка нового ключа также как и в бинарном дереве поиска. Дерево может оказаться несбалансированным.

Разделение 4-узла: Если отец 4-узла, который нужно разделить также 4-узел, то мы разделяем каждый 4-узел по пути следования. Если корень дерева есть 4-узел, преобразуем его в три 2-узла.

Св-во1. При поиске в 2-3-4 деревьях из N узлов посещается максимум lgN+1 узлов

Св-во2. для вставок в 2-3-4 деревьях из N узлов разделение менее lgN+1 узлов в худшем случае

Недостаток 2-3-4 деревьев - сложность их представления хранения и реализация алгоритмов.