Декартове дерево (cartesian tree, treap) — красива структура даних, що легко реалізується, яка з мінімальними зусиллями дозволить вам робити багато швидкісних операцій над масивами ваших даних.
| Декартове дерево | |
|---|---|
| Тип | Двійковий дерево пошуку |
| Рік винаходу | 1989 |
| Автор | Raimund Siedel, Cecilia Aragon |
| Складність у О-символіці |
Бінарне дерево (англ. binary tree) – це впорядковане кореневе дерево, у кожної вершини якого є трохи більше двох синів. У бінарне дерево кожен син довільної вершини визначається як лівий чи правий.