Декартове дерево () — це двійкове дерево отримане з послідовності чисел; його можна однозначно побудувати якщо дотримуватись властивостей що воно впорядковане як купа і що центрований (in-order) обхід дерева повертає оригінальну послідовність. Вперше описане Вілеміном в контексті структур даних для геометричного , декартові дерева також використовувались у визначенні таких структур даних для двійкового пошуку як та . Декартове дерево послідовності можна побудувати за лінійний час використовуючи стековий алгоритм для знаходження в послідовності.
Означення Декартове дерево послідовності різних чисел можна унікальним чином означити наступними властивостями: Декартове дерево послідовності має один вузол для кожного числа в послідовності. Кожен вузол дерева пов'язаний з єдиним елементом послідовності. Центрований (in-order) обхід дерева дає в результаті оригінальну послідовність. Тобто, ліве піддерево містить значення що зустрічаються в послідовності раніше за значення в корені дерева, а праве — значення що йдуть після кореня, і така ж умова виконується для кожного вузла. Дерево має властивість купи: предок будь-якого не кореневого вузла містить менше значення ніж той вузол. (Іноді порядок перевертають, так що предок містить більше значення, а корінь — максимальне).
Див. також Модель вкладених множин
Зноски
Література