Lab_07

Створення і ведення 2-3 та 2-3-4 дерев: Методичні вказівки до лабораторної роботи N9 з курсу «Алгоритми і структури даних» для студентiв базового напрямку 6.050101 «Комп’ютернi науки» / Укл.: А.Б.Керницький, П.Ю.Денисюк, М.Р.Мельник. - Львiв: НУЛП, 2009.- 19 с.

Відповідальний за випуск Ткаченко С.П., канд.техн.наук, доц.

1. МЕТА РОБОТИ

Ознайомитися iз способом подання даних в оперативнiй пам’ятi ЕОМ у

виглядi 2-3 і 2-3-4 дерев. Оволодiти методами роботи iз 2-3 та 2-3-4 деревами.

2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI

2.1Визначення 2-3 дерева

2-3-деревом називається структура даних, яка є Б-деревом порядку 3, у якій кожний вузол, що не є листом, має двох чи трьох нащадків, а довжини всіх шляхів із кореня в листки однакові. Порожнє дерево або дерево, що складається з 1 вузла, також є 2-3-деревом. Листки містять ключі і пов’язану з ними інформацію. Всі листки впорядковані зліва направо у відношенні строгого порядку (<). Ключ будь-якого листка є меншим його правого брата, і більшим за його лівого брата.

2-3 дерева називаються сильно розгалуженими деревами.

Лема. Нехай Т буде 2-3-деревом висоти h. Кiлькiсть вузлів дерева Т міститься між 2^(h+1)-1 i (3^(h+1))/2, а кiлькiсть листків між 2^h i 3^h.

Лінійно впорядковану множину S можна зобразити 2-3-деревом, приписавши всі елементи листкам дерева. Елементи множини розташовуються у листках дерева, при цьому, якщо елемент a розташовується лівіше від елемента b, справедливе відношення a<b. Припускається, що впорядковування елементів відбувається тільки по значеннях одного поля. Це поле називається ключем.

Елемент, приписаний листку l, позначається Е[l]. У кожному вузлі V, що не є листком, вимагаються два типи даних: M[V] i R[V]. M[V]- найменший елемент множини S у піддереві, коренем якого служить другий син вузла V; R[V] – найменший елемент множини S у піддереві, коренем якого є третій син вузла V, якщо він є. Значення M i R, приписані вузлам, дають змогу шукати елемент, починаючи з кореня способом, аналогічним двійковому пошуку. Операцію НАЛЕЖАТИ можна виконати на множині з n елементів за час О(log n).

Розглянемо набір операцій:

1)ВСТАВЛЯННЯ;

2)ВИДАЛЕННЯ;

3)НАЛЕЖНІСТЬ.

2.1.1 Вставлення елемента у 2-3 дерево

Щоб вставити новий елемент а, необхідно знайти місце для нового листка l, який буде містити а. Для цього шукають елемент а в дереві. Якщо дерево містить більше вiд одного елемента, то пошук а закiнчується у вузлі f, що має двох або трьох синів, які є листками.

Якщо з вузла f виходить два листки l1 i l2, то ми просто робимо елемент а третім сином, розташовуючи його у правильному порядку серед інших синів. Переписуємо два числа у вузлі f у відповідності з новою ситуацією. Якщо а<E[l1] (наприклад а=2), то l робимо найлівішим сином вузла f і приймаємо M[f]=E[l1] i R[f]=E[l2] (рис.2,а); якщо E[l1]<a<E[l2] (наприклад а=6), то l робимо середнім сином вузла f і приймаємо M[f]=a i R[f]=E[l2] (рис.2,б) і якщо a>E[l2] (наприклад а=10), то l робимо найправішим сином вузла f і приймаємо M[f]= E[l2] i R[f]=а (рис.2,в);

Рис.1. У вузла f є два сина

Рис.2 Варіанти вставляння елемента а у вузол f у якого є два сина

Приклад 1. Якщо у 2-3 дерево, зображене на рис.3. вставляється елемент 18, то отримується дерево, зображене на рис.4.

Рис.3 2-3 дерево перед вставлянням елемента 18

Рис.4. 2-3 дерево після вставляння елемента 18

Тепер припустимо, що у f уже є три листки l1, l2, l3. Зробимо l вiдповiдним сином вузла f. Тепер f має чотирьох синiв. Щоб зберегти 2-3 властивiсть, утворимо новий вузол g. Два лiвих сина залишаться синами вузла f, а два правих переробимо у синiв вузла g. Потiм зробимо g братом вузла f, зробивши його сином батька вузла f. Якщо батько вузла f мав двох синiв, то на цьому зупиняємося. Якщо ж трьох, то потрiбно рекурсивно повторювати цю процедуру доти, поки у всiх вузлiв у деревi залишиться не бiльше від трьох синiв. Якщо у кореня виявиться чотири сина, утворимо новий корiнь с з двома новими синами, кожен з яких буде мати в якостi двох своїх синiв двох iз чотирьох синiв старого кореня.

Приклад 2. Якщо у 2-3 дерево, зображеному на рис.4. вставляється елемент 10, то новий лист із мiткою 10 потрiбно зробити третім сином вузла b (рис.5).

d

10

Рис. 5. Порушення умови 2-3 дерева у вузлі b

