Поворот дерева

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

Домовленість, у який бік зсуваються вершини і є напрямком поворота.

Малюнок

Припустимо, що це бінарне дерево пошуку, тож інтерпретуємо елементи як змінні величини, а не як букви.

Деталізований малюнок

Графічне пояснення як робляться повороти.

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

Використовую термінологія - Root для кореневої вершини для поворота, Pivot для вершини яка займе місце кореневої, RS для назви сторони з якої здійснюється поворот і OS для сторони протилежної повороту. Тоді можна записати такий псевдо-код повороту.

Pivot = Root.OS
Root.OS = Pivot.RS
Pivot.RS = Root
Root = Pivot

Час такої операції не залежить від висоти дерева.

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

Поворот для балансування

Графічне пояснення яким чином поворот збалансовує АВЛ-дерево.

Дерево може бути збалансоване використовуючи повороти. Після поворота, одна із сторін збільшує висоту на одиницю, у той час як інша зменшує. Отже, важливо використовувати повороти для вершин у яких висота лівого і правого піддерева різниться більше ніж на одиницю. Самозбалансовані дерева пошуку роблять це автоматично. АВЛ-дерево використовує таку балансировку.

Відстань обертання

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

Прорахунок відстані обертання - одна з відкритих проблем математики.

Посилання

• Java applets demonstrating tree rotations (dynamic)(англ.)
• Java applets demonstrating tree rotations(англ.)
• The AVL Tree Rotations Tutorial (RTF) by John Hargrove(англ.)

Див. також

• Червоно-чорне дерево.
• Асоціативність.