МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ Національний унiверситет "Львiвська полiтехнiка"
СТВОРЕННЯ I ВЕДЕННЯ 2-3 ДЕРЕВ 1. МЕТА РОБОТИ Ознайомитися iз способом подання даних в оперативнiй пам'ятi ЕОМ у виглядi 2-3 дерев. Оволодiти методами роботи iз 2-3 деревами. 2. КОРОТКІ ТЕОРЕТИЧНI ВIДОМОСТI Визначення. 2-3-деревом називається дерево, у якому кожний вузол, що не є листом, має двох чи трьох нащадків, а довжини всіх шляхів із кореня в листки однакові. Дерево, що складається з 1 вузла, є 2-3-деревом. Лінійно впорядковану множину S можна зобразити 2-3-деревом, приписавши всі елементи листкам дерева. Елемент, приписаний листку l, позначається Е[l]. У кожному вузлі V, що не є листком, вимагаються два типи даних: L[V] i M[V]. L[V]- найбільший елемент множини S у піддереві, коренем якого служить найлівіший син вузла V; M[V] - найбільший елемент множини S у піддереві, коренем якого є другий син вузла V. Значення L i M, приписані вузлам, дають змогу шукати елемент, починаючи з кореня способом, аналогічним двійковому пошуку. Операцію НАЛЕЖАТИ можна виконати на множині з n елементів за час О (log n). Розглянемо набір операцій: 1) ВСТАВЛЯННЯ; 2) ВИДАЛЕННЯ; 3) НАЛЕЖНІСТЬ. Щоб вставити новий елемент а, необхідно знайти місце для нового листка l, який буде містити а. Для цього шукають елемент а в дереві. Якщо дерево містить більше вiд одного елемента, то пошук а закiнчується у вузлі f, що має двох або трьох синів, які є листками. Якщо з вузла f виходить лише два листки l1 i l2, то l робимо сином вузла f. Якщо а<E[l1], то l робимо сином вузла f і приймаємо L[f]=a i M[f]=E[l1]; якщо E[l1]<a<E[l2], то l робимо середнім сином вузла f і приймаємо M[f]=a; Якщо E[l2]<a, то l робимо третiм сином вузла f. В останньому випадку, можливо, потрiбно буде змiнити значення L i M на деяких дiйсних предках вузла f. дерево перед вставкою елемента 2 Рис.1. Вставка у 2-3 дерево Тепер припустимо, що у 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 дерево, зображене на рис.2.а. вставляється елемент 4, то новий лист із мiткою 4 потрiбно зробити найлiвiшим сином вузла с. Оскiльки у с уже є три сина, будуємо новий вузол с'. Потiм робимо листки 4 i 5 синами вузла с, а листки 6 i 7 - синами вузла с'. Тепер робимо с' сином вузла а. Але оскiльки в а вже є три сина, будуємо новий вузол а'. Робимо вузли b i c синами старого вузла а, а вузли с і d - синами нового вузла а. Нарешті утворюємо новий корінь r і робимо а і а' його синами. Отримане дерево зображене на рис 3. Алгоритм. Вставляння нового елемента у 2-3 дерево. Вхід. Непорожнє 2-3 дерево Т з коренем r і новий елемент а і Т. Вихід. Перетворене 2-3 дерево Т з новим листом, відміченим а. Метод. За умовою Т містить хоча б один елемент. Щоб спростити описання алгоритму, опустимо деталі коректування L i M. 1. Якщо Т складається з єдиного вузла l з міткою b, утворимо новий корінь r. Утворимо новий вузол V із міткою а. Робимо l i V синами кореня r, причому l буде лівим сином, якщо b<a, і правим, якщо b>a 2.Якщо Т містить більше вiд 1 вузла, припустимо f=ПОШУК(а,r), процедура ПОШУК наведена на рис 4. Утворимо новий листок l з міткою а. Якщо у f два сина з мітками b1 i b2, то робимо l відповідним сином вузла f. l буде лівим сином, якщо а<b1, середнім, якщо b1<a<b2, і правим, якщо b2<a. Якщо у f три сина тоді робимо l відповідним сином вузла f, а потім, щоб ввести в Т вузол f і його чотирьох синів, видаляємо ДОБАВСИНА(f). Щоб врахувати присутність вузла а, коректуємо значення L i M уздовж шляху з а в корінь. Інші очевидні зміни, які коректують значення L i M, здійснюються процедурою ДОБАВСИНА. Процедура ПОШУК procedure ПОШУК (a,r); if будь-який син вузла r є листком then return r else begin нехай Si буде і-м сином вузла r; if a<=L[r] then return ПОШУК (a,S1) else if у r два сина або a<=M[r] then return ПОШУК (a,S2) else return ПОШУК (a,S3) end; Процедура ДОБАВСИНА procedure ДОБАВСИНА (v); begin утворити новий вузол v'; зробити двох найправіших синів вузла v лівим і правим синами вузла v'; if у v немає батька then begin утворити новий корінь r; зробити v лівим, а v' правим сином кореня r end else begin нехай f-батько вузла v; зробити v' сином вузла f, розміщеного безпосередньо праворуч від v; if тепер у f чотири сина then ДОБАВСИНА (f) end end; Елемент a можна видалити з 2-3-дерева способом, по суті зворотним до вставки. Випадок 1. Якщо l-корінь, видаляємо його. (У цьому випадку а був єдиним елементом у дереві). Випадок 2. Якщо l-син вузла, що має трьох синів, видаляємо його. Випадок 3. Якщо l-син вузла, що має двох синів, то може бути одне з двох: а) f-корінь; видаляємо l і f та робимо коренем другого сина S; б) f-не корінь. Допустимо, що f має брата ліворуч від себе. Випадо к, коли брат знаходиться праворуч, розглядається аналогічно. Якщо у g лише два сина, робимо вузол S найправішим сином вузла g, видаляємо l і рекурсивно викликаємо процедуру видалення, щоб видалити f. Якщо у g три сина, то найправішого сина робимо лівим сином вузла f і видаляємо l. ІНДИВІДУАЛЬНЕ ЗАВДАННЯ Створити два дерева і перевірити чи вони рівні. Текст програми #include <stdio.h> #include "tree.h" #define TRUE 1 int cmp_tree(tree t1, tree t2) { int b; list l1, l2; b = empty(t1) && empty(t2) || !empty(t1) && !empty(t2); if (!empty(t1) && !empty(t2)) { b = root(t1)==root(t2); sons_list(t1, &l1); sons_list(t1, &l2); sl_first(&l1); sl_first(&l2); while(!sl_emp_end(l1) && !sl_emp_end(l2) && b) { b = cmp_tree(sl_current(l1),sl_current(l2)); sl_next(&l1); sl_next(&l2); } b = b && sl_emp_end(l1) && sl_emp_end(l2); } return b ; } void input_tree(tree *pt) { unsigned m, n, i; list l; tree s; int k; init(pt); printf("Vvodutu derevo? [0-ni/1-tak]: "); scanf("%u", &m); if (m==1) { printf("Vvedit korin: "); scanf("%d", &k); printf("Vvedit k-st suniv: "); scanf("%u", &n); sl_init(&l); for(i=1; i<=n; i++) { printf("Sun %u\n", i); input_tree(&s); sl_insert(&l, s); } make_node(pt,k,l); } } main() { tree t1, t2; printf("\nVvedit pershe derevo\n"); input_tree(&t1); printf("\nVvedit dryge derevo\n"); input_tree(&t2); printf("Dereva "); if (!cmp_tree(t1,t2)) printf("ne "); printf("rivni\n"); } Висновок Виконав[ім’я автора приховано]