Розширюване дерево

Розширюване дерево
Тип	Дерево
Винайдено	1985
Обчислювальна складність у записі великого О
	Середня	Найгірша
Простір	O(n)	O(n)
Пошук	O(log n)	амортиз. O(log n)
Вставляння	O(log n)	амортиз. O(log n)
Видалення	O(log n)	амортиз. O(log n)

Розширюване дерево (англ. splay tree) є двійковим деревом пошуку, у якому підтримується збалансованість. Це дерево належить до класу «саморегульованих дерев», які підтримують необхідний баланс галуження дерева, щоб забезпечити виконання операції пошуку, додавання і видалення за логарифмічний час від числа елементів, що зберігаються. Це реалізується без використання яких-небудь додаткових полів у вузлах дерева (як, наприклад, в Червоно-чорних деревах або АВЛ-деревах, де у вершинах зберігається, відповідно, колір вершини і глибина піддерева). Замість цього «розширювальні операції» (splay operation), частиною яких є повороти дерева, які виконуються при кожному зверненні до дерева. Облікова вартість з розрахунку на одну операцію з деревом складає $O(\log n)$.

Розширюване дерево придумали Роберт Тарьян і Данієль Слейтор в 1985 році.

Операції

Splay (розширення)

Основна операція дерева. Полягає в переміщенні вершини в корінь за допомогою послідовного виконання трьох, наведених нижче, операцій: Zig, Zig-Zig і Zig-Zag. Позначимо вершину, яку хочемо перемістити в корінь за x, її родича — p, а родича p (якщо існує) — g.

Zig: виконується, коли p є коренем. Дерево повертається по ребру між x та p. Існує лише для розбору крайнього випадку і виконується лише один раз в кінці, коли початкова глибина x була непарна.

Zig-Zig: виконується, коли x і p є лівими (або правими) синами. Дерево повертається по ребру між p та x.

Zig-Zag: виконується, коли x є правим сином, а p — лівим (чи навпаки). Дерево повертається по ребру між p та x, а потім — по ребру між x та g.

Search (пошук елемента)

Пошук виконується як в звичайному двійковому дереві пошуку. При знаходженні елементу запускаємо Splay для нього.

Insert (додавання елемента)

Запускаємо Splay від елементу, що додається, і підвішуємо дерева, що вийшли, за нього.

Delete (видалення елемента)

Знаходимо елемент в дереві, робимо Splay для нього, робимо поточним деревом Merge його дітей.

