Структури даних та хешування
АТДСловниквикористовується для маніпулювання набором елементів, вбудованих у лінійному порядку. Він підтримує динамічне редагування елементів (створення, внесення та видалення) та різні форми пошуку всередині набору (наприклад, пошук заданого елемента, найменшого, найбільшого елемента, попередника чи послідовника елемента).
Основними характеристиками словника є витрати на вставку елемента, видалення та пошук. Однак деякі реалізації словників дозволяють ефективно виконувати інші додаткові операції, такі як об'єднання словників, перехід до більшого/меншого сусіда тощо. Оцінки часу для таких ефективно виконуваних операцій ми також включатимемо в таблиці.
Зазвичай, для ефективного доступу словники організуються з урахуванням упорядкованих структур даних. Якщо такого впорядкування немає, воно вводиться. Наприклад: лексикографічний порядок для рядків, порядок для трикутників значення координати x самої лівої вершини. Найчастіше алгоритм, що використовує словник як структуру даних, сам нагадує необхідний порядок.
Найпростіший словник можна реалізувати у вигляді списку елементів у порядку надходження.
Якщо додатково підтримувати впорядкованість цього списку, маємо такі оцінки:
Двійкові дерева
У ряді додатків, де не потрібний швидкий пошук та видалення довільного елемента, і де цінні додаткові переваги, що надаються структурою списку, такий вибір є оптимальним. Однак дуже часто від словника потрібні кращі основні характеристики.
Хорошим вибором може бути двійкове дерево пошуку.
Реальний час виконання операцій залежить від форми деревини. Якщо воно схоже насписок - маємо O(n), як у списку, якщо дерево - то O(log n). Можна довести, що з послідовному включенні до дерева випадкових даних виходить саме середній час виконання операцій. Однак, якщо вхідні дані, наприклад, утворюють зростаючу послідовність, виходить список і все перевага дерева втрачено.
На практиці двійкові дерева пошуку дуже зручні в багатьох додатках, де вхідні дані є випадковими або є інші причини сподіватися на збереження деревом гарної форми. Існують способи домогтися часу O(log n) на будь-яких входах, вони корисні, але дають невеликі витрати на зберігання спеціальної інформації.
Є одна задача, яка не може бути ефективно вирішена за допомогою бінарних дерев пошуку: для заданого елемента в бінарному дереві пошуку знайти найближчі більший і менший елементи. Хоча при симетричному обході всі елементи шикуються в порядку збільшення, це не дозволяє ефективно визначити попередника та послідовника для довільного елемента.
Проблему можна ефективно вирішити з допомогою поповнення структури двійкового дерева. Класичним рішенням є пов'язані двійкові дерева пошуку, які є двійковими деревами пошуку зі зв'язковим списком, що охоплює всі вузли в порядку зростання.
Поліпшені двійкові дерева
Очевидно, пошук здійснюється тим швидше, чим ближче до кореня розташований елемент, що шукається. В ідеалі двійкове дерево пошукузбалансоване, тобто його форма така, що кожен елемент знаходиться порівняно близько до кореня. Збалансоване двійкове дерево пошуку розміру n має висоту O(log n), припущення, що шлях від кореня до кожного вузла має довжину більше, ніж O(log n). Але зовсім незбалансоване дерево пошуку маєвисоту O(n); пошук у такому дереві так само неефективний, як у зв'язаному списку.
Причин, через які дерево може стати погано збалансованим, кілька. По-перше, у багатьох додатках вхідний потік елементів не обов'язково буде випадковим (у крайньому випадку елементи вводяться в зростаючому або спадному порядку і дерево, що виходить, в більшості випадків виявляється незбалансованим). По-друге, порядок операцій пошуку (перемежуються з операціями введення) може бути непередбачуваним (пошук нещодавно введених елементів може виявитися особливо дорогим, оскільки елемент може виявитися на нижньому рівні двійкового дерева). По-третє, очікувані властивості дерев пошуку, що вийшло після виконання операцій видалення не завжди добре зрозумілі.
У цьому підрозділі будуть розглянуті різні варіації двійкових дерев, що дозволяють досягти більш стабільної, а отже, більш швидкої роботи.
Один із підходів полягає у балансуванні дерева після кожної операції. Таким чином, виходять суворі обмеження на висоту вузла, і, як наслідок, гарантована оцінка O(logn) для операцій.
Інший підхід полягає в рандомізації алгоритму, тобто введення датчика випадкових чисел, від якого (а не від вхідної послідовності) і залежатиме форма дерева. Таким чином, дерево виходить 'випадковим' з оцінкою O(log n).