Оскiльки у b уже є три сина, будуємо новий вузол b'. Потiм робимо листки 7 i 8 синами вузла b, а листки 10 i 12 - синами вузла b'. Тепер робимо b' сином вузла d (рис.6). Але оскiльки в d вже є три сина, будуємо новий вузол d'. Робимо вузли a i b синами старого вузла d, а вузли b' і c - синами нового вузла d'. Нарешті утворюємо новий корінь r і робимо d і d' його синами. Отримане дерево зображене на рис 3.

Рис. 6. Порушення умови 2-3 дерева у корені d

Рис. 7. 2-3 дерево після вставляння елемента 10

2.1.2 Видалення елемента з 2-3 дерева

При видаленні листка може трапитися так, що батько f цього листка залишиться тільки з одним сином. Якщо вузол f є коренем, то єдиний син стає новим коренем дерева. Для випадку, коли вузол f не є коренем, позначимо його батька як r. Якщо цей батько має іншого сина, розташованого зліва або праворуч від вузла f, і цей син має трьох синів, то один з них стає сином вузла f. Таким чином, вузол f матиме двох синів.

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

Приклад 3. Видалимо елемент 10 із дерева, представленого на рис. 7. Після видалення цього елементу його батько матиме тільки одного сина. Але його "дідусь" має іншого сина, у якого, у свою чергу, є три сини: елементи 16, 18 і 19. Цей вузол знаходиться праворуч від неповного вузла, тому листок із найменшим елементом 16 переноситься у неповний вузол. У результаті отримаємо дерево, показане на рис. 8.

Рис. 8. 2-3 дерево після видалення елемента 10

Нехай далі потрібно видалити з отриманого дерева елемент 7. Після видалення його батько матиме тільки одного сина 8, а його "дідусь" не має синів з трьома "дітьми". Тому робимо елемент 8 "братом" елементів 2 і 5, як показано на рис. 9.а. На цьому рисунку вузол, помічений зірочкою, має тільки одного сина, а його батько не має синів з трьома "дітьми". Тому ми видаляємо помічений вузол, приєднуючи його сина до вузла, розташованого праворуч від поміченого вузла. Тепер корінь матиме тільки одного сина, тому він також віддаляється. У результаті отримаємо дерево, показане на рис. 9.б.

Рис. 9 Кроки видалення вузла 7 та редукції 2-3 дерева а) у вузла d лише один нащадок, що порушує правило існування 2-3 дерева, б) результуюче 2-3

дерево

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

отримати шляхом рекурсивного застосування алгоритму ВИДАЛЕННЯ, який викликається для кожного вузла, що формують шлях, який починається від кореня дерева. Ситуації, що виникають при цьому, враховані при написанні програми (див. у додатках), що реалізовує оператор DELETE.

2.1.3 Типи даних для 2-3 дерев

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

При написанні програм на мові Pascal батьки листків повинні бути записами, що містять два поля дійсних чисел (ключі найменших елементів у другому і в третьому піддеревах) і три поля вказівників на елементи. Батьки цих вузлів є записами, що складаються з двох полів дійсних чисел і трьох полів вказівників на батьків листків. Таким чином, різні рівні 2-3 дерева мають різні типи даних (вказівники на елементи або вказівники на вузли).

Ця ситуація викликає утруднення при програмуванні на мові Pascal операторів, що виконуються над 2-3 деревами. Проте мова Pascal має механізм, варіант структури record (запис), який дозволяє працювати з вузлами 2-3 дерева, які мають різний тип даних. У лістингу наведено оголошення типів даних для вузлів 2-3 дерева, а також для типу даних SET (множина), що представляє 2-3 дерево, у вигляді вказівників на корінь цього дерева.

Лістинг 1. Оголошення типів даних вузлів 2-3 дерева type

elementtype = record key: real;

{ оголошення інших полів, якщо необхідно }

end;

nodetype = {leaf, interior);

{ оголошення типу вузла, який містить поля leaf і interior }

twothreenode = record case kind: nodetype of

leaf: (element: elementtype);

interior: (firstchild, secondchild, thirdchild: ↑twothreenode; lowofsecond, lowofthird: real)

end;

SET = ↑twothreenode;

2.2 2-3-4 дерева

2-3-4-деревом (також називається 2-4 дерево) називається структура даних, яка є Б-деревом порядку 4, у якій кожний вузол, що не є листом, має двох, трьох або чотирьох нащадків, а довжини всіх шляхів із кореня в листки

третім сином, розташовуючи його у правильному порядку серед інших синів (рис.11). Аналогічно потрійним вузол можна перетворити на 4-ний (рис.12).

Рис.12. Додавання нового сина до подвійного вузла

Рис.13. Додавання нового сина до потрійного вузла

Приклад 4. Наприклад, елемент із ключем 240 ми могли б додати у дерево зображене на рис. 11 просто додавши його (і іншу гілку) до вузла, який містить ключ 190.

Але як нам бути якщо новий елемент повинен бути вставлений в 4-ний вузол? Якщо на нашому шляху від кореня дерева ми зустрінемо 4-ний вузол, то ми розщеплюватимемо йог на два подвійних вузла і переміщати середній елемент у батьківський вузол. Це гарантує відсутність проблеми вставки середнього елемента колишнього 4-ного вузла у його батьківський 4-ний вузол. Після цього ми можемо скористатися одним із вищерозглянутих видів вставляння елемента. Оскільки вставляння відбувається на шляху від кореня до листків, то його називають вставлянням „зверху-вниз”.