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

Основна операція дерева. Полягає в переміщенні вершини в корінь за допомогою послідовного виконання трьох, наведених нижче, операцій: 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.

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

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

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

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

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

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

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

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

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

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

1. ZIG

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

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

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

2. ZIG-ZIG

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

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

   ${\displaystyle =2+(r'(X)+r'(P)+r'(G)-r(X)-r(P)-r(G))}$

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

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

   ${\displaystyle {\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 маємо:

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

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

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

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

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

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