Итак, главное отличие 2-3-4 деревьев от 2-3 состоит в том, что они могут содержать более трех дочерних узлов, что дает возможность создавать четырехместные узлы (узлы, имеющие четыре дочерних узла и три элемента данных). Можно увидеть отличия визуально на гифке под эти текстом.На первом слайде показано 2-3 дерево, на втором — 2-3-4.
К данным, размещаемым в узлах 2-3-4 дерева выдвигаются некоторые требования (как и к данным, которые размещаются в 2-3 деревьях) — короткое изображение данной информации вы можете увидеть на картинке под текстом:
Главные плюсы 2-3-4 деревьев в сравнении с 2-3 деревьями состоят в том, что стандартные операции вставки и удаления элементов осуществляются за меньшее количество шагов. Главным минусом является количество требуемой памяти, ведь по скольку 2-3-4 деревья могут содержать большее количество элементов, которые потребуется где-то хранить, надо будет потреблять больше памяти. Для того что-бы устранить эту проблему можно использовать красно-черное бинарное дерево (red-black tree) специального вида, но про них мы поговорим позже.
Перед тем как описать принципы основных операций 2-3-4 деревьев, я наведу пример кода из книги «Абстракция данных и решение задач на C++», как можно классом описать 2-3-4 дерево.
сlass TreeNode
{
private:
TreeltemType smallltem, middleltem, largeltem;
TreeNode *leftChildPtr, *lMidChildPtr,
*rMidChildPtr, *rightChildPtr;
friend class TwoThreeFourTree;
};
Поиск в 2-3-4 дереве
Алгоритм поиска в элементах 2-3-4 дерева схож с алгоритмом поиска в элементах 2-3 дерева (эффективность алгоритма поиска
в 2-3 дереве имеет порядок O(log n)), можно сказать, что алгоритм тот же, но он расширен. Суть заключается в том, что например для поиска в дереве элемента, содержащего значение 31, хорошо было бы обследовать левое поддерево корня, поскольку число 31 меньше, чем 37. Затем обследуется среднее поддерево узла , поскольку число 31 лежит между 30 и 35. Поиск заканчивается указателем на левый дочерний узел узла , поскольку число 31 меньше, чем 32. В результате приходим к выводу, что в дереве нет элемента, содержащего значение 31.
Вставка в 2-3-4 дерево
Алгоритм вставки элемента в 2-3-4 дерево отличается от алгоритма вставки элемента в 2-3 дерево только те, что узлы, которые содержат 4 элемента разделяются сразу после обнаружения.В дереве 2-3 алгоритм поиска проходил по пути от корня до листа, а затем возвращался обратно, разделяя узлы. Чтобы избежать этого возвращения, алгоритм вставки элемента в 2-3-4 дерево разделяет четырехместные узлы сразу при обнаружении на пути от корня к листу. Поиск позиции для вставки начинается с корня, представляющего собой четырехместный узел . Перемещая число 30 вверх, разделяем его на три части. Поскольку этот узел является корнем, нужно создать новый корень, поместить в него число 30 и присоединить к нему два дочерних узла. Продолжаем поиск числа 20, проверяя левое поддерево корня, поскольку число 20 меньше 30.
Удаление узла из 2-3-4 дерева
Алгоритм удаления заключается в том, что сначала выполняется поиск узла, содержащего заданный элемент. Потом ищем симметричного преемника этого узла. Затем меняем их местами с элементом, так чтобы удаление всегда выполнялось из листа. Если лист содержит 3 или 4 элемента, мы просто удаляем из него искомый элемент. Главное отличие состоит в том, что в 2-3-4 дереве нам не нужно возвращаться в корень и перестраивать дерево, как мы это делаем в 2-3 дереве.
Закончить свой рассказ я бы хотел словами своего предшественника: «При написании курсового проекта по этой теме, я понял, что информации в Рунете практически нет, поэтому решил внести свои пару копеек в это дело, рассказав заинтересованному сообществу об этой структуре данных.»
P.S.: во время написания я черпал знания из книги «Абстракция данных и решение задач на C++. Стены и зеркала» 3-е издание, авторы: Френк М. Каррано, Джанет Дж. Причард, советую всем ее для прочтения и огромное спасибо вам, читатели, за уделенное материалу внимание.
Источник: Хабрахабр
