Дерево розрізу — це самобалансуюче бінарне дерево пошуку, призначене для ефективного доступу до елементів даних на основі їхніх ключових значень. Ключовою особливістю розкосного дерева є те, що кожен раз, коли здійснюється доступ до елемента, він переміщується в корінь дерева, створюючи більш збалансовану структуру для наступних звернень.11 квітня 2024 р
Недоліки. Найсуттєвішим недоліком розкосих дерев є те, що висота розкосного дерева може бути лінійною. Наприклад, так буде після доступу до всіх n елементів у порядку неспадання.
Розширене дерево є типом бінарного дерева пошуку. На відміну від інших варіантів, таких як дерево AVL, червоно-чорне дерево або дерево козла відпущення, розкосне дерево не завжди збалансоване. Натомість його оптимізовано, щоб елементи, до яких нещодавно відкривався, швидко відкривалися знову. Ця властивість схожа за своєю природою на стек.
Операція зигзаг передбачає обертання x з його батьківським (y), а потім обертання знову з його новим батьківським (z). операція також буде використана в симетричному випадку (тобто, де x є правим дочірнім елементом y, а y є лівим дочірнім елементом z).
Видалення в Splay Tree
- Розділіть дерево на два дерева Tree1 = ліве піддерево кореня та Tree2 = праве піддерево кореня та видаліть кореневий вузол.
- Нехай корінь Tree1 і Tree2 буде Root1 і Root2 відповідно.
- Якщо Root1 дорівнює NULL: повертає Root2.
- Інакше відтворіть максимальний вузол (вузол із максимальним значенням) Tree1.
Недоліки Splay Trees: Splay-дерева можуть мати найгіршу часову складність O(n) для деяких операцій, що робить їх менш передбачуваними, ніж інші збалансовані структури даних дерева, такі як дерева AVL або червоно-чорні дерева. Розкошені дерева може не підходити для певних програм, де потрібна передбачувана продуктивність.