Перегляд вихідного коду сторінки Розширюване дерево

{{Infobox data structure
|name=Розширюване дерево
|type=tree
|invented_by=
|invented_year=1985
|space_avg=O(n)
|space_worst=O(n)
|search_avg=O(log n)
|search_worst=амортиз. O(log n)
|insert_avg=O(log n)
|insert_worst=амортиз. O(log n)
|delete_avg=O(log n)
|delete_worst=амортиз. O(log n)
}}
'''Розширюване дерево''' ({{lang-en|splay tree}}) є [[Двійкове дерево пошуку|двійковим деревом пошуку]], у якому підтримується [[Збалансоване дерево|збалансованість]]. Це дерево належить до класу «саморегульованих дерев», які підтримують необхідний баланс галуження дерева, щоб забезпечити виконання операції пошуку, додавання і видалення за логарифмічний час від числа елементів, що зберігаються. Це реалізується без використання яких-небудь додаткових полів у вузлах дерева (як, наприклад, в [[Червоно-чорне дерево|Червоно-чорних деревах]] або [[АВЛ-дерево|АВЛ-деревах]], де у вершинах зберігається, відповідно, колір вершини і глибина піддерева). Замість цього «розширювальні операції» (splay operation), частиною яких є [[Поворот дерева|повороти дерева]], які виконуються при кожному зверненні до дерева. Облікова вартість з розрахунку на одну операцію з деревом складає <math>O(\log n)</math>.

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

== Операції ==

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

'''Zig:''' виконується, коли ''p'' є коренем. Дерево повертається по ребру між ''x'' та ''p''. Існує лише для розбору крайнього випадку і виконується лише один раз в кінці, коли початкова глибина ''x'' була непарна.
[[Файл:splay_tree_zig.svg|center]]
'''Zig-Zig:''' виконується, коли ''x'' і ''p'' є лівими (або правими) синами. Дерево повертається по ребру між ''p'' та ''x''.
[[Файл:Zigzig.gif|center]]
'''Zig-Zag:''' виконується, коли ''x'' є правим сином, а ''p''&nbsp;— лівим (чи навпаки). Дерево повертається по ребру між ''p'' та ''x'', а потім&nbsp;— по ребру між ''x'' та ''g''.
[[Файл:Zigzag.gif|center]]

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

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

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

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

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

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

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

== Аналіз ==
Амортизована вартість будь-якої операції на розширюваному дереві становить <math>O(\log(n)),</math> де <Math>n</math> це кількість вузлів у дереві. Будь-яка операція на дереві може зайняти <math>O(n)</math> часу, але, як правило, також робить дерево більш збалансованим, так що з плином часу середня вартість операції є <math>O(\log(n)).</math><ref>[http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/dzhang_splaytree.pdf Розширюване дерево] {{Webarchive|url=https://web.archive.org/web/20150319214600/http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-854j-advanced-algorithms-fall-2005/lecture-notes/dzhang_splaytree.pdf |date=19 березня 2015 }} на [[MIT OpenCourseWare]]</ref>

Для отримання заявленої оцінки <math>O(\log(n))</math> використаємо [[Метод потенціалів (амортизаційний аналіз)|метод потенціалів]]. По-перше визначимо вагу, суму і функцію рангу для кожного вузла:
* Кожен вузол <math>X</math> має вагу <math>w(X) > 0</math> (з метою аналізу, може бути будь-якою)
* <math>s(X) = \Sigma_{Y\in subtree(X)}w(Y)</math> (вага вузла дорівнює сумі ваг усіх вузлів його піддерева)
* <math>r(X) = \log_2(s(X))</math>
Визначимо потенціал усього розширюваного дерева в будь-який момент <math>i</math> як суму рангів у дереві:
:<math>\theta(i)=\sum_{X\in tree}r(X)</math>

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

=== Амортизована вартість одного кроку розширення ===
Нехай <math>r(X)</math> буде ранг <math>X</math> перед розширенням і нехай <math>r'(X)</math> буде ранг <math>X</math> після розширення. Тоді амортизаційна вартість розширення 
:у випадку ZIG <math>\le 3(r'(X)-r(X))+1,</math>
:у випадках ZIG-ZIG і ZiG-ZAG <math>\le 3(r'(X)-r(X)).</math>
'''Доведення:'''
Позначимо амортизовану вартість як <math>\hat{c}</math> і дійсну вартість як <math>c.</math>

Розглянемо кожен з випадків окремо:
#'''ZIG'''
#:<math>\hat{c} = c + \theta(i+1) - \theta(i) = 1 + (r'(X)+r'(P)-r(X)-r(P))</math>
#:Дійсна вартість дорівнює 1, тому що ми здійснюємо лише одне обертання, щоб перенести <math>X</math> в корінь. Оскільки <math>r'(X) = r(P)</math> і <math>r'(P) \le r'(X),</math> маємо:
#:<math>\hat{c} \le 1 + (r'(X) - r(X)) \le 1 + 3(r'(X) - r(X))</math>
#'''ZIG-ZIG'''
#:Дійсна вартість є 2, бо ми виконуємо подвійне обертання. Використавши те, що <math>r'(X) = r(G), r(P)\ge r(X), r'(P) \le r'(X)</math> маємо:
#:<math>\hat{c} = c + \theta(i+1) - \theta(i)</math>
#:<math>= 2 + (r'(X)+r'(P)+r'(G)-r(X)-r(P)-r(G))</math>
#:<math>\le 2+r'(X)+r'(G)-r(X)-r(X)</math>
#:Для подальшого спрощення звернімо увагу на факт, що <math>\log</math>&nbsp;— [[угнута функція]], тобто для будь-яких <math>a > 0, b > 0</math> повинно виконуватись <math>\frac{\log_2 a+\log_2 b}{2} \le \log_2{\frac{a+b}{2}}.</math> Зауважимо, що <math>s(X) + s'(G) \le s'(X).</math> Через угнутість функції <math>\log,</math> маємо <math>\frac{r(X)+r'(G)}{2}\le \log_2\frac{s(X)+s'(G)}{2},</math> по транзитивності <math>\frac{r(X)+r'(G)}{2}\le \log_2\frac{s'(X)}{2} = r(X) - 1.</math> Отже,
#:<math>\hat{c}\le 2 + r'(X) + (2r'(X) - 2 - r(X)) - r(X) - r(X)\le 3(r'(X) - r(X))</math>
#'''ZIG-ZAG''' аналогічно до '''ZIG-ZIG''' маємо:
#:<math>\hat c\le 3(r'(X) - r(X))</math>

=== Амортизаційний аналіз операції розширення ===
Наступні два наслідки слідують з попереднього аналізу.

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

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

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

====Наслідок ІІ====
Дійсна вартість послідовності з <math>m</math> розширень становить <math>O((m+n)\log n).</math>

== Див. також ==
Сбалансовані дерева:
:* [[Червоно-чорне дерево]]
:* [[АВЛ-дерево]]

== Примітки ==
{{reflist}}

== Джерела ==
* {{CLRS}}
* {{книга
 |автор          = Daniel Sleator, Robert Tarjan
 |заголовок      = A data structure for dynamic trees
 |посилання      = 
 |відповідальний = 
 |місце          = 
 |видавництво    = Journal of Computer and System Sciences
 |рік            = 1983
 |том            = 
 |сторінок       = 
 |сторінки       = 262-391
 |isbn           = 
}}

{{Дерева (інформатика)}}

[[Категорія:Дерева (структури даних)]]