68828

Використання бінарних дерев при роботі з таблицею символів

Лекция

Информатика, кибернетика и программирование

Кожний елемент містить змістовну частину і два покажчики на інші вершини. Вершини А С F що не мають ненульових покажчиків називають листями. Окремим випадком дерева є пусте дерево і дерево що складається з однієї вершини. Якщо у дереві є покажчик від вершини А до В то В називають прямим нащадком або сином А.

Украинкский

2014-09-26

163 KB

0 чел.

Лекція 16

Використання бінарних дерев при роботі з таблицею символів

Крім хеширування для роботи з таблицями упорядкованих елементів застосовують такі структури даних як бінарні  дерева.  Перевага  цих структур полягає  в  тому,  що  вони  дозволяють  не  тільки  швидко знаходити потрібні елементи таблиці і вносити зміни, але також  виводити упорядкований  зміст  таблиці.   Схематично   бінарне   дерево,   що застосовується як структура даних, можна, наприклад, зобразити як на рис.16.1.

Рис.16.1.Структура даних типу бінарне дерево.

Це дерево складається з шести елементів  (або  вершин).  Кожний елемент містить змістовну частину і два покажчики на інші вершини. У змістовній частині зберігається ідентифікатор, його тип, можливо  ще деяка інформація. Умовно на малюнку у  змістовній  частині  записані різні букви, що можна сприймати як позначення вершин. Оскільки кожна вершина має не більше двох ненульових покажчиків, дерево називається бінарним. Вершини  А, С, F,  що  не  мають  ненульових  покажчиків, називають листями. Сукупність усіх листів називається кроною дерева. Вершина D, на яку не показує  жоден  покажчик,  називається  коренем дерева.  Окремим  випадком  дерева  є  пусте  дерево  і  дерево,  що складається з однієї вершини.

Якщо у  дереві  є  покажчик  від  вершини   А   до   В,  то   В  називають прямим нащадком  (або  сином)   А.  Для  кожної  вершини відрізняють лівого і правого сина. Прямий нащадок   C   вершини   В, яка в свою чергу є прямим нащадком  вершини   A,  називається  також нащадком вершини  A. При цьому  В  та A  називають предками  вершини  C, і  В - безпосереднім предком (або батьком)  C. На рис.16.1  С  є нащадком вершин  В  та  D, а  В  є батьком лівого сина  A  та правого сина  C.

Для кожної вершини відрізняють ліве та  праве  піддерево.  Ліве піддерево містить лівого сина даної вершини і  усіх  його  нащадків. Отож,  лівий  син  є  коренем  лівого  піддерева.  Коренем   правого піддерева є правий син. На рис.16.1 ліве піддерево вершини   D   має корень  B, а праве - Е.

Відстанню  від  вершини   Х   до  кореня  називають   кількість покажчиків (ребер), що дозволяють пройти від кореня до  Х. Для цього поняття  застосовують  також  термін  рівень  вершини.   При   цьому вважають, що рівень кореня дорівнює  0.

Висотою піддерева називають  максимальну  різницю  між  рівнями листа цього  піддерева  і  його  кореня.  Висотою  дерева  називають максимальний рівень листа. У прикладі на рис.16.1 висота дерева - 2, а висота лівого і правого піддерева вершини  В - 1.

Для запам’ятовування упорядкованих елементів у бінарних деревах уводять певний порядок обходу вершин.  Одержали  розповсюдження  три порядки обходу (нумерації)  вершин  дерева,  шо  можна  означити  за допомогою рекурсивного правила:

    пронумеровати вершини дерева це означає:

    1) пронумеровати корень, потім ліве піддерево і після  цього  - праве;

    2) пронумеровати ліве піддерево, потім - праве  і  після  цього присвоїти номер кореню;

    3) пронумеровати  ліве  піддерево,  після  цього  -  корень,  і потім - праве піддерево.

Перше правило відповідає прямій нумерації  (або  зверху  униз); друге - зворотній (або знизу вгору); третє - внутрішній  (або  зліва направо). Саме третє правило  застосовується,  коли  бінарне  дерево використовують для утворення таблиць символів.

