Scapegoat-дерева

Сьогодні ми подивимося на структуру даних, звану Scapegoat-деревом. «Scapegoat», хто не в курсі, перекладається як «козел відпущення», що робить дослівний переклад назви структури якимось дивним, тому будемо використовувати оригінальну назву. Дерев пошуку, як ви, можливо, знаєте є дуже багато різних видів, і в основі всіх їх лежить одна і та ж ідея: "А добре б при пошуку елемента перебирати не весь набір даних підряд, а тільки якусь частину, бажано розміру порядку log(N)".

Для цього кожна вершина зберігає посилання на своїх дітей і якийсь критерій, за яким при пошуку точно зрозуміло, в яку з дочірніх вершин треба перейти. За логарифмічний час це все буде працювати тоді, коли дерево є збалансованим (ну або прагне до цього) — тобто коли «висота» кожного з піддерев кожної вершини приблизно однакова. А ось способи балансування дерева вже у кожного типу дерев свої: в червоно-чорних деревах у вершинах зберігаються маркери «кольору», підказують коли і як потрібно перебалансувати дерево, АВЛ-дерева в вершинах зберігається різниця висот дітей, Splay-дерева заради балансування змушені змінювати дерево під час операцій пошуку і т. д.

Scapegoat-дерево теж має свій підхід до вирішення проблеми балансування дерева. Як і для всіх інших випадків він не ідеальний, але цілком застосовний в деяких ситуаціях.

