Декартове дерево

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

Декартово дерево - це двійкове дерево, у вузлах якого зберігаються посилання на праве і ліве піддерево, посилання на батьківський вузол (необов'язково), ключі x і y, які є двійковим деревом пошуку по ключу x і двійковій купою по ключу y. А саме, для будь-якого вузла дерева n ключі x вузлів правого (лівого) піддереві більше (менше або рівні) ключа x вузла n, ключі y вузлів правого і лівого дітей більше або рівні ключу y вузла n. Посилання на батьківський вузол не обов'язкове, вона бажана тільки для лінійного алгоритму побудови дерева.

Термінологія[ред.ред. код]

В англомовній літературі декартово дерево, побудоване для масиву із заданих ключів і привласнених їм при побудові випадкових ваг називається словом-записником treap, тому що поєднує властивості сортуючого дерева-купи (heap) і випадкового двійкового дерева (tree) з логарифмічним очікуванням висоти.

Найпростіший алгоритм побудови декартового дерева. Властивість однозначності структури[ред.ред. код]

Найпростіший для розуміння алгоритм побудови декартового дерева по безлічі даних пар (x, y) виглядає наступним чином. Впорядкуємо всі пари по ключу x і пронумеруємо вийшла послідовність ключів y:

y (1), y (2), y (3), ..., y (n).

Знайдемо мінімальний ключ y. Нехай це буде y (k). Він буде коренем дерева. Ключ y (k) ділить послідовність ключів y на дві:

y (1), ..., y (k-1); y (k +1), ..., y (n).

У кожній з них знайдемо мінімальний y - це будуть діти вузла y (k) - лівий і правий. З отриманими 4 шматочками (можливо менше) поступимо аналогічним чином. Запропонований алгоритм побудови декартового дерева заснований на рекурсії: знаходимо в послідовності мінімальний y і призначаємо його коренем. знайдений y розбиває послідовність на дві частини, для кожної з частин запускаємо алгоритм побудови декартового дерева. Схематично це можна записати так:

T( y(1), ..., y(n) ) =  root: y(k)   
                           left_tree: T( y(1), ..., y(k−1) )   
                           right_tree: T( y(k+1), ..., y(n)) )
                        where  y(k) = min( y(1), ..., y(n) )

З даного алгоритму випливає, що безліч пар (x, y) однозначно визначає структуру декартового дерева. Зауважимо для порівняння, що безліч ключів, які зберігаються в двійковому дереві пошуку не визначають однозначно структуру дерева. Те ж саме стосується двоичной купи - якою буде структура двійковій купи (як ключі розподіляться по вузлах) залежить не тільки від самого безлічі ключів, але і від послідовності їх додавання. У декартовому дереві такої неоднозначності немає.

Лінійний алгоритм побудови дерева[ред.ред. код]

Інший алгоритм побудови дерева також заснований на рекурсії. Тільки тепер ми послідовно будемо додавати елементи y і перебудовувати дерево. Дерево T (y (1), ..., y (k +1)) буде будуватися з дерева T (y (1), ..., y (k)) і наступного елемента y (k +1).

T( y(1), ..., y(k+1) ) = F ( T( y(1), ..., y(k) ), y(k+1) )

На кожному кроці будемо пам'ятати посилання на останній доданий вузол. Він буде самим правим. Дійсно, ми впорядкували ключі y по прикріпленому до них ключу x. Так як декартово дерево - це дерево пошуку, то після проекції на горизонтальну пряму ключі x повинні зростати зліва направо. Самий правий вузол завжди має максимально можливе значення ключа x. Функція F, яка відображає декартово дерево T (y (1), ..., y (k)) попереднього кроку і чергове y (k +1) в нове дерево T (y (1), ..., y (k +1)) , виглядає наступним чином. Вертикаль для вузла y (k +1) визначена. Нам необхідно визначитися з його горизонталлю. Для початку ми перевіряємо, чи можна новий вузол y (k +1) зробити правим дитиною вузла y (k) - це слід зробити, якщо y (k +1)> y (k). Інакше ми робимо крок по схилу від вузла y (k) вгору і дивимося на значення y, яке там зберігається. Піднімаємося вгору по схилу, поки не знайдемо вузол, в якому значення y менше, ніж y (k +1), після чого робимо y (k +1) його правим дитиною, а його попереднього правого дитини робимо лівим дитиною вузла y (k + 1). Це алгоритм амортизаційні (в сумі за всі кроки) працює лінійне (по числу додаються вузлів) час. Дійсно, як тільки ми «переступили» через будь-який вузол, піднімаючись вгору по схилу, то ми його вже ніколи не зустрінемо при додаванні наступних вузлів. Таким чином, сумарне число кроків вгору по схилу не може бути більше загального числа вузлів.

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

Література[ред.ред. код]