Розглянемо визначення номерів вершин при  внутрішній  нумерації для дерева на рис.16.1. Перед тим, як присвоювати номер  кореню   D, треба пронумеровати ліве піддерево з коренем  В.  Нумерації  вершини  В  передує присвоєння  номеру   1   вершині   А.  Потім  вершині   В  присвоюється номер 2, і після цього вершині  С - 3. Далі  корень   D  дерева одержує номер 4, і починається нумерація  правого  піддерева. Оскільки  Е  не має лівого сина, то ця вершина одержує номер  5,  і, нарешті, вершині  F  присвоюється номер 6.

Пошук  елемента  у   бінарному   дереві   здійснюється   шляхом послідовного  порівняння  цього  елемента  з  поточною  вершиною   і перехода  до  лівого  або  правого  сина  залежно   від   результату порівняння.  Процес  пошуку  починається  з  порівняння  елемента  з коренем. Отож, кількість порівнянь не перебільшує висоти  дерева,  і тому  доцільно  так  організовувати  дерева,  щоб  їх  висота   була мінімальна. Для цього  необхідно,  щоб  дерево  містило  максимальну кількість вершин усіх рівнів за винятком, можливо, останнього. Це означає,  що для кожного рівня  k, крім останнього у дереві є  2k  вершин. Дерево, що задовольняє цій  умові  називають  ідеально  збалансованим.  Якщо ідеально збалансоване дерево  Т  містить  n  вершин, то його  висота визначається як  H(T) = log2n, де А означає найбільше  ціле,  що не більше числа А, і називається підлогою числа  А.  

При включенні нового елемента у дерево (або вилученні з  нього) ідеальна збалансованість може порушитись. У найгіршому випадку після декількох змін структури дерева може утворитись  лінійний  ланцюжок, як показано на рис.16.2. У цьому випадку кількість вершин, що  треба проглядати при пошуку, може  досягати  n.  Тому  при  включенні  або вилученні вершини необхідно коректувати дерево так, щоб  зберігалась ідеальна збалансованість. Однак,  виявилося,  що  операція  корекції потребує великої кількості дій,  і  в  результаті  позитивний  ефект застосування ідеально збалансованих дерев втрачається.

Рис.16.2.Вироджене бінарне дерево – лінійний ланцюжок.

АВЛ-дерева

Цікаве  рішення  поданої  проблеми  було  знайдено   вченими   з Московського  державного  університету   Г.М.Адельсон-Вельським   та Е.М.Ландісом.   Вони   запропонували   використовувати   дерева   зі структурою,  що  дещо  відрізняється  від  ідеально   збалансованого дерева, але допускає відносно просту операцію корекції. Ці дерева на честь їх авторів назвали  АВЛ-деревами ( застосовують  також  термін збалансовані дерева).

                       a

                                 б

За означенням бінарне дерево називається збалансованим  тоді  і тільки тоді, коли висоти двох піддерев кожної вершини  відрізняються не більш ніж на одиницю. Приклади збалансованого і  відповідного  (з тією ж кількістю вершин) ідеально збалансованого дерев  показано  на рис.16.3.

Рис.16.3.Дерева: а) збалансоване, б) ідеально збалансоване.

Важлива властивість збалансованого дерева полягає  у  тому,  що його висота не більше, ніж, на 45%  перебільшує  висоту  відповідного ідеально  збалансованого  дерева  [4].  Тому   асимптотична   оцінка кількості елементарних операцій при пошуку дорівнює  О(log n).

Включення елемента у збалансоване дерево

Рис.16.4. Збалансоване  дерево

Нехай подано збалансоване дерево, елементи  якого  -  цілі  числа (рис.16.4)