До достоїнств Scapegoat-дерева можна віднести:
  • Відсутність необхідності зберігати будь-які дані в вершинах (а значить ми виграємо по пам'яті у червоно-чорних, АВЛ і декартових дерев)
  • Відсутність необхідності перебалансувати дерево при операції пошуку (а значить ми можемо гарантувати максимальний час пошуку O(log N), на відміну від Splay-дерев, де гарантується тільки амортизированное O(log N))
  • Амортизована складність операцій вставки і видалення O(log N) — це в загальному-то аналогічно іншим типам дерев
  • При побудові дерева ми обираємо деякий коефіцієнт «строгості» α, який дозволяє «тюнінгувати» дерево, роблячи операції пошуку швидшими за рахунок уповільнення операцій модифікації або навпаки. Можна реалізувати структуру даних, а далі вже підбирати коефіцієнт за результатами тестів на реальних даних та специфіки використання дерева.
До недоліків можна віднести:
  • У гіршому випадку операції модифікації дерева можуть зайняти O(n) часу (амортизированна складність у них як і раніше O(log N), але захисту від «поганих» випадків немає).
  • Можна неправильно оцінити частоту різних операцій з деревом і помилитися з вибором коефіцієнта α — в результаті часто використовувані операції будуть працювати довго, а рідко використовуються — швидко, що як-то не добре.


Давайте будемо розбиратися, що ж таке Scapegoat-дерево і для нього виконувати операції пошуку, вставки та видалення.

Використовувані поняття (квадратні дужки в позначеннях вище означають, що ми зберігаємо це значення явно, а значить можемо взяти за час О(1). Круглі дужки означають, що значення буде обчислюватися по ходу справи тобто пам'ять не витрачається, але зате потрібно час на обчислення)
  • T — так будемо позначати дерево
  • root[T] — корінь дерева T
  • left[x] — лівий «син» вершини х
  • right[x] — лівий «син» вершини х
  • brother(x) — брат вершини х (вершина, яка не має загального батька)
  • depth(x) — глибина вершини х. Це відстань від неї до кореня (кількість ребер)
  • height(T) — глибина дерева T. Це глибина самої глибокої вершини дерева T
  • size(x) — вага вершини х. Це кількість всіх її дочірніх вершин + 1 (вона сама)
  • size[х] — розмір дерева T. Це кількість вершин в ньому (вага кореня)




Тепер введемо поняття, необхідні нам для Scapegoat-дерева:
  • max_size[T] — максимальний розмір дерева. Це максимальне значення, яке параметр size[T] брав з моменту останньої перебалансування. Якщо перебалансування відбулася тільки що, то max_size[T] = size[T]
  • Коефіцієнти α — це число в діапазоні від [0.5; 1), що визначає необхідну ступінь якості балансування дерева. Деяка вершина x називається "α-збалансованої за вагою", якщо вага її лівого сина менше або дорівнює α * size(x) і вагу їй правого сина менше або дорівнює α * size(x).

    size(left[x]) ≤ α * size(x)
    size(right[x]) ≤ α * size(x)


Давайте спробуємо зрозуміти цей критерій. Якщо α = 0.5 ми вимагаємо, щоб у лівому поддереве було рівно стільки ж вершин, скільки в правом (± 1). Тобто фактично це вимога ідеально збалансованого дерева. При α > 0.5 ми говоримо «гаразд, нехай балансування буде не ідеальною, хай одному з піддерев буде дозволено мати більше вершин, ніж іншому». При α = 0.6 одне з піддерев вершини х може містити до 60% всіх вершин піддерева х щоб вершина х все ще вважалася "α-збалансованої за вагою". Легко побачити, що при α прагне до 1 ми фактично погоджуємося вважати "α-збалансованим за вагою" навіть звичайний зв'язний список.

Тепер давайте подивимося як в Scapegoat-дереві виконуються звичайні операції.
На початку роботи з деревом ми вибираємо параметр α в діапазоні [0.5; 1). Також заводимо дві змінні для зберігання поточних значень size[T] і max_size[T] і обнуляем їх.

Пошук
Отже, у нас є деякий Scapegoat-дерево і ми хочемо знайти в ньому елемент. Оскільки це бінарне дерево пошуку, то пошук буде стандартним: йдемо від кореня, порівнюємо вершину з шуканим значенням, якщо знайшли — повертаємо, якщо значення у вершині менше — рекурсивно шукаємо в лівому поддереве, якщо більше — у правому. Дерево по ходу пошуку не модифікується.

Складність операції пошуку, як ви могли здогадатися, залежить від α і виражається формулою

Тобто складність, звичайно, логарифмічна, ось тільки підстава логарифма цікаве. При α близькому до 0.5 ми отримуємо двійковий (або майже двійковий) логарифм, що означає ідеальну (або майже ідеальну) швидкість пошуку. При α близькому до одиниці підстава логарифма прагне до одиниці, а отже загальна складність прагне до O(N). Ага, а ніхто й не обіцяв ідеалу.

Вставити
Починається вставка нового елемента в Scapegoat-дерево класично: пошуком шукаємо місце, куди б підвісити нову вершину, ну і підвішуємо. Легко зрозуміти, що це дія могла порушити α-балансування по вазі для однієї або більше вершин дерева. І ось тепер починається те, що і дало назву структурі даних: ми шукаємо «козла відпущення» (Scapegoat-вершину) — вершину, для якої втрачено α-баланс та її піддерево має бути перебудована. Сама тільки що вставлена вершина, хоча і винна у втраті балансу, «козлом відпущення» стати не може — у неї ще немає «дітей», а значить її баланс ідеальний. Відповідно, потрібно пройти по дереву від цієї вершини до кореня, перераховуючи ваги для кожної вершини по дорозі. Якщо на цьому шляху зустрінеться вершина, для якої критерій α-збалансованості за вагою порушився — ми повністю перебудовуємо відповідне їй піддерево так, щоб відновити α-збалансованість по вазі.

По ходу справи виникає ряд питань:
А як пройти від вершини «вгору» корені? Нам потрібно зберігати посилання на батьків?
— Ні. Оскільки ми прийшли до місця вставки нової вершини з кореня дерева — у нас є стек, в якому знаходиться весь шлях від кореня до нової вершини. Беремо батьків з нього.

А як порахувати «вага» вершини — ми ж його не зберігаємо в самій вершині?
— Ні, не зберігаємо. Для нової вершини вага = 1. Для її батька вага = 1 (вага нової вершини) + 1 (вага самого батька) + size(brother(x)).

Ну ок, а як порахувати size(brother(x)) ?
— Рекурсивно. Так, це займе час O(size(brother(x))). Розуміючи, що в гіршому випадку нам, можливо, доведеться порахувати вага половини дерева — ми бачимо ту саму складність O(N) у гіршому випадку, про яку йшлося на початку. Але оскільки ми обходимо піддерево α-збалансованого за вагою дерева можна показати, що амортизована складність операції не перевищить O(log N).

А адже вершин, для яких порушився α-баланс може бути і дещо — що робити?
— Коротка відповідь: можна вибирати будь-яку. Довгий відповідь: в оригінальному документі з описом структури даних є пара евристик, як можна вибрати «конкретного козла відпущення» (ось це термінологія пішла!), але взагалі-то вони зводяться до «ось ми спробували так і так, експерименти показали, що зразок ось так краще, але чому — пояснити не можемо».

як робити перебалансировку знайденої Scapegoat-вершини?
— Є два шляхи: тривіальний і трохи більш хитрий.

Тривіальна перебалансування
  1. Обходимо всі піддерево Scapegoat-вершини (включаючи її саму) за допомогою in-order обходу — на виході отримуємо відсортований список властивість In-order обхід бінарного дерева пошуку).
  2. Знаходимо медіану на цьому відрізку, підвішуємо її в якості кореня піддерева.
  3. Для «лівого» і «правого» піддерева рекурсивно повторюємо ту ж операцію.


Видно, що все це справа вимагає O(size(Scapegoat-вершина)) часу і стільки ж пам'яті.

Трохи більш хитра перебалансування
Навряд чи ми покращимо час роботи перебалансування — все-таки кожну вершину потрібно «підвісити» в нове місце. Але ми можемо спробувати заощадити пам'ять. Давайте подивимося на «тривіальний» алгоритм уважніше. Ось ми вибираємо медіану, підвішуємо в корінь, дерево ділиться на два піддерева — і ділиться досить однозначно. Ніяк не можна вибрати якусь іншу медіану» або підвісити «праве» піддерево замість лівого. Та ж сама однозначність переслідує нас і на кожному з наступних кроків. Тобто для деякого списку вершин, відсортованих у порядку зростання, у нас буде рівно одне породжене цим алгоритмом дерево. А звідки ж ми взяли відсортований список вершин? З in-order обходу початкового дерева. Тобто кожній вершині, знайденої по ходу in-order обходу перебалансируемого дерева відповідає одна конкретна позиція в новому дереві. І ми можемо цю позицію розрахувати в принципі і без створення самого відсортованого списку. А розрахувавши — відразу її туди записати. Виникає тільки одна проблема — адже ми цим затираємо якусь (можливо ще не попередньо переглянуту) вершину — що ж робити? Зберігати її. Де? Ну, виділяти для списку таких вершин пам'ять. Але цієї пам'яті потрібно буде вже не O(size(N)), а всього лише O(log N).

В якості вправи уявіть собі в умі дерево, що складається з трьох вершин — кореня і двох підвішених як «ліві» сини вершин. In-order обхід поверне нам ці вершини в порядку від самої «глибокої» до кореня, але зберігати в окремій пам'яті по ходу цього обходу нам доведеться всього одну вершину (найглибшу), оскільки коли ми прийдемо в другу вершину, ми вже будемо знати, що це медіана і вона буде коренем, а інші дві вершини — її дітьми. Тобто витрата пам'яті тут — на зберігання однієї вершини, що узгоджується з верхньою оцінкою для дерева з трьох вершин — log(3).

Видалення вершини
Видаляємо вершину звичайним видаленням вершини бінарного дерева пошуку (пошук, видалення, можливе переподвешивание дітей).
Далі перевіряємо виконання умови
size[T] < α * max_size[T]
якщо воно виконується — дерево могло втратити α-балансування за вагою, а значить потрібно виконати повну перебалансировку дерева (починаючи з кореня) і присвоїти max_size[T] = size[T]

Наскільки це все продуктивно?
Відсутність оверхеда по пам'яті і перебалансування при пошуку — це добре, це працює на нас. З іншого боку перебалансування при модифікаціях не так щоб дуже дешеві. Ну і вибір α істотно впливає на продуктивність тих чи інших операцій. Самі винахідники порівнювали продуктивність Scapegoat-дерева з червоно-чорними та Splay-деревами. У них вийшло підібрати α так, що на випадкових даних Scapegoat-дерево перевершив по швидкості всі інші типи дерев, на будь-яких операціях (що взагалі-то досить непогано). На жаль, на монотонно-зростаючому наборі даних Scapegoat-дерево працює гірше в частині операцій вставки і виграти у Scapegoat не вийшло ні при якому α.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.