Анализ вычислительной сложности алгоритмов (стр. 4 )

 

19

 

18 19

Корень разбивается на два узла и создается новый корень.

 

10 -

7 - 16

 

19

18 19

T23_Insert(t, x)+T23_Insert1(&t,&lt,&tnew,&low);

30. 2 – 3-дерево поиска. Алгоритм удаления элементов, эффективность операций в 2-3-дереве

Если при удалении узла x-листа, у родителя w остается один сын и узел w является корнем, то родитель удаляется из дерева, а корнем становится его единственный сын. Пусть родитель w не является корнем. Тогда, если братья узла-родителя w имеют трех сыновей, то один из сыновей брата передается узлу w и у него становится двое сыновей. Если братья узла w имеют двух сыновей, то единственный сын узла w передается одному из его братьев, и узел w удаляется. Если после этого у родителя удаленного узла w останется один сын, то процесс перестройки повторяется дальше по дереву.

 

1

-

9 -

 

2

 

1

 

 

8

19

12 18

 

 

9

УДАЛЕНИЕ ИЗ 2-3 ДЕРЕВА

Рекурсивная операция T23_Delete(t, x) по заданному указателю на удаляемый узел x отыскивает узел x в 2-3 дереве и удаляет его. Если после удаления родитель узла x имеет одного сына, то функция возвращает значение TRUE, иначе – FALSE. T23_Delete1(t, x);

31. 2-3-4-дерево поиска. Операция вставки элементов в 2-3-4-дерево

Существует еще одна разновидность сбалансированных деревьев, аналогичных по алгоритмам вставки и удаления элементов 2-3-деревьям. Это 2-3-4 – деревья.

В отличие от 2-3 –деревьев, 2-3-4- деревья допускают хранение в узлах данных. Кроме того, узлы имеют от 2-х до 4-х сыновей. Данные, хранящиеся в узлах, служат границами, разделяющими значения ключей в поддеревьях узлов.

12

 

4 18 22

0 24 26

В 2-3-4 – дереве узлы обладают еще большей гибкостью, чем в 2-3- дереве и соответственно количество разделений и слияний узлов в нем меньше, благодаря наличию 4-узлов. Алгоритм поиска ничем не отличается от поиска в 2-3- дереве кроме того, что здесь в 4-узлах рассматриваются 4 интервала ключей для выбора одного из сыновей для последующего поиска. Поиск может закончится на любом узле, а не только на листе, как в 2-3- дереве. Алгоритмы вставки и удаления также аналогичны 2-3- деревьям . Они обеспечивают полную сбалансированность дерева. Если поиск при вставке заканчивается на 2-узле, то он преобразуется в 3-узел. Если это 3-узел, то он преобразуется в 4-узел. Если элемент вставляется в 4-узел, то он разделяется на два 2-узла, при этом средний элемент передается родительскому узлу. Если родительский узел тоже 4-узел, то он также разделяется на два 2-узла. Этот процесс может распространиться вплоть до корня дерева. Если корень дерева также 4-узел, то он разделяется на два 2-узла и образуется новый корень – 2-узел, к которому присоединены два 2-узла, полученные при разделении бывшего корня. Таким образом точкой роста 2-3-4- дерева является корень дерева. Этот процесс восходящего разделения узлов можно исключить, если организовать нисходящее разделение 4-узлов, встречающихся на пути поиска. То есть если в родительском узле при выборе сына для дальнейшего поиска обнаружено, что это 4-узел, то разделяется сын и дальнейший поиск продолжается уже в 2-узле:

2-узел 3-узел 3-узел 4-узел

4-узел 4-узел

 

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

Когда корень дерева является 4-узлом, то при вставке любого элемента он автоматически разделяется и образуется новый 2-узел, который становится корнем дерева.

Пример построения 2-3-4- дерева:

1

18

18 7

 

4 19

 

 

18

 

 

Поскольку 4-узлы разделяются на пути от вершины вниз, эти деревья называются нисходящими 2-3-4- деревьями.

Максимальная высота 2-3-4- дерева h=(log2n+1), и вставка нового элемента, как правило, не изменяет ее за исключением случая, когда разделяется корень дерева.

В худшем случае, когда все узлы на пути поиска при вставке являются 4-узлами, каждый узел на пути поиска подвергается разделению. Но если входная последовательность элементов является случайной перестановкой по ключам, такой случай маловероятен.

До сих пор не удалось точно проанализировать аналитически производительность