Припустимо, необхідно включити у  це  дерево  елемент,  що  має значення  1. Тоді після послідовного розглядання вершини  8,  4,  2, з’ясовується, що цей елемент треба включити як лівого сина  елемента 2. При цьому у вершинах 2 та 4  збалансованість  зберігається,  а  у вершині  8   порушується.   Отже,   необхідно   виконати   корекцію. Виявляється, що це можна зробити за допомогою  лише  локальних  змін структури  дерева,  коли  треба  розглядати  лише  вершину,  у  якій порушується  збалансованість,  її  сина  та  онука.  Для   прикладу, показаного на рис.16.4, перетворення дерева зображено на рис.16.5.

            а

                    б

Рис.16.5.Дерево до перетворення (а) і після (б).

У поданому випадку  лівий  син  4  вершини  8,  у  якій  порушено збалансованість, стає батьком, а вершина 8 - правим сином. Вершина 6 включається у дерево як лівий син вершини 8. Слід  зауважити,  що  у процесі перетворення вершини переміщуються  тільки  у  вертикальному напрямку, зберігаючи відносне горизонтальне  розташування.  Оскільки внутрішня нумерація вершин відповідає порядку  обходу  вершин  зліва направо, то розглянуте перетворення не порушує цей порядок.

                                   а                                                    б

Рис.16.6. Перетворення дерева (ліве піддерево, лівий син). 

У  загальному  випадку  розглянуте  перетворення  можна  умовно подати у вигляді рис.16.6, де показано схему дерева до перетворення (а) і після (б). Перекреслений квадрат позначає останній включений  елемент, що викликав порушення збалансованості,  прямокутники  застосовуються для відображення піддерев.

Аналогічне   перетворення   можна   виконати,   якщо    елемент включається у праве  піддерево  правого  сина  вершини  з  порушеною збалансованістю. Дещо інша ситуація виникає, якщо  син  і  піддерево мають різні розташування (наприклад, син лівий, а піддерево  праве). В цьому випадку застосувати розглянуте перетворення не  можна.  Так, якби елемент включався у праве піддерево вершини  B  (рис.16.6),  то дане перетворення привело б до того,  що  порушення  збалансованості від вершини  A  перейшло до вершини  B.

У поданому випадку у перетворенні приймають участь син вершини  B (або онук вершини  A), як показано на рис.16.7. Тепер батьком стає онук  С, його лівим сином - колишній  батько B, а правим  сином  -  колишній  дід   A.  Зрозуміло,  що  включення елемента у  праве  піддерево  вершини   С   не  впливає  суттєво  на перетворення.

Алгоритм включення  елемента  у  дерево  істотно  залежить  від структури даних, що застосовується  для  зберігання  інформації  про стан дерева. Для прискорення перетворень дерева доцільно для  кожної вершини  запам’ятовувати  покажчик  збалансованості,   що   дорівнює різниці між висотою правого і лівого піддерев.

                                   а                                                    б

Рис.16.7. Перетворення дерева (ліве піддерево, правий син).

Структуру даних для зберігання дерева можна описати так

             type

               ptr = ^node;

               balance = [-1..+1];

               node = record

                 id : integer;

                 left, right : ptr;

                 bal : balance

               end

Алгоритм включення вершини у дерево складається з трьох етапів:

1)  прохід  шляхом  пошуку,  доки  не  буде знайдено місце для додавання нового елементу;

2) додавання нової вершини;

3) повернення шляхом  пошуку  з  перевіркою  збалансованості  у кожній вершині і можливого коректування дерева.

Повернення  здійснюється  за  рахунок  рекурсивної  організації процедури пошуку. Чотири різних випадки коректування  дерева: лівий син і ліве піддерево, лівий син і праве піддерево, правий син і ліве піддерево та правий син і праве  піддерево -  будемо   позначати відповідно  ll, lr, rl, rr.

