Сортування й пошук: Рецептурний довідник, страница 12

¨  Для червоно-чорних дерев у кожному вузлі потрібно зберігати посилання на лівого й правого нащадка, а також посилання на предка. Крім того, десь потрібно зберігати й кольори вузла! Хоча на кольори достатній тільки один біт, через вирівнювання структур, необхідного для ефективності доступу, як правило, буде витрачено більше місця. Таким чином, кожний вузол червоно-чорного дерева вимагає пам'яті, якої вистачило б на 3-4 покажчика.

¨  Для розділених списків у кожному вузлі є посилання нульового рівня. Імовірність мати посилання рівня 1 дорівнює S. Імовірність мати посилання рівня 2 дорівнює j. Загалом, кількість посилань на вузол дорівнює

• Час. Алгоритм повинен бути ефективним. Це особливо важливо, коли очікуються більші обсяги даних. У таблиці 3.2 рівняються часи пошуку для кожного алгоритму. Зверніть увагу на те, що найгірші випадки для хеш-таблиц і розділених списків надзвичайно малоймовірні. Експериментальні дані описані нижче.
• Простота. Якщо алгоритм короткий і простий, при його реалізації й/або використанні помилки будуть допущені з меншою ймовірністю. Крім того, це полегшує проблеми супроводу програм. Кількості операторів, що виконують у кожному алгоритмі, також утримуються в таблиці 3.2.

      Таблиця 0.2: Порівняння алгоритмів ведення словників

      У таблиці 3.3 наведені часи, вимагаємоые для вставки, пошуку й видалення 65536 (2¹⁶) випадкових елементів. У цих експериментах розмір хеш-таблицы рівнявся10009, для розділених списків допускалося до 16 рівнів посилань. Звичайно, у реальних ситуаціях часи можуть відрізнятися від наведених тут, однак, таблиця дає досить інформації для вибору підходящого алгоритму.

Таблиця 0.3: Середній час (мсек) для 65536 випадкових елементів

      У таблиці 3.4 наведені середні часи пошуку для двох випадків: випадкових даних, і впорядкованих, значення яких надходили в зростаючому порядку. Упорядковані дані є найгіршим випадком для незбалансованих дерев, оскільки дерево вироджується у звичайний однозв'язний список. Наведено часи для “одиночного” пошуку. Якби нам знадобилося знайти всі 65536 елементів, то красно-черныму дереву знадобилося б 6 секунд, а незбалансованому - близько 1 години.

Таблиця 0.4: Середній час пошуку (мсек)

4. Тексти програм

typedef int T;          /* type of item to be sorted */

typedef int tblIndex;   /* type of subscript */

#define compGT(a,b) (a > b)

void insertSort(T *a, tblIndex lb, tblIndex ub) {

    T t;

    tblIndex i, j;

   /**************************

    *  sort array a[lb..ub]  *