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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Розширюване дерево
Тип Дерево
Винайдено 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 була непарна.

Splay tree zig.svg

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

Zigzig.gif

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

Zigzag.gif

Search (пошук елемента)[ред.ред. код]

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

Insert (додавання елемента)[ред.ред. код]

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

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)).[1]

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

Амортизаційний аналіз операції розширення[ред.ред. код]

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

Наслідок І[ред.ред. код]

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

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

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

Наслідок ІІ[ред.ред. код]

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

Див. також[ред.ред. код]

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

Примітки[ред.ред. код]

Джерела[ред.ред. код]

  • Daniel Sleator, Robert Tarjan A data structure for dynamic trees. — Journal of Computer and System Sciences, 1983. — С. 262-391.