| 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 |
wiki-commons:Special:FilePath/Cartesian_tree.svg?width=300 |
| dbo:wikiPageExternalLink |
http://www.cs.sunysb.edu/~bender/pub/lca.ps http://citeseer.ist.psu.edu/seidel96randomized.html |
| dbo:wikiPageID |
15843635 (xsd:integer) |
| dbo:wikiPageLength |
22406 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID |
1100496685 (xsd:integer) |
| dbo:wikiPageWikiLink |
dbr:Cartesian_plane dbr:Euler_tour dbr:Binary_heap dbr:Binary_search_tree dbr:Binary_tree dbr:All_nearest_smaller_values dbr:Path_graph dbr:Permutation dbr:SIAM_Journal_on_Computing dbr:Linear_time dbr:Logarithm dbr:Lowest_common_ancestor dbr:Communications_of_the_ACM dbr:Computer_science dbr:Parallel_algorithm dbr:Priority_queue dbc:Sorting_algorithms dbr:Treap dbr:Tree_traversal dbr:Data_structure dbr:Widest_path_problem dbr:Heap_(data_structure) dbr:Lecture_Notes_in_Computer_Science dbr:Potential_method dbr:Randomized_binary_search_tree dbr:Range_searching dbc:Binary_trees dbr:Stack_(data_structure) dbr:Sorting_algorithm dbr:Merge_algorithm dbr:Minimum_spanning_tree dbr:Selection_sort dbr:Tree_rotation dbr:Range_Minimum_Query dbr:Ultrametric_space dbr:Cartesian_coordinate dbr:Heap_sort dbr:Random_binary_search_tree dbr:Binary_search dbr:Sequential_search dbr:File:Bracketing_pairs.svg dbr:File:Cartesian_tree.svg dbr:File:Cartesian_tree_range_searching.svg |
| dbp:wikiPageUsesTemplate |
dbt:CS-Trees dbt:Citation dbt:For dbt:Harvtxt dbt:Main_article dbt:Refbegin dbt:Refend dbt:Reflist dbt:Sfnp dbt:Sorting |
| dct:subject |
dbc:Sorting_algorithms dbc:Binary_trees |
| gold:hypernym |
dbr:Tree |
| rdf:type |
yago:WikicatSortingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Event100029378 yago:Procedure101023820 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity dbo:Plant yago:Rule105846932 yago:SortingAlgorithm105847658 |
| 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 |
freebase:Cartesian tree yago-res:Cartesian tree wikidata:Cartesian tree dbpedia-de:Cartesian tree dbpedia-es:Cartesian tree dbpedia-fa:Cartesian tree dbpedia-fr:Cartesian tree dbpedia-sr:Cartesian tree dbpedia-th:Cartesian tree dbpedia-uk:Cartesian tree dbpedia-zh:Cartesian tree https://global.dbpedia.org/id/4gQi5 |
| prov:wasDerivedFrom |
wikipedia-en:Cartesian_tree?oldid=1100496685&ns=0 |
| foaf:depiction |
wiki-commons:Special:FilePath/Bracketing_pairs.svg wiki-commons:Special:FilePath/Cartesian_tree.svg wiki-commons:Special:FilePath/Cartesian_tree_range_searching.svg |
| foaf:isPrimaryTopicOf |
wikipedia-en:Cartesian_tree |
| is dbo:wikiPageDisambiguates of |
dbr:Cartesian |
| is dbo:wikiPageWikiLink of |
dbr:List_of_data_structures dbr:All_nearest_smaller_values dbr:Best,_worst_and_average_case dbr:René_Descartes dbr:Search_data_structure dbr:Range_query_(data_structures) dbr:Lowest_common_ancestor dbr:Comparison_sort dbr:Random_binary_tree dbr:Adaptive_heap_sort dbr:Adaptive_sort dbr:Treap dbr:Widest_path_problem dbr:Cartesian dbr:Heapsort dbr:Jean_Vuillemin dbr:Range_minimum_query dbr:Message_Passing_Interface dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:List_of_things_named_after_René_Descartes dbr:Stern–Brocot_tree |
| is foaf:primaryTopic of |
wikipedia-en:Cartesian_tree |