procedure search(x:integer; var p:ptr; h:boolean);

 var p1,p2:ptr;

 begin

   if p = nil then {додавання вершини}

     begin

       new(p)

       with p^ do

         begin

           id := x; left := nil; right := nil;

           bal := 0; h := true

         end;

     end

   else if p^.id > x then

          begin

            search(x,p^.left,h);

            if h then {зросло ліве піддерево}

              case p^.bal of

                1: begin

                     p^.bal := 0; h := false

                   end;

                0: p^.bal := -1;

               -1: {коректування}

                   begin

                     p1 := p^.left; h := false;

                     if p1^.bal = -1 then

                       {перетворення ll}

                       begin

                         p^.left := p1^.right;

                         p1^.right := p; p1^.bal := 0;

                         p^.bal := 0; p := p1

                       end

                     else {перетворення lr}

                     begin

                       p2 := p1^.right;

                       p1^.right := p2^.left;

                       p2^.left := p1;

                       p^.left := p2^.right;

                       p2^.right := p;

                       if p2^.bal = -1 then p^.bal := 1

                       else p^.bal := 0;

                       if p2^.bal = +1 then

                         p1^.bal := -1

                       else p1^.bal := 0;

                       p := p2; p^.bal := 0

                     end;

                   end;

              end; {case}

          end {begin}

        else if p^.id < x then

        begin

          search(x,p^.right,h);

          if h then {зросло праве піддерево}

            case p^.bal of

              -1: begin

                    p^.bal := 0; h := false

                  end;

               0: p^.bal := 1;

               1: {коректування}

                  begin

                    p1 := p^.right; h := false;

                    if p1^.bal = 1 then

                    {rr-перетворення}

                    begin

                      p^.right := p1^.left;

                      p1^.left := p;

                      p1^.bal := 0; p^.bal := 0; p := p1

                    end;

                    else {rl-перетворення}

                    begin

                      p2 := p1^.left;

                      p1^.left := p2^.right;

                      p2^.right := p1;

                      p^.right := p2^.left;

                      p2^.left := p;

                      if p2^.bal = +1 then p^.bal := -1

                      else p^.bal := 0;

                      if p2^.bal = -1 then p1^.bal := 1

                      else p1^.bal := 0;

                      p := p2; p^.bal := 0

                    end;

                  end;

            end; {case}

        end; {begin}

 end.

Вилучення елемента зі збалансованого дерева

Вилучення виявляється  простим  у  випадку,  коли  елемент,  що вилучається, є лист або вершина з одним сином.  Якщо  ж  вилучається вершина, що має двох синів, то щоб не порушити  порядок  вершин,  її можна замінити або на найлівішу вершину правого  піддерева,  або  на найправішу  вершину  лівого.  Зупинемося,  наприклад,   на   другому варіанті.   В   усіх   випадках    вилучення,    якщо    порушується збалансованість, дерево треба  коректувати.  При  цьому  виконуються  подібні перетворення до тих, що і при включенні, тобто  ll, lr, rl, rr. Різниця полягає лише в тому, що треба враховувати інші  варіанти конфігурацій піддерев.

Розглянемо  приклади  вилучення  вершин  з   дерев.   Початкове збалансоване дерево показано  на  рис.16.8,  а  усі  наступні  -  на рис.16.9.  Вертикальна стрілка вказує  вершину,  що  вилучається,   символ    А  відповідає числу 10, а  В - 11. Після вилучення вершини 4 збалансованість порушується у вершині 3.   Застосування   у   цій   вершині    ll-перетворення    поновлює збалансованість. Вилучення вершини 8  зводиться  до  заміни   її  на найправішу вершину лівого піддерева, тобто на вершину  7.  Вилучення вершини 6  потребує  застосування  rr-перетворення.  

           

Рис. 16.8. Початкове збалансоване дерево.

           

а

           

б

     

           

в

           

г

        

д

е

є

              

Рис.16.9. Приклади вилучення вершин.

Вершина  5  при вилученні замінюється на вершину 3. Вилучення вершини  2  призводить до  порушення збалансованості   у   вершині   3,   а   застосування  rl-перетворення дає дерево, що показано  на  рис.16.9,д.  Вершина  1 вилучається очевидним чином. Вилучення вершини 7 складається з  двох етапів. Спочатку вершина 7 замінюється вершиною 3, а потім у вершині 3 застосовується  rr-перетворення.

Оскільки число елементарних операцій  при  корекції  дерева  не залежить від числа його вершин,  то  завжди  вилучення  елементу  зі збалансованого дерева можна виконати за  О(log n) операцій.

