Структури даних, Детальна інформація

InsertTree ( b, e, T )

if (b \xF0A3\xF020begin[T] and end[T] \xF0A3\xF020e) then flag[T] = TRUE;

else

begin

if (b <\xF020\xF028begin[T] + end[T] ) / 2 ) then InsertTree ( b, e, left[T] )

if (\xF020\xF028begin[T] + end[T] ) / 2 < e) then InsertTree ( b, e, right[T] )

end;

Наприклад, після занесення інтервала [5, 14] до дерева відрізків T(4,15) параметр flag у наступних стандартних інтервалах буде встановлено в істину:

[5, 6], [6, 9], [9, 12], [12, 13], [13, 14].

2-3 деревом називається дерево, в якому кожний вузол, який не є листом, має двох або трьох синів, а довжини всіх шляхів з кореня до листів однакові.

Позначимо через E[l] елемент даних, приписаний вершині l. Кожна вершина v, яка не є листом, містить два додаткові елементи: L[v] та M[v] найбільший елемент множини даних S у піддереві, коренем якого є відповідно лівий та середній син вершини v.

Вставка в 2 - 3 дерево. Для вставки нового елемента а необхідно знайти місце для нового листа l. Для цього шукають елемент а в дереві. Пошук закінчується у вузлі f, який має двох чи трьох синів що є листами.

Якщо з вузла f виходить лише два вузла l1 та l2, то l стає сином f. Якщо a < E[l1], то l стає самим лівим сином вузла f і покладаємо L[f] = a, M[f] = E[l1]. Якщо E[l1] < a < E[l2], то l стає середнім сином вузла f і покладаємо M[f] = a. Якщо E[l2] < a, то l стає третім сином вузла f. В останньому випадку може виникнути необхідність змінити значення L та M на деяких предках вузла f.

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

Формула Ейлера. Позначимо через V, E, F кількість вершин, ребер та граней планарного графу G (включаючи необмежену область). Тоді справедлива формула:

V - E + F = 2

Малюнок Х. Граф. V = 4, E = 6, F = 4: V - E + F = 4 - 6 + 4 = 2

Якщо граф G незв’язний, а С – кількість компонент зв’язності, то має місце формула:

V - E + F - C = 1

Теорема. Планарний граф з V вершинами має не більше 3(V - 2) ребер та не більше 2(V - 2) граней.

Доведення. Припустимо, що граф не має подвійних ребер та циклів. Побудуємо триангуояцію графу.

Реберний список з подвійними зв’язками (РСПЗ) використовується для представлення планарного графа. Плоске укладання планарного графа – це відображення кожної вершини у точку на площині, а кожного ребра – в просту лінію, яка сполучає пару образів кінцевих вершин цього ребра так, щоб образи ребер перетиналися лише у своїх кінцевих точках.

Головною компонентою РСПЗ для планарного графа (V, E) є реберний вузел. Між ребрами та реберними вузлами існує взаємно однозначна відповідність. Реберний вузел містить чотири інформаційні поля (V1, V2, F1, F2) та два поля вказівників (P1, P2). Поле V1 містить початок ребра, а поле V2 містить його кінець (ребро таким чином має орієнтацію). Поля F1 та F2 містять імена граней. Вказівник P1 (відповідно P2) задає реберний вузел, який містить перше ребро, що зустрічається за ребром (V1, V2) при повороті від нього проти годинникової стрілки навколо V1 (відповідно V2). Імена граней та вершин задаються цілими числами.

a8 5 4 1 2 4 9

a9 4 7 4 2 3 7

a10 3 7 5 4 2 9



Якщо граф має N вершин та F граней, то введемо два масива HV[1:N] та HF[1:F], які містять номер ребра, що виходить з відповідної вершини (обмежує грань). Процедура Fill заповнює ці масиви переглядаючи V1 та F1 за час O(N).

Fill

for i \xF0AC\xF0201 to N do