2-3 дерево поиска. Алгоритм вставки и удаления элементов в 2-3 дереве

Страницы работы

7 страниц (Word-файл)

Фрагмент текста работы

                          2 – 3 ДЕРЕВЬЯ

Предложены Хопкрофтом в 1973 г.

В 2-3 дереве

1)  Каждый внутренний узел имеет 2 или 3 сына.

2)  Все пути от корня до любого листа имеют одинаковую длину.

3)  Элементы располагаются в листьях 2-3 дерева.

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

 


                                                             7         16

                                                             

 


                             5          -                  8         12                19        -

                             2          5               7       8     12             16        19

                                                            k-1          k-1

2-3 дерево с k уровнями имеет от 2      до 3     листьев, то есть 2-3 дерево, содержащее n элементов, имеет высоту не менее 1+log3 n и не более 1+log2 n. Таким образом высота дерева имеет порядок О(log n).

Элемент можно найти за время О(log n), сравнивая ключ искомого элемента  с параметрами в узлах.

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

ВКЛЮЧЕНИЕ ЭЛЕМЕНТА В 2-3 ДЕРЕВО

Включение нового элемента начинается так же, как и процесс поиска. Пусть мы находимся в некотором внутреннем узле x, чьи сыновья – листья и не содержат элемента с заданным ключом k. Если узел содержит двух сыновей, то новый элемент подключается к этому узлу в качестве третьего сына. Новый элемент помещается так, чтобы не нарушить упорядоченность сыновей. После этого корректируются значения минимальных ключей в узле x.

Например, включаем элемент с ключом 18.

При поиске мы приходим к самому правому узлу на среднем уровне. Помещаем 18 среди сыновей этого узла в порядке 16, 18, 19. В узле записываются значения 18 и 19.

                                                       

                                                             7         16

 


                               5                           8          12             18       19

 


                             2            5             7       8     12       16     18       19

Если при подключении к узлу новый элемент является четвертым, то узел x разбивается на 2 узла x и x’. Два наименьших элемента переносятся в узел x, а два наибольших – в x’. Теперь надо вставить узел x’ среди сыновей родителя узла x. Здесь ситуация повторяется. Если родитель имеет двух сыновей, то узел x’ становится третьим сыном. Если родитель имеет трех сыновей, то он в свою очередь разбивается на два узла. Процесс идет в случае необходимости выше и может достигнуть корня дерева. При необходимости разбиения корня создается новый корень, сыновьями которого становятся два узла, получившиеся при разбиении старого корня.

Пусть мы вставляем элемент m с ключом 10. Выбранный узел до подключения имеет трех сыновей, поэтому он разбивается на два новых узла.

 


                                                                          7         16

 


                           5            -              8          -                 12          -                  18        19

 


                           2         5               7            8                 10           12          16        18       19

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

 


                                                                           10      -

                                                           7       -                       16

 


                                 5       -                  8        -                  12    -                  18      19

                                2       5                  7         8               10       12          16     18     19

struct Internal       { type=INTERNAL

                                T    low2, low3

                                Internal son1, son2, son3

                              };

struct Leaf           { type=LEAF

                              T    key

                              T1   data

                              };

T23_Insert(t,x)

1    x – элемент данных

2    t – корень 2-3 дерева

3 lt      new Leaf(x)

4 if t=nil

5    then t        new Internal

6            son1[t]       lt

7            son2[t]       son3[t]        nil

8            return t

9 if son2[t]=nil

10   then son2[t]        lt

11           low2[t]       key[lt]

12           return t

13 Insert1(t,lt,tbk,lbk)

14 if tbk=nil

15     then temp         t

16             t        new Internal

17             son1[t]         temp

18             son2[t]        tbk

19             low2[t]        lbk

20             son3[t]        nil

21             return t

Первоначально дерево пусто и указатель на корень дерева root=nil.

Вызов функции:

Root         T23_Insert(root,x)

T23_Insert1(&t,&lt,&tnew,&low)

1      t – корень 2-3 дерева/2-3 поддерева

2      lt – новый узел - лист    

3      tnew – адрес нового узла, передаваемого родителю

4      low – минимальный ключ в поддереве нового узла tnew

5 tnew          nil

6      t - лист

7 if t - лист

8     then if key[t]=key[lt]

9                  then tnew        t или lt с большим ключом

10                        low          больший из key[t] и key[lt]

11                        return

12   t – внутренний узел

13 выбрать w – сына t узла для вставки lt

14 T23_Insert1(w,lt,tbk,lbk)

15 if tbk=nil

16    then вставка tbk среди сыновей узла t, справа от w

17            if t имеет 4 сына

18                then создание нового внутреннего узла tnew

19                        перенос двух правых сыновей узла t в узел tnew

20                        low        минимальный ключ первого сына tnew

