Основным материалом нужно считать вот эту статью (и следующие две за ней): https://habrahabr.ru/post/101818/
А также материал file:/zksh_cartesian.pdf
После него предлагаю реализовать либо AVL- либо красно-чёрное сбалансированное дерево.
Задачи
1. Предумать и реализовать струкруру, в которой будет храниться декартово дерево
2. Попробовать реализовать операцию слияния двух декартовых деревьев
3. Попробовать реализовать операцию разрезания декартова дерева