Відкрити головне меню

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

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

МалюнокРедагувати

 

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

Деталізований малюнокРедагувати

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

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

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

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

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

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

Поворот для балансуванняРедагувати

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

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

Відстань обертанняРедагувати

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

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

ПосиланняРедагувати

Див. такожРедагувати