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

Вершина х не має дітей тоді і тільки тоді коли left-child[x] = NIL. Вершина х є крайньою правою дитиною свого батька якщо right-child[x] = NIL.

AVL - деревом (Adelson-Velskii and Landis) називається бінарне дерево, яке має наступні властивості:

висоти піддерев кожного батька відрізняються не більше ніж на 1:

кожне піддерево батька є AVL - деревом.

AVL - дерева належать до класу збалансованих бінарних дерев.

Ліве дерево є AVL - деревом, оскільки у нього висота кожного лівого сина на 1 більша за висоту відповідного правого сина. Дерево, яке зображене справа, не є AVL - деревом, оскільки лівий син вершини 12 (дерево з коренем 8) має висоту 4, а правий син вершини 12 (дерево з коренем 18) має висоту 2.

Дерево відрізків – це структура даних, яка створена для роботи з такими інтервалами на числовій осі, кінці яких належать фіксованій множині з N абсцис (далі цими абсцисами будемо вважати цілі числа в інтервалі [1, N]). Оскільки множина абсцис фіксована, то дерево відрізків являє собою статичну структуру по відношенню до цих абсцис.

Дерево відрізків – це двійкове дерево з коренем. Для заданих цілих чисел l та r (l < r) дерево відрізків T(l, r) будується рекурсивно наступним чином: воно складається з кореня v з параметрами B[v] = l, E[v] = r (B – Begin, E - End). Якщо r - l > 1, то воно складається з лівого піддерева T(l, [(B[v] + E[v])/2]) та правого піддерева T([(B[v] + E[v])/2], r).

J

Z

h

\x00A8

\x031E\x5A6A

K називаються стандартними інтервалами дерева T(l, r). Стандартні інтервали, які належать листам T(l, r), називаються елементарними інтервалами. T(l, r) збалансоване та має глибину \xF0E9log2(r - l)\xF0F9.

Дерево відрізків призначено для динамічного запам’ятання інтервалів, кінці яких належать множині {l, l + 1, ..., r}. Якщо r - l > 3, то інтервал [b, e] з цілими b < e буде розбито в набір не більш ніж \xF0E9log2 (r - l)\xF0F9 + \xF0EBlog2 (r - l)\xF0FB - 2 стандартних інтервалів дерева T(l, r).

Функція BuildTree ( l, r ) будує та повертає дерево відрізків T(l, r). Складний тип даних tree має структуру дерева, в якій left та right – вказівники на лівого та правого сина, begin та end – параметри вершини.

BuildTree ( l, r )

temp \xF0AC new tree;

begin [temp] \xF0AC l;

end [temp] \xF0AC r;

if (r - l < 2) then

begin

left[temp] \xF0AC NIL;

right[temp] \xF0AC NIL;

return temp;

end;

left[temp] \xF0AC BuildTree ( l, [(l + r) / 2] );

right[temp] \xF0AC BuildTree ( [(l + r) / 2], r );

return temp;

Фрагментація інтервала [b, e] повністю визначається операцією занесення [b, e] в дерево відрізків Т. До структури даних tree додамо булевий параметр flag, який буде відповідати за включення стандартного інтервалу до інтервалу [b, e]. Тобто якщо для деякої вершини v має місце flag[v] = TRUE, то [ begin[v], end[v] ] \xF0CD [b, e].