| dbo:abstract
|
- In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Introduced by in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence. (en)
- Ein kartesischer Baum ist ein aus einer Folge von Zahlen abgeleiteter Binärheap, mit der zusätzlichen Eigenschaft, dass ein in-order-Durchlauf wieder die ursprüngliche Folge liefert. Der kartesische Baum für eine Folge kann in Linearzeit konstruiert werden. (de)
- En Ciencias de la Computación, un árbol cartesiano es un árbol binario que se deriva de una sucesión de números; se define únicamente a partir de que cumple con una ordenación a modo de montículo y de que un recorrido entre-orden del árbol retorna la secuencia original de números. Introducido por en el contexto de las estructuras de datos de búsqueda en rangos geométricos, los árboles cartesianos también han sido utilizados en la definición del treap y árboles aleatorios binarios de búsqueda para problemas de búsqueda binaria. El árbol cartesiano de una secuencia puede ser construido en tiempo lineal usando un algoritmo de pila para encontrar todos los menores valores más cercanos en una secuencia. (es)
- En algorithmique, un arbre cartésien est un arbre binaire construit à partir d'une séquence de nombres. Il est défini comme un tas dont un parcours symétrique de l'arbre renvoie la séquence d'origine. (fr)
- Декартове дерево (англ. Cartesian tree) — це двійкове дерево отримане з послідовності чисел; його можна однозначно побудувати якщо дотримуватись властивостей що воно впорядковане як купа і що центрований (in-order) обхід дерева повертає оригінальну послідовність. Вперше описане Вілеміном в контексті структур даних для геометричного , декартові дерева також використовувались у визначенні таких структур даних для двійкового пошуку як та . Декартове дерево послідовності можна побудувати за лінійний час використовуючи стековий алгоритм для знаходження в послідовності. (uk)
- 笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。 (zh)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 22406 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| dbp:wikiPageUsesTemplate
| |
| dcterms:subject
| |
| gold:hypernym
| |
| rdf:type
| |
| rdfs:comment
|
- In computer science, a Cartesian tree is a binary tree derived from a sequence of numbers; it can be uniquely defined from the properties that it is heap-ordered and that a symmetric (in-order) traversal of the tree returns the original sequence. Introduced by in the context of geometric range searching data structures, Cartesian trees have also been used in the definition of the treap and randomized binary search tree data structures for binary search problems. The Cartesian tree for a sequence may be constructed in linear time using a stack-based algorithm for finding all nearest smaller values in a sequence. (en)
- Ein kartesischer Baum ist ein aus einer Folge von Zahlen abgeleiteter Binärheap, mit der zusätzlichen Eigenschaft, dass ein in-order-Durchlauf wieder die ursprüngliche Folge liefert. Der kartesische Baum für eine Folge kann in Linearzeit konstruiert werden. (de)
- En Ciencias de la Computación, un árbol cartesiano es un árbol binario que se deriva de una sucesión de números; se define únicamente a partir de que cumple con una ordenación a modo de montículo y de que un recorrido entre-orden del árbol retorna la secuencia original de números. Introducido por en el contexto de las estructuras de datos de búsqueda en rangos geométricos, los árboles cartesianos también han sido utilizados en la definición del treap y árboles aleatorios binarios de búsqueda para problemas de búsqueda binaria. El árbol cartesiano de una secuencia puede ser construido en tiempo lineal usando un algoritmo de pila para encontrar todos los menores valores más cercanos en una secuencia. (es)
- En algorithmique, un arbre cartésien est un arbre binaire construit à partir d'une séquence de nombres. Il est défini comme un tas dont un parcours symétrique de l'arbre renvoie la séquence d'origine. (fr)
- Декартове дерево (англ. Cartesian tree) — це двійкове дерево отримане з послідовності чисел; його можна однозначно побудувати якщо дотримуватись властивостей що воно впорядковане як купа і що центрований (in-order) обхід дерева повертає оригінальну послідовність. Вперше описане Вілеміном в контексті структур даних для геометричного , декартові дерева також використовувались у визначенні таких структур даних для двійкового пошуку як та . Декартове дерево послідовності можна побудувати за лінійний час використовуючи стековий алгоритм для знаходження в послідовності. (uk)
- 笛卡尔树是一种特定的二叉树数据结构，可由数列构造，在范围最值查询、范围top k查询（range top k queries）等问题上有广泛应用。它具有堆的有序性，中序遍历可以输出原数列。笛卡尔树结构由Vuillmin(1980)在解决范围搜索的几何数据结构问题时提出。从数列中构造一棵笛卡尔树可以线性时间完成，需要采用基于栈的算法来找到在该数列中的所有最近小数。 (zh)
|
| rdfs:label
|
- Kartesischer Baum (de)
- Árbol cartesiano (es)
- Cartesian tree (en)
- Arbre cartésien (fr)
- 笛卡尔树 (zh)
- Декартове дерево (uk)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageDisambiguates
of | |
| is dbo:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