21     return

Более подробный псевдокод операции вставки в 2-3 дерево приведен ниже.

T23_Insert1(&t,&lt,&tnew,&low)

1   t – корень 2-3 дерева/2-3 поддерева

2   lt – новый узел - лист

3 tnew          nil

4 if type[t]=LEAF

5    then if key[t]=key[lt]

6               then tnew         lt

7                       if key[t]<key[lt]

8                          then low          key[lt]

9                          else  low          key[t]

10                                temp        t

11                                t          lt

12                                lt        t

13          return

14    t – внутренний узел

15 if key[lt]<low2[t]

16    then child         1

17         w          son1[t]

18    else if son3[t]=nil or key[lt]<low3[t]

19               then child       2

20                        w           son2[t]

21               else child        3

22                        w           son3[t]

23 T23_Insert1(w,lt,tbk,lbk)

24 if tbk=nil

25    вставка нового сына

26     then if son3[t]=nil

27                then       узел имел 2-х сыновей

28                          if child=2         вставка во второе поддерево

29                             then son3[t]         tbk

30                                     low3[t]        lbk

31                              else        вставка в первое поддерево

32                                         son3[t]         son2[t]

33                                         low3[t]         low2[t]

34                                         son2[t]         tbk

35                                         low2[t]          lbk

36                 else        узел имел 3-х сыновей

37                          tnew       new Internal

38                          if child=3

39                             then        вставка в третье поддерево

40                                        son1[tnew]           son3[t]

41                                        son2[tnew]           tbk

42                                        son3[tnew]           nil

43                                        low2[tnew]           lbk

44                                        son3[t]           nil

45                                        low         low3[t]

46                            else       child<=2

47                                        son2[tnew]         son3[t]

48                                        low2[tnew]        low3[t]

49                                        son3[tnew]         nil

50                                        son3[t]         nil

51                                        if child=2

52                                           then son1[tnew]       tbk

53                                                   low         lbk

54                                       if child=1

55                                           then son1[tnew]        son2[t]

56                                                   son2[t]         tbk

57                                                   low        low2[t]

58                                                   low2[t]        lbk

59                        конец then 26 

60                      return

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

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

 


                                   10 -                                                                       12  -

                      7  -                     16  -                                            7  -                      18  -

                         

            5  -          8  -        12  -       18  -                           5  -         8  -            16  -          19  -

 


   2          5      7        8     10    12    16   18  19          2       5       7       8     12     16       18     19

 


                                12  -                                                                      12  -

 


                   7  -                       18  -                                                      12 18

 


                  5  8                 16  -       19  -                                 5  8           16  -       19  -

            2      5       8      12    16     18    19                    2       5       8     12    16   18       19

                                    12  18

 


                     5  8         16  -      19  -

 


         2       5       8     12    16     18     19

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

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

T23_Delete1(t,x)

1   t – узел корня 2-3 дерева/2-3 поддерева

2   x – удаляемый узел-лист

3 if сыновья  t - листья

4     then if x принадлежит к сыновьям узла t

5                 then удаление x

6                        смещение сыновей t справа от порцию влево

7                          if t имеет одного сына

8                              then return TRUE

9                              else return FALSE

10    t – внутренний узел, сыновья которого не листья

11  выбрать w – сына узла t для удаления узла x

12 F        T23_Delete1(w,x)

13 if F=FALSE then return FALSE

14        удален один из сыновей узла w и w имеет одного сына

15    if w – первый сын узла t

16        then if y – второй сын узла t имеет 3-х сыновей

17                     then 1-й сын y делается 2-м сыном узла w

18                     else сын узла w делается 1-м сыном узла y

19                            удаление узла w из сыновей узла t

20                            if t имеет одного сына

21                                then return TRUE

22                                else return FALSE

23     if w – второй сын узла t  

24         then if y – первый сын узла t имеет 3-х сыновей

25                     then 3-й сын узла y делается 1-м сыном узла w

26                             return FALSE

27                 if z – третий сын узла t имеет 3-х сыновей

28                    then 1-й сын узла z делается 2-м сыном узла w

29                            return FALSE

30                   первый и третий сыновья узла t не имеют 3-х сыновей

31              сын узла w делается 3-м сыном первого сына узла t-y

32              удаление w из сыновей узла t

33              if t имеет одного сына

34                   then return TRUE

35                   else return FALSE

36               w – третий сын узла t

37            if y – второй сын узла t имеет 3-х сыновей

38                then 3-й сын узла y делается 1-м сыном узла w

39                        return FALSE

40                else        узел y имеет 2-х сыновей

41                          сын w делается 3-м сыном узла у

42                          удаление w из сыновей узла t

43                          return FALSE

Более подробный псевдокод операции удаления

Похожие материалы

Информация о работе