Merge (об'єднання двох дерев)

Для злиття дерев T1 і T2, в яких всі ключі T1 менше ключів в T2, робимо Splay для максимального елементу T1, тоді біля кореня T1 не буде правого дочірнього елемента. Після цього робимо T2 правим дочірнім елементом T1.

Split (розділення дерева на дві частини)

Для розділення дерева знайдемо найменший елемент, більший або рівний x і зробимо для нього Splay. Після цього відрізуємо біля кореня лівого дочірнього елемента і повертаємо 2 дерева, що вийшли.

Примітка

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

Розширюване дерево не володіє жодними явними функціями балансування, але процес скосу вузлів до кореня сприяє підтримці дерева в збалансованому вигляді.

Аналіз

Амортизована вартість будь-якої операції на розширюваному дереві становить $O(\log(n)),$ де $n$ це кількість вузлів у дереві. Будь-яка операція на дереві може зайняти $O(n)$ часу, але, як правило, також робить дерево більш збалансованим, так що з плином часу середня вартість операції є $O(\log(n)).$

Для отримання заявленої оцінки $O(\log(n))$ використаємо метод потенціалів. По-перше визначимо вагу, суму і функцію рангу для кожного вузла:

• Кожен вузол $X$ має вагу $w(X)>0$ (з метою аналізу, може бути будь-якою)
• $s(X)=\Sigma _{Y\in subtree(X)}w(Y)$ (вага вузла дорівнює сумі ваг усіх вузлів його піддерева)
• $r(X)=\log _{2}(s(X))$

Визначимо потенціал усього розширюваного дерева в будь-який момент $i$ як суму рангів у дереві:

$\theta (i)=\sum _{X\in tree}r(X)$

Потенціал вимірює наскільки збалансованим є дерево. Чим менше потенціал тим ліпше збалансоване дерево. Амортизаційна вартість операції складається з дійсної вартості плюс зміна потенціалу дерева.

Амортизована вартість одного кроку розширення

Нехай $r(X)$ буде ранг $X$ перед розширенням і нехай $r'(X)$ буде ранг $X$ після розширення. Тоді амортизаційна вартість розширення

у випадку ZIG $\leq 3(r'(X)-r(X))+1,$

у випадках ZIG-ZIG і ZiG-ZAG $\leq 3(r'(X)-r(X)).$

Доведення: Позначимо амортизовану вартість як ${\hat {c}}$ і дійсну вартість як $c.$

Розглянемо кожен з випадків окремо:

1. ZIG

   ${\hat {c}}=c+\theta (i+1)-\theta (i)=1+(r'(X)+r'(P)-r(X)-r(P))$

   Дійсна вартість дорівнює 1, тому що ми здійснюємо лише одне обертання, щоб перенести $X$ в корінь. Оскільки $r'(X)=r(P)$ і $r'(P)\leq r'(X),$ маємо:

   ${\hat {c}}\leq 1+(r'(X)-r(X))\leq 1+3(r'(X)-r(X))$

2. ZIG-ZIG

   Дійсна вартість є 2, бо ми виконуємо подвійне обертання. Використавши те, що $r'(X)=r(G),r(P)\geq r(X),r'(P)\leq r'(X)$ маємо:

   ${\hat {c}}=c+\theta (i+1)-\theta (i)$

   $=2+(r'(X)+r'(P)+r'(G)-r(X)-r(P)-r(G))$

   $\leq 2+r'(X)+r'(G)-r(X)-r(X)$

   Для подальшого спрощення звернімо увагу на факт, що $\log$ — угнута функція, тобто для будь-яких $a>0,b>0$ повинно виконуватись ${\frac {\log _{2}a+\log _{2}b}{2}}\leq \log _{2}{\frac {a+b}{2}}.$ Зауважимо, що $s(X)+s'(G)\leq s'(X).$ Через угнутість функції $\log ,$ маємо ${\frac {r(X)+r'(G)}{2}}\leq \log _{2}{\frac {s(X)+s'(G)}{2}},$ по транзитивності ${\frac {r(X)+r'(G)}{2}}\leq \log _{2}{\frac {s'(X)}{2}}=r(X)-1.$ Отже,

   ${\hat {c}}\leq 2+r'(X)+(2r'(X)-2-r(X))-r(X)-r(X)\leq 3(r'(X)-r(X))$

3. ZIG-ZAG аналогічно до ZIG-ZIG маємо:

   ${\hat {c}}\leq 3(r'(X)-r(X))$

Амортизаційний аналіз операції розширення

Наступні два наслідки слідують з попереднього аналізу.

Наслідок І

Нехай $V$ буде вершиною розширюваного дерева перед виконанням операції розширення. Тоді амортизована вартість розширення вузла $X$ становить $O(\log n).$

Доведення: Амортизована вартість розширення в $X$ дорівнює сумі вартостей всіх кроків розширення. Під час складання проміжні члени скорочуються і отримуємо, що розширення $X$ є $\leq 3(r'(X)-r(X))+1.$ Доданок 1 відповідає за можливість ZIG-обертання.

Цей аналіз незалежний від ваг у дереві. Припустимо, що ми встановили всі ваги в 1. Тоді найбільша можлива різниця між $r(V)$ і $r(X)$ дорівнює $\log$ від кількості вузлів у дереві. Отже, амортизована вартість розширення $X$ є $O(\log n).$

Наслідок ІІ

Дійсна вартість послідовності з $m$ розширень становить $O((m+n)\log n).$

Див. також

Сбалансовані дерева:

• Червоно-чорне дерево
• АВЛ-дерево

Джерела

• Т. Кормен; Ч. Лейзерсон; Р. Рівест; К. Стайн (2009) [1990]. Вступ до алгоритмів (вид. 3rd). MIT Press і McGraw-Hill. ISBN 0-262-03384-4.
• Daniel Sleator, Robert Tarjan. A data structure for dynamic trees. — Journal of Computer and System Sciences, 1983. — С. 262-391.