Розглянемо програмну реалізацію вилучення. У основній процедурі  del  відрізняють три випадки:

    1) вершини  х  у дереві нема;

    2) вершина  х  має не більш одного сина;

    3) вершина  х  має двох синів.

У третьому випадку викликається вспоміжна рекурсивна  процедура  del, яка знаходить найправішу вершину лівого піддерева і виконує заміну  покажчиків. У вершині, де порушується збалансованість викликається або процедура  balancel, або  balancer.

procedure balancel(var p:ptr; h:boolean);

    var p1, p2 : ptr; b1, b2 : balance;

    begin {ліве піддерево стало нижче}

      case p^.bal of

        -1: p^.bal = 0;

         0: begin

              p^.bal := 1; h := false

            end;

         1: begin {коректування}

              p1 := p^.right; b1 := p1^.bal;

              if b1 >= 0 then {rr-перетворення}

                begin

                  p^.right := p1^.left; p1^.left := p;

                  if b1 = 0 then

                    begin

                      p^.bal := 1; p1^.bal := -1;

                      h := false

                    end

                  else

                  begin

                    p^.bal := 0; p1^.bal := 0

                  end;

                  p := p1

                end;

              else {rl-перетворення}

              begin

                p2 := p1^.left; b2 := p2^.bal;

                p1^.left := p2^.right; p2^.right := p1;

                p^.right := p2.left; p2^.left := p;

                if b2 = +1 then p^.bal := -1

                else p^.bal := 0;

                if b2 = -1 then p1^.bal := 1

                else p1^.bal := 0; p := p2; p2^.bal := 0

              end;

            end;

      end; {case}

    end;{balancel}

    procedure balancer (var p: ptr; h: boolean);

    var p1, p2 : ptr; b1, b2 : balance;

    begin {праве піддерево стало нижче}

      case p^.bal of

        1: p^.bal := 0;

        0: begin

             p^.bal := -1; h := false

           end;

       -1: begin {коректування}

             p1 := p^.left; b1 := p1^.bal;

             if b1 <= 0 then {ll-перетворення}

               begin

                 p^.left := p1^.right; p1^.right := p;

                 if b1 = 0 then

                   begin

                     p^.bal := -1; p1^.bal := 1;

                     h := false

                   end

                 else

                 begin

                   p^.bal := 0; p1^.bal := 0

                 end

             else {lr-перетворення}

             begin

               p2 := p1^.right; b2 := p2^.bal;

               p1^.right := p2^.left; p2^.left := p1;

               p^.left := p2^.right; p2^.right := p;

               if b2 = -1 then p^.bal := 1

               else p^.bal := 0;

               if b2 = +1 then p1^.bal := -1

               else p1^.bal := 0;

               p := p2; p2^.bal := 0

             end;

           end;

      end;{case}

    end;{balancer}

    procedure delete(x:integer;var p: ptr; h: boolean);

    var q : ptr;

    procedure del(var r: ptr; h: boolean);

    begin

      if r^.right not nil then

        begin

          del(r^.right,h);

          if h then balancer(r,h)

        end

      else

        begin

          p := r; r := r^.left; h := true

        end;

    end;{del}

    begin {delete}

      if p = nil then {ідентифікатора у дереві нема}

      absence

      else

      if p^.id > x then

        begin

          delete(x,p^.left,h);

          if h then balancel(p,h)

        end

      else

      if p^.id < x then

        begin

          delete(x,p^.right,h);

          if h then balancer(p,h)

        end

      else {вилучення p^}

      begin

        q := p; if q^.right = nil then

                  begin

                    p := q^.left; h := true

                  end

                else if q^.left = nil then

                       begin

                         p := q^.right; h := true

                       end

                     else

                     del(p^.left,h);

                     if h then balancel(p,h)

      end;

      dispose(q)

    end;{delete}


 

А также другие работы, которые могут Вас заинтересовать

