Self-balancing binary search tree (original) (raw)

About DBpedia

平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。

thumbnail

Property Value
dbo:abstract En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave. Tiempos para varias operaciones en términos del número de nodos en el árbol n: Para algunas implementaciones estos tiempos son el peor caso, mientras que para otras están amortizados. Estructuras de datos populares que implementan este tipo de árbol: * Árbol AVL * Árbol rojo-negro (es) In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing". For height-balanced binary trees, the height is defined to be logarithmic in the number of items. This is the case for many binary search trees, such as AVL trees and red–black trees. Splay trees and treaps are self-balancing but not height-balanced, as their height is not guaranteed to be logarithmic in the number of items. Self-balancing binary search trees provide efficient implementations for mutable ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets. (en) 平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。 (ja) 컴퓨터 과학에서 자가 균형 (높이 균형) 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리이다. 이 자료 구조는 변경이 가능한 정렬된 리스트의 효율적인 구현이며, 연관 배열(associative array), 우선순위 큐, 과 같은 다른 로 쓰일 수 있다. (ko) In informatica, un albero binario di ricerca bilanciato è un albero binario di ricerca la cui altezza, grazie a particolari condizioni che la sua struttura deve soddisfare, rimane limitata. Queste condizioni implicano delle operazioni di inserimento ed eliminazione più complesse rispetto a quelle di semplici alberi binari, ma garantiscono che esse vengano eseguite in O(log n). (it) Em ciência da computação, uma árvore binária de busca balanceada ou árvore binária de busca auto-balanceada é qualquer árvore de busca binária que automaticamente mantém a sua altura (número máximo de níveis abaixo da raiz) pequeno mesmo depois de sucessivas inserções e exclusões arbitrárias. Estas estruturas fornecem implementações eficientes para listas ordenadas mutáveis, podendo ser usadas para outras estruturas de dados abstratas, tais como arrays associativos, e conjuntos. (pt) 平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。 (zh)
dbo:thumbnail wiki-commons:Special:FilePath/Unbalanced_binary_tree.svg?width=300
dbo:wikiPageExternalLink https://xlinux.nist.gov/dads/HTML/heightBalancedTree.html http://adtinfo.org/
dbo:wikiPageID 378310 (xsd:integer)
dbo:wikiPageLength 8194 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID 1092928206 (xsd:integer)
dbo:wikiPageWikiLink dbr:Quicksort dbr:Scapegoat_tree dbr:Binary_search_tree dbr:Binary_tree_sort dbr:Day–Stout–Warren_algorithm dbr:Node_(computer_science) dbr:Online_algorithm dbr:Search_data_structure dbr:Geometric_series dbr:Logarithm dbr:Cache_(computing) dbr:Computational_geometry dbr:Computer_science dbr:Priority_queue dbr:B-tree dbr:Treap dbr:Weight-balanced_tree dbr:Fusion_tree dbr:Linked_list dbr:Abstract_data_type dbr:Amortized_analysis dbr:2–3_tree dbr:Floor_and_ceiling_functions dbr:Hash_table dbr:Heapsort dbr:Asymptotic dbr:AA_tree dbr:AVL_tree dbc:Binary_trees dbc:Trees_(data_structures) dbr:Big_O_notation dbr:Red–black_tree dbr:Associative_array dbr:Splay_tree dbr:Merge_sort dbr:Randomized_algorithm dbr:Tree_rotation dbr:Set_(abstract_data_type) dbr:Sorting dbr:Tango_tree dbr:Point_location dbr:Line_segment_intersection dbr:Skip_list dbr:List_(computing) dbr:Asymptotically_optimal dbr:In-order_iteration dbr:Key_(database) dbr:Random_binary_search_tree dbr:Computational_overhead dbr:File:Unbalanced_binary_tree.svg dbr:File:BinaryTreeRotations.svg dbr:File:AVLtreef.svg
dbp:wikiPageUsesTemplate dbt:CS-Trees dbt:Refimprove dbt:Reflist dbt:Short_description dbt:Data_structures
dct:subject dbc:Binary_trees dbc:Trees_(data_structures)
gold:hypernym dbr:Tree
rdf:type yago:WikicatSovietInventions yago:Ability105616246 yago:Abstraction100002137 yago:Arrangement105726596 yago:Cognition100023271 yago:Creativity105624700 yago:DataStructure105728493 yago:Invention105633385 yago:PsychologicalFeature100023100 dbo:Plant yago:Structure105726345 yago:WikicatDataStructures
rdfs:comment 平衡二分探索木（へいこうにぶんたんさくぎ、英: self-balancing binary search tree）とは、計算機科学において二分探索木のうち木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするもの（）である。平衡二分探索木は連想配列や集合その他の抽象データ型を実装する最も効率のよいデータ構造の1つである。 (ja) 컴퓨터 과학에서 자가 균형 (높이 균형) 이진 탐색 트리는 삽입과 삭제가 일어나는 경우에 자동으로 그 높이(루트에서부터 내려갈 수 있는 최대 레벨)를 작게 유지하는 노드 기반 이진 탐색 트리이다. 이 자료 구조는 변경이 가능한 정렬된 리스트의 효율적인 구현이며, 연관 배열(associative array), 우선순위 큐, 과 같은 다른 로 쓰일 수 있다. (ko) In informatica, un albero binario di ricerca bilanciato è un albero binario di ricerca la cui altezza, grazie a particolari condizioni che la sua struttura deve soddisfare, rimane limitata. Queste condizioni implicano delle operazioni di inserimento ed eliminazione più complesse rispetto a quelle di semplici alberi binari, ma garantiscono che esse vengano eseguite in O(log n). (it) Em ciência da computação, uma árvore binária de busca balanceada ou árvore binária de busca auto-balanceada é qualquer árvore de busca binária que automaticamente mantém a sua altura (número máximo de níveis abaixo da raiz) pequeno mesmo depois de sucessivas inserções e exclusões arbitrárias. Estas estruturas fornecem implementações eficientes para listas ordenadas mutáveis, podendo ser usadas para outras estruturas de dados abstratas, tais como arrays associativos, e conjuntos. (pt) 平衡树是计算机科学中的一类数据结构，为改进的二叉查找树。一般的二叉查找树的查询复杂度取决于目标结点到树根的距离（即深度），因此当结点的深度普遍较大时，查询的均摊复杂度会上升。为了实现更高效的查询，产生了平衡树。 在这里，平衡指所有叶子的深度趋于平衡，更广义的是指在树上所有可能查找的均摊复杂度偏低。 (zh) En ciencias de la computación, un árbol binario de búsqueda auto-balanceable o equilibrado es un árbol binario de búsqueda que intenta mantener su altura, o el número de niveles de nodos bajo la raíz, tan pequeños como sea posible en todo momento, automáticamente. Esto es importante, ya que muchas operaciones en un árbol de búsqueda binaria tardan un tiempo proporcional a la altura del árbol, y los árboles binarios de búsqueda ordinarios pueden tomar alturas muy grandes en situaciones normales, como cuando las claves son insertadas en orden. Mantener baja la altura se consigue habitualmente realizando transformaciones en el árbol, como la rotación de árboles, en momentos clave. (es) In computer science, a self-balancing binary search tree (BST) is any node-based binary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these abstract data structures receive the attribute "self-balancing". (en)
rdfs:label Árbol binario de búsqueda auto-balanceable (es) Albero binario di ricerca bilanciato (it) 平衡二分探索木 (ja) 자가 균형 이진 탐색 트리 (ko) Self-balancing binary search tree (en) Árvore binária de busca balanceada (pt) 平衡树 (zh)
owl:sameAs freebase:Self-balancing binary search tree yago-res:Self-balancing binary search tree wikidata:Self-balancing binary search tree dbpedia-es:Self-balancing binary search tree dbpedia-fa:Self-balancing binary search tree dbpedia-it:Self-balancing binary search tree dbpedia-ja:Self-balancing binary search tree dbpedia-ko:Self-balancing binary search tree dbpedia-lmo:Self-balancing binary search tree dbpedia-pt:Self-balancing binary search tree dbpedia-sr:Self-balancing binary search tree dbpedia-th:Self-balancing binary search tree dbpedia-zh:Self-balancing binary search tree https://global.dbpedia.org/id/2KK8h
prov:wasDerivedFrom wikipedia-en:Self-balancing_binary_search_tree?oldid=1092928206&ns=0
foaf:depiction wiki-commons:Special:FilePath/BinaryTreeRotations.svg wiki-commons:Special:FilePath/AVLtreef.svg wiki-commons:Special:FilePath/Unbalanced_binary_tree.svg
foaf:isPrimaryTopicOf wikipedia-en:Self-balancing_binary_search_tree
is dbo:wikiPageRedirects of dbr:SBB_tree dbr:Height-balanced_binary_search_tree dbr:Height-balanced_binary_tree dbr:Height-balanced_tree dbr:Relaxed_balance dbr:Admissible_tree dbr:Balanced_binary_search_tree dbr:Balanced_binary_tree dbr:Balanced_tree dbr:Balanced_trees dbr:Binary_self-balancing_search_tree dbr:Self-balancing_binary_tree dbr:Root_balance
is dbo:wikiPageWikiLink of dbr:Scapegoat_tree dbr:List_of_data_structures dbr:Binary_search_algorithm dbr:Binary_search_tree dbr:Binary_tree dbr:Bloom_filter dbr:List_of_graph_theory_topics dbr:Day–Stout–Warren_algorithm dbr:Dynamic_array dbr:Dynamic_problem_(algorithms) dbr:Interval_tree dbr:T-tree dbr:Geometry_of_binary_search_trees dbr:Order_statistic_tree dbr:Search_data_structure dbr:Container_(abstract_data_type) dbr:Dancing_tree dbr:WAVL_tree dbr:Rebalance dbr:Array_(data_structure) dbr:Bentley–Ottmann_algorithm dbr:Left-leaning_red–black_tree dbr:Standard_Template_Library dbr:Comparison_of_programming_languages_(associative_array) dbr:PAM_library dbr:Peek_(data_type_operation) dbr:Priority_queue dbr:Suffix_tree dbr:Sweep_line_algorithm dbr:B-tree dbr:Time_complexity dbr:Tree_sort dbr:Weight-balanced_tree dbr:Fusion_tree dbr:Garsia–Wachs_algorithm dbr:Join-based_tree_algorithms dbr:Linked_list dbr:List-labeling_problem dbr:List_(abstract_data_type) dbr:Hash_table dbr:AA_tree dbr:AVL_tree dbr:Red–black_tree dbr:Dijkstra's_algorithm dbr:Associative_array dbr:Associative_containers dbr:Sorting_algorithm dbr:Splay_tree dbr:Selection_algorithm dbr:Set_(abstract_data_type) dbr:Iacono's_working_set_structure dbr:List_of_terms_relating_to_algorithms_and_data_structures dbr:Tango_tree dbr:Rotation_distance dbr:Single-access_key dbr:Multimap dbr:Sorted_array dbr:Random_access dbr:Search_tree dbr:SBB_tree dbr:Height-balanced_binary_search_tree dbr:Height-balanced_binary_tree dbr:Height-balanced_tree dbr:Relaxed_balance dbr:Admissible_tree dbr:Balanced_binary_search_tree dbr:Balanced_binary_tree dbr:Balanced_tree dbr:Balanced_trees dbr:Binary_self-balancing_search_tree dbr:Self-balancing_binary_tree dbr:Root_balance
is foaf:primaryTopic of wikipedia-en:Self-balancing_binary_search_tree