Live briefing
Everything about Cartesian tree
Binary tree derived from a sequence of numbers
In computer science, a Cartesian tree is a binary tree derived from a sequence of distinct numbers. To construct the Cartesian tree, set its root to be the minimum number in the sequence, and recursively construct its left and right subtrees from the subsequences before and after this number. It is uniquely defined as a min-heap whose symmetric (in-order) traversal returns the original sequence. Wikipedia →
🧭 Start here: a 6-step reading path
- Read the overview: Cartesian treeA 5-minute orientation
- Skim a recent paper: An efficient tree-topological local mesh refinement on Cartesian grids for multiple moving objects in incompressible flowInfluential work since 2022
- Pick up a classic book: Discrete and combinatorial mathematicsThe most-reprinted book on the subject
- Read the landmark paper: Fast algorithms for single and multiple pattern Cartesian tree matchingCited 25 times
- Go sideways: TreapA closely related topic
- Go sideways: Heap (data structure)A closely related topic
📖 Definitions
No dictionary entry for this exact phrase.
🗂️ The subject at a glance
🏆 Landmark papers (most cited)
Fast algorithms for single and multiple pattern Cartesian tree matching
A simple parallel cartesian tree algorithm and its application to parallel suffix tree construction
Finding patterns and periods in Cartesian tree matching
Hamiltonian cycles in the cartesian product of a tree and a cycle
Improvements in anisotropic models of single tree effects in Cartesian coordinates
The crossing number of Cartesian product of 5-wheels with any tree
Approximate Cartesian tree pattern matching
Subsequence Matching and LCS under Cartesian-Tree Equivalence
🆕 Influential since 2022
An efficient tree-topological local mesh refinement on Cartesian grids for multiple moving objects in incompressible flow
Robotic Tree-fruit harvesting with arrays of Cartesian Arms: A study of fruit pick cycle times
Anisotropic Cartesian Grid Generation Strategy for Arbitrarily Complex Geometry Based on a Fully Threaded Tree
The ceBWT Index: An Index for Circular Cartesian Tree Matching on Multiple Texts
Optimal radio labelings of the Cartesian product of the generalized Peterson graph and tree
📚 Books worth reading
Discrete and combinatorial mathematicsRalph P. Grimaldi · 1985- 📕How to be a quantitative ecologistJason Matthiopoulos · 2011
Genetic ProgrammingKrzysztof Krawiec · 2013
Combinatorial Matrix Theory and Generalized Inverses of MatricesRavindra B. Bapat · 2013
Introduction to Discrete MathematicsR. Hirschfelder, J. Hirschfelder · 1990
Minds and ComputersMatt Carter · 2007
Programming Game AI by ExampleMat Buckland · 2004- 📕A three-dimensional Cartesian tree-code and applications to vortex sheet roll-upKeith Lindsay · 1997
Ranked by number of editions on Open Library, a rough measure of how lasting a book is.
🔗 Related topics
- Treap In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain…
- Heap (data structure) In computer science, a heap is a tree-based data structure that satisfies the heap property: In a max heap, for any given node C, if P is the parent node…
- Binary heap A binary heap is a heap data structure that takes the form of a binary tree. Binary heaps are a common way of implementing priority queues. The binary…
- Weak heap In computer science, a weak heap is a data structure for priority queues, combining features of the binary heap and binomial heap. It can be stored in…
- Optimal binary search tree In computer science, an optimal binary search tree (Optimal BST), sometimes called a weight-balanced binary tree, is a binary search tree which provides…
- Leftist tree In computer science, a leftist tree or leftist heap is a priority queue implemented with a variant of a binary heap. Every node x has an s-value which…
- All nearest smaller values In computer science, the all nearest smaller values (ANSV) problem is: given an array A [ 1.. n ] {\displaystyle A[1..n]} , compute for each position i…
- Skew heap A skew heap (or self-adjusting heap) is a heap data structure implemented as a binary tree. Skew heaps are advantageous because of their ability to merge…