Linear-time construction of treaps and Cartesian trees
type: Item
instance of: scholarly article
title: Linear-time construction of treaps and Cartesian trees
zbMATH Open document ID: 0815.68047
DOI: 10.1016/0020-0190(94)00150-2
author: Mark Allen Weiss
published in: Information Processing Letters
publication date: 1994-12-01T00:00:00Z
Mathematics Subject Classification ID: 68P10
Mathematics Subject Classification ID: 68P05
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 699128
zbMATH Keywords: heap-ordered deque
zbMATH Keywords: search tree
zbMATH Keywords: treap
zbMATH Keywords: Cartesian tree
MaRDI profile type: Publication
full work available at URL: 0020-0190(94)00150-2
OpenAlex ID: W2010509073
cites work: Q4230325
cites work: New Results on Dynamic Planar Point Location
cites work: Q4335210
cites work: Solution of a Divide-and-Conquer Maximin Recurrence
cites work: Priority Search Trees
cites work: Self-adjusting binary search trees
cites work: A unifying look at data structures
cites work: Q4864244
Recommended article: Construction of a tree from its traversals in optimal time and space
Recommended article: A linear-time algorithm for the generation of trees
Recommended article: Q2753956
Recommended article: Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
Recommended article: Linear-time algorithms for tree root problems
Recommended article: Linear-Time Algorithms for Tree Root Problems
Recommended article: A Faster CREW PRAM Algorithm for Computing Cartesian Trees
Recommended article: A linear algorithm for compact box-drawings of trees
Recommended article: Constructing optimal search trees in optimal time
description: scientific article; zbMATH DE number 699128