ПЕРЕЛІК ДИСЦИПЛІН:
  • Адміністративне право
  • Арбітражний процес
  • Архітектура
  • Астрологія
  • Астрономія
  • Банківська справа
  • Безпека життєдіяльності
  • Біографії
  • Біологія
  • Біологія і хімія
  • Ботаніка та сільське гос-во
  • Бухгалтерський облік і аудит
  • Валютні відносини
  • Ветеринарія
  • Військова кафедра
  • Географія
  • Геодезія
  • Геологія
  • Етика
  • Держава і право
  • Цивільне право і процес
  • Діловодство
  • Гроші та кредит
  • Природничі науки
  • Журналістика
  • Екологія
  • Видавнича справа та поліграфія
  • Інвестиції
  • Іноземна мова
  • Інформатика
  • Інформатика, програмування
  • Юрист по наследству
  • Історичні особистості
  • Історія
  • Історія техніки
  • Кибернетика
  • Комунікації і зв'язок
  • Комп'ютерні науки
  • Косметологія
  • Короткий зміст творів
  • Криміналістика
  • Кримінологія
  • Криптология
  • Кулінарія
  • Культура і мистецтво
  • Культурологія
  • Російська література
  • Література і російська мова
  • Логіка
  • Логістика
  • Маркетинг
  • Математика
  • Медицина, здоров'я
  • Медичні науки
  • Міжнародне публічне право
  • Міжнародне приватне право
  • Міжнародні відносини
  • Менеджмент
  • Металургія
  • Москвоведение
  • Мовознавство
  • Музика
  • Муніципальне право
  • Податки, оподаткування
  •  
    Бесплатные рефераты
     

     

     

     

     

     

         
     
    Динамічні структури даних: двійкові дерева
         

     

    Інформатика, програмування

    Динамічні структури даних: двійкові дерева

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

    В двійковому (бінарному) дереві кожен вузол може бути пов'язаний не більш як двома іншими вузлами. Як розширення двійкове дерево визначається так: двійкове дерево буває або порожнім (не містить жодного вузла), або містить вузол, званий коренем, а також два незалежних піддереві - ліве піддерево і праве піддерево.

    Двійкове дерево пошуку може бути або порожнім, або воно має таку властивість, що кореневий елемент має більше значення вузла, ніж будь-який елемент в лівому піддереві, і менше або рівне, ніж елементи в правому піддереві. Зазначене властивість називається характеристичним властивістю двійкового дерева пошуку та виконується для будь-якого вузла такого дерева, включаючи коріння. Далі будемо розглядати тільки двійкові дерева пошуку. Таку назву двійкові дерева пошуку отримали з тієї причини, що швидкість пошуку в них приблизно така ж, що і в впорядкованих масивах: O (n) = C • log2n (в гіршому випадку O (n) = n).

    Приклад. Для набору даних 9, 44, 0, -7, 10, 6, -12, 45 побудувати двійкове дерево пошуку.

    Згідно визначення двійкового дерева пошуку число 9 поміщаємо в корінь, всі значення, менші його - на ліве піддерево, більші або рівні - на праве. У кожному піддереві черговий елемент можна розглядати як корінь і діяти за того ж алгоритму. У підсумку отримуємо

    Виділимо типові операції з двiйковими деревами пошуку:

    додавання елемента в дерево;

    видалення елемента з дерева;

    обхід дерева (для друку елементів і т.д.);

    пошук у лісі.

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

    Нехай двійкове дерево пошуку описується таким типом

    Type BT = LongInt; U = ^ BinTree; BinTree = Record Inf: BT; L, R: U End;

    Покажемо два варіанти додавання елемента в дерево: ітеративний і рекурсивний.

    (Ітеративний варіант додавання елемента в дерево, Turbo Pascal)

    Procedure InsIteration (Var T: U; X : BT);

    Var vsp, A: U;

    Begin

    New (A); A ^. Inf: = X; A ^. L: = Nil; A ^. R: = Nil;

    If T = Nil Then T: = A

    Else Begin vsp: = T;

    While vsp Nil Do

    If A ^. Inf < vsp ^. Inf

    Then

    If vsp ^. L = Nil Then Begin vsp ^. L: = A; vsp: = A ^. L End Else vsp: = vsp ^. L

    Else

    If vsp ^. R = Nil Then Begin vsp ^. R : = A; vsp: = A ^. R End Else vsp: = vsp ^. R;

    End

    End;

    (Рекурсивний варіант додавання елемента в дерево, Turbo Pascal)

    Procedure InsRec (Var Tree: U; x: BT);

    Begin

    If Tree = Nil

    Then Begin

    New (Tree);

    Tree ^. L: = Nil;

    Tree ^. R: = Nil;

    Tree ^. Inf: = x

    End

    Else If x

    Then InsRec (Tree ^. L, x)

    Else InsRec (Tree ^. R, x)

    End;

    Аналогічно на C ++.

    typedef long BT;

    struct BinTree (

    BT inf;

    BinTree * L; BinTree * R;

    );

    /* Ітеративний варіант додавання елемента в дерево, C + + */

    BinTree * InsIteration (BinTree * T, BT x)

    (BinTree * vsp, * A;

    A = (BinTree *) malloc (sizeof (BinTree));

    A-> inf = x; A-> L = 0; A-> R = 0;

    if (! T) T = A;

    else (vsp = T;

    while (vsp)

    (if (A-> inf inf)

    if (! vsp-> L) (vsp-> L = A; vsp = A-> L;)

    else vsp = vsp-> L;

    else

    if (! vsp-> R) (vsp-> R = A; vsp = A-> R;)

    else vsp = vsp-> R;

    )

    )

    return T;

    )

    /* Рекурсивний варіант додавання елемента в дерево, C + + */

    BinTree * InsRec (BinTree * Tree, BT x)

    (

    if (! Tree) (Tree = (BinTree *) malloc (sizeof (BinTree));

    Tree-> inf = x; Tree-> L = 0; Tree-> R = 0;

    )

    else if (x inf) Tree-> L = InsRec (Tree-> L, x);

    else Tree-> R = InsRec (Tree-> R, x);

    return Tree;

    )

    Існує декілька способів обходу (проходження) усіх вузлів дерева. Три найбільш часто використовуваних з них називаються обхід в прямому (префіксном) порядку, в обхід зворотному (постфіксном) порядку і обхід у внутрішньому порядку (або симетричний обхід). Кожен з обходів реалізується з використанням рекурсії.

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

    (Turbo Pascal)

    Procedure PrintTree (T: U);

    begin

    if T Nil

    then begin PrintTree (T ^. L); write (T ^. inf: 6); PrintTree (T ^. R) end;

    end;

    // C + +

    void PrintTree (BinTree * T)

    (

    if (T) (PrintTree (T-> L); cout infR );}

    )

    Реалізуємо функція, що повертає true (1), якщо елемент присутній в дереві, і false (0) - В іншому випадку.

    (Turbo Pascal)

    function find (Tree: U; x: BT): boolean;

    begin

    if Tree = nil then find: = false

    else if Tree ^. inf = x then Find: = True

    else if x

    then Find: = Find (Tree ^. L, x)

    else Find: = Find (Tree ^. R, x)

    end;

    /* C + + */

    int Find (BinTree * Tree, BT x)

    (if (! Tree) return 0;

    else if (Tree-> inf == x) return 1;

    else if (x inf) return Find (Tree-> L, x);

    else return Find (Tree-> R, x);

    )

    За порівнянні з попередніми завдання видалення вузла з дерева реалізується кілька складніше. Можна виділити два випадки видалення елемента x (випадок відсутності елемента в дереві є виродженим):

    1) вузол, що містить елемент x, має ступінь не більше 1 (ступінь вузла - число піддерев, що виходять з цього вузла);

    2) вузол, що містить елемент x, має ступінь 2.

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

    Набагато складніше, якщо видаляється вузол має два піддереві. У цьому випадку потрібно замінити видаляється елемент самим правим елементом з його лівого піддереві.

    (Turbo Pascal)

    function Delete (Tree: U; x: BT): U;

    var P, v: U;

    begin

    if (Tree = nil)

    then writeln ( 'такого елемента в дереві немає!')

    else if x

    else

    if x> Tree ^. inf

    then Tree ^. R: = Delete (Tree ^. R, x) (випадок 1)

    else

    begin (випадок 1)

    P: = Tree;

    if Tree ^. R = nil

    then Tree: = Tree ^. L

    else if Tree ^. L = nil

    then Tree: = Tree ^. R

    else begin

    v: = Tree ^. L;

    while v ^. R ^. R nil do v: = v ^. R;

    Tree ^. inf : = V ^. R ^. Inf;

    P: = v ^. R;

    v ^. R: = v ^. R ^. L;

    end;

    dispose (P);

    end;

    Delete: = Tree

    end;

    (C ++}

    BinTree * Delete (BinTree * Tree, BT x)

    ( BinTree * P, * v;

    if (! Tree) cout L = Delete (Tree-> L, x);

    else if (x> Tree-> inf) Tree-> R = Delete (Tree-> R, x);

    else (P = Tree;

    if (! Tree-> R) Tree = Tree-> L;// випадок 1

    else if (! Tree-> L) Tree = Tree-> R;// випадок 1

    else (v = Tree-> L;

    while (v-> R-> R) v = v-> R;// випадок 2

    Tree-> inf = v-> R-> inf;

    P = v-> R; v-> R = v-> R-> L;

    )

    free (P);

    )

    return Tree;

    )

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

    Список літератури

    Для підготовки даної роботи були використані матеріали з сайту http://comp-science.narod.ru

         
     
         
    Реферат Банк
     
    Рефераты
     
    Бесплатные рефераты
     

     

     

     

     

     

     

     
     
     
      Все права защищены. Reff.net.ua - українські реферати ! DMCA.com Protection Status