Cartesian tree: Difference between revisions

Revision as of 16:39, 11 December 2024

Latest revision as of 21:45, 11 July 2025

(7 intermediate revisions by 4 users not shown)

Line 27:

Another linear-time algorithm for Cartesian tree construction is based on [[Divide-and-conquer algorithm|divide-and-conquer]]. The algorithm recursively constructs the tree on each half of the input, and then merges the two trees. The merger process involves only the nodes on the left and right ''spines'' of these trees: the left spine is the path obtained by following left child edges from the root until reaching a node with no left child, and the right spine is defined symmetrically. As with any path in a min-heap, both spines have their values in sorted order, from the smallest value at their root to their largest value at the end of the path. To merge the two trees, apply a [[merge algorithm]] to the right spine of the left tree and the left spine of the right tree, replacing these two paths in two trees by a single path that contains the same nodes. In the merged path, the successor in the sorted order of each node from the left tree is placed in its right child, and the successor of each node from the right tree is placed in its left child, the same position that was previously used for its successor in the spine. The left children of nodes from the left tree and right children of nodes from the right tree remain unchanged. The algorithm is parallelizable since on each level of recursion, each of the two sub-problems can be computed in parallel, and the merging operation can be [[Merge algorithm#Parallel merge|efficiently parallelized]] as well.{{sfnp|Shun|Blelloch|2014}}

Yet another linear-time algorithm, suitableusing ifa thelinked inputlist sequencerepresentation isof giventhe ininput a linked list representationsequence, is based on ''locally maximum linking'': onethe algorithm repeatedly identifies a ''local maximum'' element, i.e., one that is larger than both its neighbors (or than its only neighbor, in case it is the first or last element in the list). This element is then removed from the list, and madeattached as the right child of its left neighbor, or the left child of its right neighbor, depending on which of the two neighbors ishas a larger value, breaking ties arbitrarily. This process can be implemented in a single left-to-right pass of the input, and it is easy to see that each element can gain at most one left-, and at most one right child, and that the resulting binary tree is a Cartesian tree of the input sequence. <ref>{{sfnp|Kozma|Saranurak|2020}}.</ref> {{sfnp|Hartmann|Kozma|Sinnamon|Tarjan|2021}}

It is possible to maintain the Cartesian tree of a dynamic input, subject to insertions of elements and [[lazy deletion]] of elements, in logarithmic [[amortized time]] per operation. Here, lazy deletion means that a deletion operation is performed by marking an element in the tree as being a deleted element, but not actually removing it from the tree. When the number of marked elements reaches a constant fraction of the size of the whole tree, it is rebuilt, keeping only its unmarked elements.{{sfnp|Bialynicka-Birula|Grossi|2006}}

Line 154:

| volume = 13

| year = 1984}}

*{{citation

| last1 = Hartmann | first1 = Maria

| last2 = Kozma | first2 = László

| last3 = Sinnamon | first3 = Corwin

| last4 = Tarjan | first4 = Robert E. | author4-link = Robert Tarjan

| doi =10.4230/LIPIcs.ICALP.2021.79

| journal = [[ICALP]]

| pages = 79:1–79:20

| title = Analysis of Smooth Heaps and Slim Heaps

| series = Leibniz International Proceedings in Informatics (LIPIcs)

| year = 2021| volume = 198

| doi-access = free

| isbn = 978-3-95977-195-5

}}

*{{citation|title=The maximum capacity route problem|first=T. C.|last=Hu|author-link=T. C. Hu|journal=Operations Research|volume=9|issue=6|year=1961|pages=898–900|jstor=167055|doi=10.1287/opre.9.6.898|doi-access=free}}

*{{citation

Line 175 ⟶ 189:

| doi = 10.1137/18M1195188

| number = 5

| journal = [[SIAM J. Comput.]]

| publisher = SIAM

| title = Smooth Heaps and a Dual View of Self-Adjusting Data Structures

| volume = 49

| year = 2020

| arxiv = 1802.05471

}}

*{{citation

Line 282 ⟶ 297:

| url = http://citeseer.ist.psu.edu/seidel96randomized.html

| volume = 16

| year = 1996| doi-broken-date = 1 NovemberJuly 20242025 }}

*{{citation

| last1 = Schieber | first1 = Baruch