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}


 

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

27266. Недоліки ринку і необхідність сполучення ринкового механізму з державним регулюванням економіки. Економічні функції держави та система методів державного впливу на економіку 25.09 KB
  На сучасному етапі основними завданнями державних органів управління в Україні є: створення умов для зайнятості працездатного населення і забезпечення соціального захисту громадян; охорона навколишнього середовища та забезпечення раціонального природокористування; формування фінансовобюджетної політики та її реалізація; кредитногрошове регулювання контроль за грошовим обігом; проведення цінової політики; здійснення зовнішньоекономічної діяльності та організація міжурядових відносин створення державного валютного фонду; розвиток місцевого...
27267. Економічні потреби та їх класифікація. Закон зростання потреб 27.11 KB
  Економічні потреби та їх класифікація. Закон зростання потреб. Кінцевою метою виробництва є задоволення різноманітних потреб людини як особистості споживача і виробника. Виробництво яке працює не з метою задоволення потреб людини чи суспільства тобто заради власне виробництва є безглуздою витратою обмежених ресурсів землі корисних копалин довкілля економічних благ і робочої сили.
27268. Економіка як специфічна сфера людської діяльності та об’єкт наукового пізнання. Основні напрямки розвитку теоретичної економічної науки 20.58 KB
  До духовної сфери діяльності відноситься мистецтво сфера послуг і наука. У Віктора Гюго є таке висловлювання: Наука безперервно рухається вперед перекреслюючи саму себе. Наука є складовою частиною духовної культури людства.Отже наука виступає як: специфічна форма суспільної свідомості основою якої є система знань; процес пізнання закономірностей об'єктивного світу; певний вид суспільного розподілу праці; процес виробництва знань і їх використання.
27269. Предмет і функції політичної економії. Роль теоретичної і економічної науки у формуванні сучасного економічного мислення 20.56 KB
  Роль теоретичної і економічної науки у формуванні сучасного економічного мислення. Мислення це психологічний процес із відкриттям нового знання вирішення проблеми на основі переробки отриманої інформації. Мислення є найбільш загальною і опосередкованою формою психологічного відображення що встановлює звязок між пізнаваними обєктами. Економічне мислення складова мислення людини взагалі.
27270. Головні методологічні підходи до вивчення економічних явищ і процесів. Загальнонаукові та специфічні методи досліджень економічної дійсності 25.05 KB
  Як метод науки воно означає сукупність або систему прийомів та операцій які застосовуються економістами для збору систематизації та аналізу економічних фактів явищ і процесів. Під індукцією розуміємо виведення принципів законів э аналізу фактів. Метод індукції означає хід думок від аналізу фактів до теорії від часткового до загального. Важливим засобом пізнання економічних процесів і явищ є використання методів аналізу і синтезу.
27271. Закони, принципи і категорії політичної економіки. Етапи пізнання економічної діяльності. Позитивна і нормативна економіка 18.25 KB
  Кожна наука у процесі пізнання об'єктивної реальності займається систематизацією фактів подій процесів щоб виявити певні причини і наслідкові зв'язки між ними та відкрити і сформулювати економічні категорії закони і принципи. Економічні закони відображають внутрішні найсуттєвіші стабільні такі що постійно повторюються причиннонаслідкові взаємозв'язки і взаємозалежності між економічними процесами і явищами. Вони як і закони природи мають об'єктивний характер і виражають причиннопослідовний зв'язок між компонентами явища що...
27272. Процес праці та його основні елементи.Виробництво і праця.Суспільний характер виробництва 19.77 KB
  Процес праці та його основні елементи. Завдяки праці накопичено потенціал продуктивних сил суспільні багатства сформовано сучасну цивілізацію. Прогрес людства неможливий без праці. Отже технічний прояв праці у виробництві відображає її зміст під яким розуміється сукупність трудових функцій працівників.
27273. Економічні ресурси та їх класифікація.Фактори виробництва 17.54 KB
  Обмеженість ресурсів. У певній країні або у масштабі планети обсяги економічних ресурсів природно обмежені.Про обмеженість людських ресурсів у межах планети говорити недоцільно оскільки у світі налічується до 800 млн. Отже обмеженість людських ресурсів і засобів виробництва зумовлена сутністю природою економічної системи.
27274. Економічна система, її структурні елементи та цілі. Типи і еволюція економічних систем 25.31 KB
  їх зміст виявляється у взаємодії людини і природи яка здійснюється у процесі праці виробництва матеріальних і нематеріальних або економічних благ. У такій взаємодії суб'єктом є трудовий колектив сукупний працівник людство а об'єктом природа. Продуктивні сили фактори які забезпечують перетворення речовини природи відповідно до потреб людей створюють матеріальні й духовні блага визначають зростання продуктивності суспільної праці завдяки своєму рівню та характеру порізному впливають на еволюцію певних типів форм власності. Вона...