Дерево статистичних порядків

Яку проблему це вирішує

Відсортований масив відповідає на запитання «який елемент є k-тим найменшим» за допомогою прямого індексування з константною швидкістю та на запитання «яка ранг елемента x?» за логарифмічної швидкості через бінарний пошук. Однак вставка або видалення значення в відсортованому масиві потребує лінійного часу, оскільки все після ураженої позиції має зміститися. Збалансоване дерево з пошуком (plain balanced binary search tree) перевертає цей вибір: вставка та видалення здійснюються логарифмічно, але знаходження k-того найменшого елемента потребує обходу в порядку, який коштує лінійно часу, оскільки дерево не зберігає інформації про кількість елементів, що знаходяться в кожному піддереві. Жодна з цих структур сама по собі не забезпечує швидких версій усіх чотирьох операцій одночасно: пошук, вставка, видалення та вибір на основі рангу. Дерево статистичних порядків (order-statistics tree) закриває цей проміжок, доповнюючи збалансоване дерево, найчастіше червоно-чорне дерево, одним цілим числом, що представляє розмір піддерева. Оскільки червоно-чорне дерево вже гарантує висоту дерева O(log n) завдяки своїй кольоровій та балансованій інваріантності, і розмір піддерева можна підтримувати під час тих самих ротацій, що зберігають ці інваріантність, доповнення є практично безкоштовним. Воно додає постійний простір на вузол та додаткову роботу на кожній ротації, одночасно відкриваючи можливість запитів щодо вибору та рангу, які в іншому випадку змушують виконувати повний обхід. Цей шаблон узагальнюється: той самий принцип доповнення застосовується до дерев інтервалів (interval trees), які зберігають максимальні кінцеві точки піддерева, або до дерев, що зберігають суми піддерев для запитів агрегування діапазонів. У кожному випадку базове збалансоване дерево забезпечує логарифмічну висоту, а ретельно підібране поле доповнення, яке оновлюється за постійний час на кожній ротації, надає додаткову швидкість запитів без шкоди для продуктивності вставки та видалення оригінального дерева. Дерево статистичних порядків є найпростішим прикладом цього техніки доповнення, і його вивчення добре полегшує розуміння більш складних збалансованих структур пізніше.

Уздовж гілки: Зберігання розміру піддерева

Кожен вузол x у дереві статистичних порядків містить поле size[x], яке визначає кількість вузлів у піддереві, що корениться в x, включно з самим x. Формально, size[x] = size[ліве[x]] + size[праве[x]] + 1, де порожнє дитиння внесено нульовим значенням. Це рекурсивне визначення робить підтримку більш керованою: коли-небудь, коли змінюються діти вузла, його розмір можна обчислити лише з його безпосередніх дітей, не заглиблюючись далі в дерево. Під час стандартного вставлення у бінарне дерево нового вузол додається як листова наприкінці шляху від кореня до листка; кожен предок на цьому шляху збільшується на 1, оскільки вставка йде назад, або ж збільшується при обході вниз перед тим, як лист буде приєднано. Видалення є симметричним: видалення вузла зменшує поле size[x] для кожного предка на шляху до видаленого вузла на 1. Найскладнішим є поворот – операція, яку використовують червоно-чорні дерева, щоб відновити баланс після вставлення або видалення. Поворот (лівий або правий) змінює, який вузол є батьківським, а який дитячим серед двох вузлів, що означає зміну того, хто має піддерево. Наприклад, у лівому повороті навколо вузла x з правою дитиною y, вузол y займає місце x, x стає лівою дитиною y, а колишнє ліве піддерево y стає новим правим піддеревом x. Після цієї операції зміни покажчиків потрібно перерахувати лише для двох полів розміру, і їх потрібно перерахувати в правильному порядку: спочатку size[x], використовуючи оновлених дітей x, а потім size[y], використовуючи нову ліву дитину y (x) та його незмінне праве піддерево. Оскільки лише постійна кількість вузлів змінюється за допомогою одного повороту, оновлення полів розміру додає лише константної накладки до кожного повороту, тому вставка або видалення залишаються O(log n).

OS-ВИБІР: Знаходження k-го найменшого елемента

