Explanation:
- A **Cartesian Tree** is a binary tree in which the heap property is satisfied (the value of each node is less than or equal to its children) and the inorder traversal of the tree gives a sorted sequence of elements.
-
- The Cartesian Tree is a binary search tree (BST) in terms of the **inorder** traversal but satisfies the **heap property** in terms of node values.
-
-
Steps:
- Insertion: Each insertion keeps the tree balanced by promoting the new element to the root and adjusting the tree using rotations (similar to splay operations).
- Heap Property: The tree must maintain the heap property such that every parent node has a value less than or equal to its children.
-
Time Complexity:
- Insertion: O(log n)
- Search: O(log n) for balanced trees, but it can be worse depending on tree shape.