Content deleted Content added
Citation bot (talk | contribs) Alter: title. Add: isbn. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox | #UCB_webform_linked 116/1109 Tag: Reverted |
Citation bot (talk | contribs) Altered doi-broken-date. | Use this bot. Report bugs. | #UCB_CommandLine |
||
| (19 intermediate revisions by 6 users not shown) | |||
Line 26:
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, using a linked list representation of the input sequence, is based on ''locally maximum linking'': the 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 attached as the right child of its left neighbor, or the left child of its right neighbor, depending on which of the two neighbors has 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. {{sfnp|Kozma|Saranurak|2020}} {{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 102 ⟶ 104:
| title = STACS 2006, 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings
| volume = 3884
| year = 2006| isbn = 978-3-540-32301-3
}}
| year = 2006}}▼
*{{citation|contribution=On Cartesian trees and range minimum queries|first1=Erik D.|last1=Demaine|author1-link=Erik Demaine|first2=Gad M.|last2=Landau|first3=Oren|last3=Weimann|series=Lecture Notes in Computer Science|volume=5555|year=2009|pages=341–353|doi=10.1007/978-3-642-02927-1_29|title=Automata, Languages and Programming, 36th International Colloquium, ICALP 2009, Rhodes, Greece, July 5-12, 2009|isbn=978-3-642-02926-4|hdl=1721.1/61963|hdl-access=free}}
*{{citation
| last1 = Fischer | first1 = Johannes
| last2 = Heun | first2 = Volker
| title = Combinatorial Pattern Matching▼
| contribution = Theoretical and Practical Improvements on the RMQ-Problem, with Applications to LCA and LCE
▲ | title = Proceedings of the 17th Annual Symposium on Combinatorial Pattern Matching
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
Line 120 ⟶ 122:
| last1 = Fischer | first1 = Johannes
| last2 = Heun | first2 = Volker
| title = Combinatorics, Algorithms, Probabilistic and Experimental Methodologies▼
| contribution = A New Succinct Representation of RMQ-Information and Improvements in the Enhanced Suffix Array.
▲ | title = Proceedings of the International Symposium on Combinatorics, Algorithms, Probabilistic and Experimental Methodologies
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
Line 132 ⟶ 134:
| last1 = Gabow | first1 = Harold N. | author1-link = Harold N. Gabow
| last2 = Bentley | first2 = Jon Louis | author2-link = Jon Bentley (computer scientist)
| last3 = Tarjan | first3 = Robert E.
| contribution = Scaling and related techniques for geometry problems
| doi = 10.1145/800057.808675
Line 139 ⟶ 141:
| pages = 135–143
| publisher = ACM
| title = STOC '84: Proc. 16th ACM Symp. Theory of Computing
| year = 1984| title-link = Symposium on Theory of Computing
| s2cid = 17752833 }}
Line 151 ⟶ 154:
| volume = 13
| year = 1984}}
*{{citation
*{{citation|title=The maximum capacity route problem|first=T. C.|last=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}}▼
| 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
| last1 = Kim | first1 = Sung-Hwan
Line 164 ⟶ 181:
| title = 32nd Annual Symposium on Combinatorial Pattern Matching, CPM 2021, July 5-7, 2021, Wrocław, Poland
| volume = 191
| year = 2021| doi-access = free
| isbn = 9783959771863 }}
*{{citation
| last1 = Kozma | first1 = László
| last2 = Saranurak | first2 = Thatchaphol
| doi = 10.1137/18M1195188
| number = 5
| journal = [[SIAM J. Comput.]]
| publisher = SIAM
| volume = 49
| arxiv = 1802.05471
}}
*{{citation
Line 178 ⟶ 208:
| last1 = Levcopoulos | first1 = Christos
| last2 = Petersson | first2 = Ola
▲ | title = Algorithms and Data Structures
| contribution = Heapsort - Adapted for Presorted Files
| doi = 10.1007/3-540-51542-9_41
Line 185 ⟶ 214:
| publisher = Springer-Verlag
| series = Lecture Notes in Computer Science
| title = WADS '89: Proceedings of the Workshop on Algorithms and Data Structures
| volume = 382
| year = 1989| isbn = 978-3-540-51542-5
}}
*{{citation
| last1 = Nishimoto | first1 = Akio
Line 203 ⟶ 233:
| title = String Processing and Information Retrieval - 28th International Symposium, SPIRE 2021, Lille, France, October 4-6, 2021, Proceedings
| volume = 12944
| year = 2021| isbn = 978-3-030-86691-4
}}
*{{citation
Line 221 ⟶ 251:
| title = 33rd Annual Symposium on Combinatorial Pattern Matching, CPM 2022, June 27-29, 2022, Prague, Czech Republic
| volume = 223
| year = 2022| doi-access = free
| isbn = 9783959772341 | s2cid = 246679910
}}
Line 239 ⟶ 270:
| title = 30th Annual Symposium on Combinatorial Pattern Matching, CPM 2019, June 18-20, 2019, Pisa, Italy
| volume = 128
| year = 2019| doi-access = free
| isbn = 9783959771030 | s2cid = 162168587
}}
Line 265 ⟶ 297:
| url = http://citeseer.ist.psu.edu/seidel96randomized.html
| volume = 16
| year = 1996| doi-broken-date = 1 July 2025 }}
*{{citation
| last1 = Schieber | first1 = Baruch
| |||