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

Послідовність значень і декартове дерево яке їй відповідає.

Декартове дерево (англ. Cartesian tree) — це двійкове дерево отримане з послідовності чисел; його можна однозначно побудувати якщо дотримуватись властивостей що воно впорядковане як купа і що центрований (in-order) обхід дерева повертає оригінальну послідовність. Вперше описане Вілеміном в контексті структур даних для геометричного пошуку за областю, декартові дерева також використовувались у визначенні таких структур даних для двійкового пошуку як treap та рандомізоване двійкове дерево пошуку. Декартове дерево послідовності можна побудувати за лінійний час використовуючи стековий алгоритм для знаходження всіх найближчих менших значень в послідовності.

Означення

Декартове дерево послідовності різних чисел можна унікальним чином означити наступними властивостями:

1. Декартове дерево послідовності має один вузол для кожного числа в послідовності. Кожен вузол дерева пов'язаний з єдиним елементом послідовності.

1. Центрований (in-order) обхід дерева дає в результаті оригінальну послідовність. Тобто, ліве піддерево містить значення що зустрічаються в послідовності раніше за значення в корені дерева, а праве — значення що йдуть після кореня, і така ж умова виконується для кожного вузла.
2. Дерево має властивість купи: предок будь-якого не кореневого вузла містить менше значення ніж той вузол. (Іноді порядок перевертають, так що предок містить більше значення, а корінь — максимальне).

Див. також

• Модель вкладених множин

Література

• Vuillemin, Jean (1980). A Unifying Look at Data Structures. Commun. ACM. 23 (4): 229—239. doi:10.1145/358841.358852. ISSN 0001-0782. Процитовано 18 серпня 2017.