Структура данных 2-3-4 дерево

Автор: admin от 22-12-2015, 13:00, посмотрело: 836

Когда я первый раз столкнулся с темой бинарных деревьев в программировании, то сразу нашел на Хабре ответы почти на все возникшие у меня вопросы, но время шло, вопросов становилось больше и совсем недавно я нашел тему, которую еще не осветили на данном ресурсе — это 2-3-4 деревья. Есть отличная статья на тему 2-3 деревьев, в которой можно найти ответы на вопросы «Что такое куча?», «Что такое 2-3 деревья», а также информацию про основные операции со структурой, поэтому я не буду повторяться и сразу перейду к главной теме.

Итак, главное отличие 2-3-4 деревьев от 2-3 состоит в том, что они могут содержать более трех дочерних узлов, что дает возможность создавать четырехместные узлы (узлы, имеющие четыре дочерних узла и три элемента данных). Можно увидеть отличия визуально на гифке под эти текстом.На первом слайде показано 2-3 дерево, на втором — 2-3-4.

Структура данных 2-3-4 дерево

К данным, размещаемым в узлах 2-3-4 дерева выдвигаются некоторые требования (как и к данным, которые размещаются в 2-3 деревьях) — короткое изображение данной информации вы можете увидеть на картинке под текстом:


  • Если узел содержит 2 элемента и имеет 2 дочерних узла, то узел должен содержать один элемент, значение которого должно быть больше, чем значения левого дочернего узла, и меньше, чем значения правого дочернего узла

  • Если узел содержит 2 элемента и имеет 3 дочерних узла, то узел должен удовлетворять следующим соотношениям: значение X больше значений левого дочернего узла и меньше значений среднего дочернего узла; значение Z больше значений среднего дочернего узла и меньше значений правого дочернего узла.

  • Если узел содержит 3 элемента и имеет 4 дочерних узла, то узел должен удовлетворять следующим соотношениям: значение X больше значений левого дочернего узла и меньше значений левого среднего дочернего узла; значение Y больше значений левого среднего дочернего узла и меньше значений правого среднего дочернего узла; значение Z больше значений правого среднего дочернего узла и меньше значений правого дочернего узла.

  • Лист может содержать один, два или три элемента.


  • Структура данных 2-3-4 дерево

    Главные плюсы 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 дерево только те, что узлы, которые содержат 4 элемента разделяются сразу после обнаружения.В дереве 2-3 алгоритм поиска проходил по пути от корня до листа, а затем возвращался обратно, разделяя узлы. Чтобы избежать этого возвращения, алгоритм вставки элемента в 2-3-4 дерево разделяет четырехместные узлы сразу при обнаружении на пути от корня к листу. Поиск позиции для вставки начинается с корня, представляющего собой четырехместный узел . Перемещая число 30 вверх, разделяем его на три части. Поскольку этот узел является корнем, нужно создать новый корень, поместить в него число 30 и присоединить к нему два дочерних узла. Продолжаем поиск числа 20, проверяя левое поддерево корня, поскольку число 20 меньше 30.

    Структура данных 2-3-4 дерево

    Удаление узла из 2-3-4 дерева


    Алгоритм удаления заключается в том, что сначала выполняется поиск узла, содержащего заданный элемент. Потом ищем симметричного преемника этого узла. Затем меняем их местами с элементом, так чтобы удаление всегда выполнялось из листа. Если лист содержит 3 или 4 элемента, мы просто удаляем из него искомый элемент. Главное отличие состоит в том, что в 2-3-4 дереве нам не нужно возвращаться в корень и перестраивать дерево, как мы это делаем в 2-3 дереве.

    Структура данных 2-3-4 дерево

    Закончить свой рассказ я бы хотел словами своего предшественника: «При написании курсового проекта по этой теме, я понял, что информации в Рунете практически нет, поэтому решил внести свои пару копеек в это дело, рассказав заинтересованному сообществу об этой структуре данных.»

    P.S.: во время написания я черпал знания из книги «Абстракция данных и решение задач на C++. Стены и зеркала» 3-е издание, авторы: Френк М. Каррано, Джанет Дж. Причард, советую всем ее для прочтения и огромное спасибо вам, читатели, за уделенное материалу внимание.

    Источник: Хабрахабр

    Категория: Программирование

    Уважаемый посетитель, Вы зашли на сайт как незарегистрированный пользователь.
    Мы рекомендуем Вам зарегистрироваться либо войти на сайт под своим именем.

    Добавление комментария

    Имя:*
    E-Mail:
    Комментарий:
    • bowtiesmilelaughingblushsmileyrelaxedsmirk
      heart_eyeskissing_heartkissing_closed_eyesflushedrelievedsatisfiedgrin
      winkstuck_out_tongue_winking_eyestuck_out_tongue_closed_eyesgrinningkissingstuck_out_tonguesleeping
      worriedfrowninganguishedopen_mouthgrimacingconfusedhushed
      expressionlessunamusedsweat_smilesweatdisappointed_relievedwearypensive
      disappointedconfoundedfearfulcold_sweatperseverecrysob
      joyastonishedscreamtired_faceangryragetriumph
      sleepyyummasksunglassesdizzy_faceimpsmiling_imp
      neutral_faceno_mouthinnocent