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

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

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

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

Малюнок[ред.ред. код]

Tree rotation.png

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

Деталізований малюнок[ред.ред. код]

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

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

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

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

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

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

Поворот для балансування[ред.ред. код]

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

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

Відстань обертання[ред.ред. код]

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

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

Посилання[ред.ред. код]

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