Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями

Нажмите для полного просмотра!

Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №2

Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №3

Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №4

Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №5

Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №6

Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями, слайд №7

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Лекція 1/13. Організація таблиць та індексів впорядкування у вигляді масивів та структур з посиланнями. Доклад-сообщение содержит 7 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

Слайд 2

Описание слайда:

Опис прикладу бінарного дерева Найпростіша реалізація цього методу базується на впорядкуванні елементів через бінарне дерево, в якому до кожного вузла може бути "підвішено" не більше двох піддерев. Кожний вузол дерева являє собою сформований елемент таблиці, причому кореневий вузол є першим елементом. Перші за порядком вказівники посилаються на елементи з меншим аргументом, а другі – на елементи з більшим аргументом. Припустимо тепер, що до таблиці необхідно записати ім’я “D”. Для нього обирається ліве піддерево, тому що “D” < “G” знаходиться в корені. Тепер запишемо ім’я “М”. Тому що “G” < “N”, для збереження “М” обирається праве піддерево вузла, що зберігає ім’я “G”. I, насамкінець, запишемо ім’я “Е”. Тому що “E” < “G”, йдемо за лівою дугою i потрапляємо на ім’я “D”. Оскільки “D” < ”E”, то обираємо дугу, що веде вправо від “D”. Принцип побудови бінарного дерева такий, що для дерев з однаковим вмістом можна побудувати багато різних варіантів, які відрізняються коренями та проміжними вершинами. Кращі характеристики мають збалансовані дерева, тобто такі, в яких кількість рівнів зв’язків в ієрархії елементів не відрізняється за будь-якою парою шляхів більш ніж на 1. Формальну специфікацію обмежень пошуку в бінарних деревах можна визначити через відношення порядку елементів сусідніх рівнів: Ai+1,2j-1 < Aij < Ai+1,2j, де i – номер рівня елементів, j – номер елемента на відповідному рівні.

Слайд 3

Описание слайда:

Приклад бінарного дерева ┌─────┬─────┬─────┐ │ “G” │ptr D│ptr M│ └─────┴──┬──┴──┬──┘ ┌────────┐ ┌──┴──┬─────┬─────┐ ┌──┴──┬─────┬─────┐ │ “D” │ptr A│ptr E│ │ “M” │null │null │ └─────┴───┬─┴──┬──┘ └─────┴─────┴─────┘ ┌───────┐ ┌──┴──┬─────┬─────┐ ┌──┴──┬─────┬─────┐ │ “A” │null │ptr B│ │ “E” │null │ptr F│ └─────┴─────┴──┬──┘ └─────┴─────┴──┬──┘ ┌───

Слайд 4

Описание слайда:

Опис прикладу B-дерева Подальший розвиток методів роботи з деревоподібними структурами призвів до використання більш розгалужених деревоподібних структур, що одержали назву В-дерев. В них зберігаються відношення впорядкування зв’язків вузлів i додаються відношення впорядкування внутрішніх елементів одного вузла, які мають бути узгоджені. Для лексикографічних порівнянь це однакові відношення аргументів попередніх та наступних елементів. Вузли В-дерева зберігають інформацію про декілька впорядкованих елементів. Звичайно кількість елементів у вузлі невелика i лежить в межах 3

Слайд 5

Описание слайда:

Приклад B-дерева ┌───┬─────┬───┬─────┬───┬─────┬───┬─────┐ │0/0│ptrD│”E”│ptr>E│”X”│ptr>X│ └───┴──┬──┴───┴──┬──┴───┴──┬──┴───┴──┬──┘ ┌───────┐ null ┌─┴─┬─────┬───┬─────┬───┬─────┬─┬────┐ │ │1/0│ptrA│”B”│ptr>B│.│null│ │ └───┴──┬──┴───┴──┬──┴───┴──┬──┴─┴────┘ │ null null null │ ┌────────────────H│.│ └───┴──┬──┴───┴──┬──┴───┴──┬──┴─┴─┬ null null null

Слайд 6

Описание слайда:

ПОБУДОВА ПРОЦЕДУР ВИЗНАЧЕННЯ МІР БЛИЗЬКОСТІ ДЛЯ КЛЮЧОВИХ ПОЛІВ При пошуку помилково підготовлених слів в текстових редакторах та процесорах часто виникає потреба в визначенні схожості ключів пошуку. Такі дії часто виконуються в текстовому процесорі MS Word. Вони можуть будуватися на підрахунку кількості однакових ne, схожих літер nsi за i-м типом схожості, а також літер, які не мають відповідника в іншому ключі і можуть спиратися на абсолютні і відносні формульні критерії схожості. Схожість літер може визнача-тися залежно від випадку аналізу за схожістю написання літер в різних алфавітах ns1, за близькістю комп’ютерних кодів ns2 та за близькістю розташування на клавіатурі ns3, а також з урахуванням кількості літер ns4, які не мають відповідників в обох ключах. При створенні програм порівняння за мірою близькості треба побудувати загальний критерій близькості як монотонну функцію f(ns1, ns2, ns3, ns4) в одному напрямку від ns1, ns2 і ns3 та в іншому напрямку від ns4. Крім того, попередньо необхідно організувати підрахунок ns1, ns2, ns3 і ns4, при порівняльному перегляді ключів, які порівнюються. Результат пошуку за таким критерієм може бути неоднозначним, навіть за умови вимоги однозначності ключів. На алгоритм лінійного пошуку це практичного не впливає, а у випадку базового двійкового пошуку доцільно починати пошук навколо найближчого ключа, знайденого за відношенням порядку.

Слайд 7

Описание слайда:

Підсумки Найбільш зручними методами організації роботи з впорядкованими таблицями є побудова таблиць та індексів з деревоподібними структурами. Двійкові дерева часто використовуються для побудови індексів в базах даних і системних програмах Розгалужені B-дерева використовуються для побудови комбінованих індексів в базах даних і системних програмах