33677. Виды осмотра в уголовно-процессуальном законодательстве 12.97 KB
  Выделяют три основных этапа осмотра места происшествия: начальный основной и дополнительный этапы. Статьей 178 УПК установлен общий порядок осмотра трупа на месте его обнаружения. Осмотр трупа состоит из двух стадий: общего и детального осмотра.
33678. Особенности осмотра трупа на месте происшествия и фиксация результатов 15.45 KB
  Как относительно друг друга расположены части тела как голова относительно частей помещения Какая имеется одежда в каком она состоянии фасон модель Если юрист не знает то пусть не говорит сколько хлопка синтетики. Если на открытых частях тела есть признаки крови и т. то нужно начинать с частей тела а не одежды. Осмотр закрытых частей тела.
33679. Тактика освидетельствования 25.5 KB
  Освидетельствование осуществляется для установления на теле человека следов преступления наличия особых примет и иных признаков позволяющих судить о связи данного человека с расследуемым событием. При судебномедицинском освидетельствовании разрешаются специальные вопросы из области судебной медицины о причинах и давности причинения телесных повреждений о степени их тяжести о врожденных или приобретенных анатомических или физических аномалиях и др. Следственное освидетельствование позволяет выяснить такие вопросы: имеются ли на теле...
33680. Допрос 29 KB
  При проведении допроса в конфликтной ситуации следователь использует следующие тактические приемы: следователь и подозреваемый либо обвиняемый разъясняет допрашиваемому значение чистосердечного признания и дачи правдивых показаний; выявляет мотивы дачи ложных показаний и устраняет эти мотивы; убеждает с помощью логических доводов в бессмысленности попыток дачи ложных показаний; максимально детализирует и конкретизирует показания допрашиваемого; предъявляет доказательства изобличающие допрашиваемого начиная с самого веского либо наоборот;...
33681. Допрос подозреваемого (обвиняемого) 12.71 KB
  В соответствии с этим следователю необходимо попытаться выяснить причины конфликта и направить усилия на их устранение для формирования условия получения достоверных показаний. Основные приемы установления психологического контакта с допрашиваемым в конфликтной ситуации: 1 убедить допрашиваемого в объективности следователя внушить уважение к следователю; 2 вызвать интерес к даче показаний к процессу общения со следователем; 3 проявлять заботу о соблюдении прав допрашиваемого и об удовлетворении его за конных интересов; 4 создать и...
33682. Бесконфликтная ситуация допроса 11.48 KB
  В связи с объективным характером этой ситуации тактическая задача следователя при допросе может быть сведена к одному но весьма существенному положению: не сделать ситуацию допроса конфликтной не спровоцировать своими действиями поведением конфликт с допрашиваемым. Дело в том что успех допроса как и любого иного вида человеческого общения зависит не только от объективных но и от субъективных факторов. Необдуманная форма вызова лица на допрос оказавшаяся неприятной или нежелательной для допрашиваемого длительное ожидание под дверями...
33683. ТАКТИЧЕСКИЕ ПРИЕМЫ ОЧНОЙ СТАВКИ 12.34 KB
  Задачи очной ставки: 1 общие: а проверка имеющихся доказательств; б получение новых доказательств; в установление истины по спорным обстоятельствам; 2 конкретные: а преодоление добросовестного заблуждения допрашиваемого; б разоблачение лжи одного из допрашиваемых; в разоблачение ложного алиби; г разоблачение самооговора или оговора одного допрашиваемого другим; д разоблачение инсценировок преступления; е выяснение причин происхождения существенных противоречий; ж изучение личности допрашиваемого; з проверка и оценка следственных...
33684. Тактика подготовки и проведения предъявления для опознания живых лиц в натуре и по фотографии 14.53 KB
  тактика подготовки и проведения предъявления для опознания живых лиц в натуре и по фотографии Предъявление для опознания это самостоятельное следственное действие которое состоит в отождествлении ранее воспринимаемого объекта по его мысленному образу. Цель предъявления для опознания идентификация объекта который ранее воспринимал опознающий в связи с совершением преступления. Подготовка к предъявлению для опознания является обязательным условием успеха этого следственного действия. Она включает в себя: определение конкретной цели...