Базисне дерево

В інформатиці, базисне дерево (також компактне префіксне дерево) — структура даних, яка є оптимізованим по пам'яті префіксним деревом, в якому кожна вершина, яка є єдиним нащадком, об'єднується з її батьком. В результаті кількість нащадків кожної внутрішньої вершини не перевищує базис r базисного дерева, де r — натуральне число і степінь x числа 2, x ≥ 1. На відміну від звичайних префіксних дерев, ребра можуть бути позначені як окремими елементами, так і їх послідовностями. Це робить базисні дерева набагато ефективнішими для малих наборів рядків (особливо, якщо рядки мають велику довжину) та для наборів, в яких рядки мають спільний префікс великої довжини.

На відміну від звичайних дерев (де ключі масово порівнюються від їх початку до точки нерівності), ключ кожної вершини порівнюється блоками бітів, де кількість бітів в блоці цієї вершини дорівнює базису r базисного дерева. Коли r дорівнює 2, базисне дерево є бінарним (тобто порівнює частину з 1 біта ключа цієї вершини), що мінімізує розрідженість за рахунок максимізації глибини дерева, тобто збільшення до першого неспівпадіння бітів в рядку ключа. Коли r — степінь числа 2 та не менше 4, то базисне дерево є r-нарним, яке зменшує глибину базисного дерева за рахунок потенційної розрідженості.

Застосування

Базисні дерева зручні для конструювання асоціативних масивів із ключами, які можна виразити у вигляді рядків. Вони мають застосування в маршрутизації IP, де можливість містити великі діапазони значень за деякими винятками особливо підходить для ієрархічної організації IP-адрес. Вони також використовуються для інвертованих індексів текстових документів в інформаційному пошуку.

Операції

Базисне дерево підтримує операції додавання, видалення та пошуку. Операція додавання додає новий рядок до дерева, намагаючись мінімізувати об'єм збережених даних. Операція видалення видаляє рядок з дерева. Операція пошуку включає в себе (але не обов'язково обмежується) точний пошук, знаходження попередника, знаходження наступника та знаходження всіх рядків із префіксом. Складність всіх цих операцій O(k), де k — максимальна довжина всіх рядків у наборі та довжина вимірюється у кількості бітів рівних базису дерева.

Пошук

Операція пошуку визначає, чи рядок належить дереву. Більшість операцій змінюють цей підхід певним чином для вирішення своїх конкретних завдань. Наприклад, вершина, де закінчується рядок, може мати важливе значення. Ця операція схожа на аналогічну в префіксному дереві, за винятком того, що деякі ребра містять кілька елементів.

Додавання

Щоб вставити рядок, ми виконуємо пошук у дереві, доки ми не зможемо досягти подальшого прогресу. На цьому етапі ми або додаємо нове вихідне ребро, позначене усіма елементами у вхідному рядку, які залишились, або, якщо вже існує вихідне ребро, що має префікс, який збігається з елементами у вхідному рядку, які залишились, ми розбиваємо його на два ребра (перше позначено спільним префіксом) та продовжуємо. Цей крок розділення гарантує, що жодна вершина не має більше нащадків, ніж є можливих елементів рядка.

Видалення

Щоб видалити рядок x з дерева, спершу знаходимо лист, що представляє x. Тоді, якщо x існує, ми видаляємо відповідну вершину-лист. Якщо батько цієї вершини-листа має тільки одного іншого нащадка, то позначення вхідного ребра цього нащадка додається до вхідного ребра батька, а вершина-нащадок видаляється.

Додаткові операції

• Знайти всі рядки зі спільним префіксом: повертає масив рядків, які мають однаковий префікс.
• Знайти попередника: знаходить найбільший рядок, менший ніж заданий, в лексикографічному порядку.
• Знайти наступника: знаходить найменший рядок, більший ніж заданий, в лексикографічному порядку.

Порівняння з іншими структурами даних

(У наступних порівняннях вважається, що ключі мають довжину k та структура даних містить n елементів.)

На відміну від збалансованих дерев, базисні дерева дозволяють шукати, вставляти та видаляти елементи за O(k) часу, а не O(log n). Це не схоже на перевагу, оскільки зазвичай k ≥ log n, але в збалансованому дереві кожне порівняння — це порівняння рядків, що вимагають O(k) часу у найгіршому випадку, багато з яких на практиці повільні через довгі спільні префікси (у випадку, коли порівняння починаються з початку рядка). У префіксному дереві, всі порівняння здійснюються за константний час, але для пошуку рядка довжини m потрібно здійснити m порівнянь. Базисні дерева можуть виконувати ці операції з меншою кількістю порівнянь і потребують значно менше вершин.

Базисні дерева також мають недоліки префіксних дерев, однак, оскільки вони можуть бути застосовані тільки до рядків або елементів з ефективним зворотнім співставленням до рядків, їм бракує повної універсальності збалансованих дерев пошуку, які застосовуються до будь-якого типу даних із лінійною впорядкованістю. Зворотне співставлення до рядків може бути використане для отримання необхідної лінійної впорядкованості для збалансованих дерев пошуку, але не навпаки. Це також може бути проблематично, якщо тип даних надає тільки операцію порівняння, але не операцію (де)серіалізації.