Розширюване дерево

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Розширюване дерево (англ. splay tree) є двійковим деревом пошуку, у якому підтримується збалансованість. Це дерево належить до класу «саморегульованих дерев», які підтримують необхідний баланс галуження дерева, щоб забезпечити виконання операції пошуку, додавання і видалення за логарифмічний час від числа елементів, що зберігаються. Це реалізується без використання яких-небудь додаткових полів у вузлах дерева (як, наприклад, в Червоно-чорних деревах або АВЛ-деревах, де у вершинах зберігається, відповідно, колір вершини і глибина піддерева). Замість цього «розширювальні операції» (splay operation), частиною яких є повороти дерева, які виконуються при кожному зверненні до дерева. Облікова вартість з розрахунку на одну операцію з деревом складає O(\log n).

Розширюване дерево придумали Роберт Тарьян і Данієль Слейтор в 1985 році.

Операції[ред.ред. код]

Splay (розширення)[ред.ред. код]

Основна операція дерева. Полягає в переміщенні вершини в корінь за допомогою послідовного виконання трьох, наведених нижче, операцій: Zig, Zig-Zig і Zig-Zag. Позначимо вершину, яку хочемо перемістити в корінь за x, її родича — p, а родича p (якщо існує) — g.

Zig: виконується, коли p є коренем. Дерево повертається по ребру між x та p. Існує лише для розбору крайнього випадку і виконується лише один раз в кінці, коли початкова глибина x була непарна.

Splay tree zig.svg

Zig-Zig: виконується, коли x і p є лівими (або правими) синами. Дерево повертається по ребру між p та x.

Zigzig.gif

Zig-Zag: виконується, коли x є правим сином, а p — лівим (чи навпаки). Дерево повертається по ребру між p та x, а потім — по ребру між x та g.

Zigzag.gif

Search (пошук елемента)[ред.ред. код]

Пошук виконується як в звичайному двійковому дереві пошуку. При знаходженні елементу запускаємо Splay для нього.

Insert (додавання елемента)[ред.ред. код]

Запускаємо Split від елементу, що додається, і підвішуємо дерева, що вийшли, за нього.

Delete (видалення елемента)[ред.ред. код]

Знаходимо елемент в дереві, робимо Splay для нього, робимо поточним деревом Merge його дітей.

Merge (об'єднання двох дерев)[ред.ред. код]

Для злиття дерев T1 і T2, в яких всі ключі T1 менше ключів в T2, робимо Splay для максимального елементу T1, тоді біля кореня T1 не буде правого дочірнього елемента. Після цього робимо T2 правим дочірнім елементом T1.

Split (розділення дерева на дві частини)[ред.ред. код]

Для розділення дерева знайдемо найменший елемент, більший або рівний x і зробимо для нього Splay. Після цього відрізуємо біля кореня лівого дочірнього елемента і повертаємо 2 дерева, що вийшли.

Примітка[ред.ред. код]

Розширюване дерево, надає самозмінну структуру — структуру, що характеризується тенденцією зберігати вузли, до яких часто відбувається звернення, поблизу верхівки дерева, тоді як вузли до яких звернення відбувається рідко переміщуються ближче до листя. Таким чином час звернення до часто відвідуваних вузлів буде менший, а час звернення до рідко відвідуваних вузлів — більше середнього.

Розширюване дерево, не володіє жодними явними функціями балансування, але процес скосу вузлів до Кореня сприяє підтримці дерева в збалансованому вигляді.

Див. також[ред.ред. код]

Сбалансовані дерева:

Джерела[ред.ред. код]

  • Daniel Sleator, Robert Tarjan A data structure for dynamic trees. — Journal of Computer and System Sciences, 1983. — С. 262-391.