OS-ВИБІР(x, k) знаходить вузол, що містить k-тий за розміром ключ у піддереві, яке корениться в x, використовуючи поля збережених розмірів для прийняття обґрунтованого рішення на кожному кроці замість бездумного дослідження. Процедура починається з обчислення r = size[left[x]] + 1, що є рангом вузла x у власному піддереві: все в лівому піддереві x менше за x, тому сам x є (r)-им найменшим елементом в цьому піддереві. Існує три випадки. Якщо k дорівнює r, вузол x є точним відповіддю, і пошук завершується негайно. Якщо k менше r, бажаний k-тий найменший елемент повинен знаходитися десь у лівому піддереві, оскільки саме це піддерево вже містить щонайменше k елементів, що є меншими або рівними необхідному; алгоритм рекурсує в left[x] з тим самим значенням k. Якщо k більше r, бажаний елемент знаходиться в правому піддереві, але його ранг там менший за k, оскільки r елементів, а саме x і все ліве піддерево, вже відомо, що передують йому; алгоритм рекурсує в right[x] з відкоригованим значенням k мінус r. Це не повний обхід дерева; це одноразовий спуск від кореня до вузла відповіді, роблячи рівно одне порівняння на кожному рівні. Оскільки висота дерева становить O(log n) завдяки балансуючому інварианту, OS-ВИБІР працює за час O(log n). Це контрастується з підходом in-order обходу, який міг би відвідати та порахувати до k вузлів, потенційно торкаючись значної частини дерева; OS-ВИБІР замість цього обрізає ціле піддерево на кожному кроці, який йому не потрібно досліджувати, точно так само, як бінарний пошук обрізає половину простору пошуку при кожному порівнянні.

OS-RANK: Визначення положення елемента

OS-RANK(T, x) відповідає на питання відображення: якщо у вас вже є вказівник на вузол x, який знайдено в дереві, яке саме його положення (тобто ранг), враховуючи, що все дерево перелічено в відсортованому порядку? Алгоритм використовує ті ж самі розмірні поля, але йде вгору від x до кореня замість того, щоб спускатися вниз від кореня. Спочатку запускається лічильник r = size[left[x]] + 1, ранг x у своєму власному піддереві, точно так само, як і в OS-SELECT. Потім алгоритм піднімається по дереву рівень за рівнем. На кожному кроці, якщо поточний вузол y є правопохідним від свого батька, це означає, що батько та весь лівий піддерево батька, а також сам батько мають ключі менші за все, що було пораховано до цього моменту, тому алгоритм додає size[left[parent]] + 1 до r перед тим, як підніматися до батька. Якщо y є лівим похідним від свого батька, нічого не потрібно додавати, оскільки батько та інше праве піддерево мають ключі більші за все, що було пораховано, і лічильник r не змінюється; алгоритм просто піднімається до батька. Це триває до тих пір, поки не досягнуто кореня, в цей момент r містить правильний загальний ранг x у всьому дереві. Оскільки цей шлях слідує за єдиним шляхом від кореня до вузла, а довжина цього шляху становить O(log n) у збалансованому дереві, OS-RANK також виконується за час O(log n). Зверніть увагу на елегантну симетрію між OS-SELECT та OS-RANK: один сходить, використовуючи розмірні поля для пошуку вузла, заданого цільовим рангом, інший піднімається, використовуючи розмірні поля для обчислення рангу, заданого знайденим вузлом, і обидва покладаються на абсолютно ті ж доповнення та абсолютно той самий асимптотичний ліміт.

Практичне застосування: поточні медіани та процентили

Природним застосуванням дерева статистичних порядків є підтримка статистики, такої як медіана або будь-який заданий відсоток, над набором даних, який постійно змінюється, з додаванням і видаленням значень безперервно, наприклад, потік даних з датчиків, суми транзакцій або вимірювання затримки. Перерахунок медіани знову ж таки, означає сортування всього набору даних щоразу, коли приходить значення, або залишається, що призводить до безмежного зростання вартості, оскільки кожен з n оновлень коштує O(n log n) для нового сортування. За допомогою дерева статистичних порядків кожне нове значення вставляється за O(log n) часу, і дерево автоматично балансується, оновлюючи розміри полів вздовж шляху. Коли потрібна поточна медіана, виклик OS-SELECT з k = (n+1)/2 для непарного n або середнє значення (n/2)-го та (n/2+1)-го найменшого елементів для парного n отримує її за O(log n) часу, використовуючи розмір поля лівого дитини кореня, щоб негайно знати, чи знаходиться медіана на даний момент зліва, справа або в самому корі. Та сама ідея безпроблемно узагальнюється для будь-яких відсотків: 90-й відсоток елементів відповідає k = ceil(0.9 * n), а OS-SELECT знаходить його за допомогою одноразового спуска, незалежно від того, наскільки великим є n. Це робить дерево статистичних порядків привабливим для дашбордів і систем моніторингу, які потребують постійного звітування про показники на основі відсотків, такі як 95-й відсоток часу відповіді, що виникає з нових вимірювань, коли старі вичерпаються. Воно також перевершує наївну схему відстеження медіани двома кузнями, коли потрібні не тільки медіана, а й будь-які інші відсотки, оскільки дві кузні спеціалізовані для фіксованого розподілу, тоді як одне дерево статистичних порядків обслуговує будь-яке запит на ранжування за вимогою. Видалення будь-яких елементів, а не лише екстремальних, також обробляється чисто, на відміну від багатьох схем з кузнями, які використовують кузні для підтримки статистики.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте Order-Statistics Tree і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.