| http://dbpedia.org/ontology/abstract
|
Un arbre bicolore[réf. nécessaire], ou arb … Un arbre bicolore[réf. nécessaire], ou arbre rouge-noir ou arbre rouge et noir[réf. nécessaire] est un type particulier d'arbre binaire de recherche équilibré, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir). Cet attribut permet de garantir l'équilibre de l'arbre : lors de l'insertion ou de la suppression d'éléments, certaines propriétés sur les relations entre les nœuds et leurs couleurs doivent être maintenues, ce qui empêche l'arbre de devenir trop déséquilibré, y compris dans le pire des cas. Durant une insertion ou une suppression, les nœuds sont parfois réarrangés ou changent leur couleur afin que ces propriétés soient conservées. Le principal intérêt des arbres bicolores réside dans le fait que malgré les potentiels réarrangements ou coloriages des nœuds, la complexité (en le nombre d'éléments) des opérations d'insertion, de recherche et de suppression est logarithmique. De plus, cette structure est économe en mémoire puisqu'elle ne requiert qu'un bit supplémentaire d'information par élément par rapport à un arbre binaire classique. par rapport à un arbre binaire classique.
|
| http://dbpedia.org/ontology/discoverer
|
http://fr.dbpedia.org/resource/Rudolf_Bayer +
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Red-black_tree_example.svg?width=300 +
|
| http://dbpedia.org/ontology/wikiPageID
|
339344
|
| http://dbpedia.org/ontology/wikiPageLength
|
21769
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
186184761
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://fr.dbpedia.org/resource/Bit +
, http://fr.dbpedia.org/resource/Palo_Alto_Research_Center +
, http://fr.dbpedia.org/resource/Arbre_AVL +
, http://fr.dbpedia.org/resource/Liste_cha%C3%AEn%C3%A9e +
, http://fr.dbpedia.org/resource/Arbre_B +
, http://fr.dbpedia.org/resource/Ordonnancement_dans_les_syst%C3%A8mes_d%27exploitation +
, http://fr.dbpedia.org/resource/Arbre_%C3%A9quilibr%C3%A9 +
, http://fr.dbpedia.org/resource/Arbre_2-3-4 +
, http://fr.dbpedia.org/resource/Fichier:Red-black_tree_insert_case_D1.svg +
, http://fr.dbpedia.org/resource/Arbre_binaire +
, http://fr.dbpedia.org/resource/Fichier:Red-black_tree_insert_case_B1.svg +
, http://fr.dbpedia.org/resource/Arbre_binaire_de_recherche +
, http://fr.dbpedia.org/resource/Fichier:Red-black_tree_insert_case_C1.svg +
, http://fr.dbpedia.org/resource/Fichier:Red-black_tree_example.svg +
, http://fr.dbpedia.org/resource/Valeur_sentinelle +
, http://fr.dbpedia.org/resource/Completely_Fair_Scheduler +
, http://fr.dbpedia.org/resource/1972 +
, http://fr.dbpedia.org/resource/Structure_de_donn%C3%A9es_persistante +
, http://fr.dbpedia.org/resource/Informatique_th%C3%A9orique +
, http://fr.dbpedia.org/resource/Tableau_associatif +
, http://fr.dbpedia.org/resource/Structure_de_donn%C3%A9es +
, http://fr.dbpedia.org/resource/Rudolf_Bayer +
, http://fr.dbpedia.org/resource/Programmation_fonctionnelle +
, http://fr.dbpedia.org/resource/Rotation_d%27un_arbre_binaire_de_recherche +
, http://fr.dbpedia.org/resource/Leonidas_John_Guibas +
, http://fr.dbpedia.org/resource/Introduction_%C3%A0_l%27algorithmique +
, http://fr.dbpedia.org/resource/Noyau_Linux +
, http://fr.dbpedia.org/resource/Pointeur_%28programmation%29 +
, http://fr.dbpedia.org/resource/Robert_Sedgewick +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Arbre_%28structure_de_donn%C3%A9es%29 +
, http://fr.dbpedia.org/resource/G%C3%A9om%C3%A9trie_algorithmique +
, http://fr.dbpedia.org/resource/Complexit%C3%A9_en_temps +
|
| http://fr.dbpedia.org/property/wikiPageUsesTemplate
|
http://fr.dbpedia.org/resource/Mod%C3%A8le:R%C3%A9f%C3%A9rence_n%C3%A9cessaire +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:R%C3%A9f%C3%A9rences +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Portail +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Section_vide_ou_incompl%C3%A8te +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:%27 +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Palette +
|
| http://purl.org/dc/terms/subject
|
http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Arbre_%28structure_de_donn%C3%A9es%29 +
|
| http://www.w3.org/ns/prov#wasDerivedFrom
|
http://fr.wikipedia.org/wiki/Arbre_bicolore?oldid=186184761&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Red-black_tree_example.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Red-black_tree_insert_case_B1.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Red-black_tree_insert_case_C1.svg +
, http://commons.wikimedia.org/wiki/Special:FilePath/Red-black_tree_insert_case_D1.svg +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://fr.wikipedia.org/wiki/Arbre_bicolore +
|
| owl:sameAs |
http://id.dbpedia.org/resource/Pohon_merah-hitam +
, http://zh.dbpedia.org/resource/%E7%BA%A2%E9%BB%91%E6%A0%91 +
, http://uk.dbpedia.org/resource/%D0%A7%D0%B5%D1%80%D0%B2%D0%BE%D0%BD%D0%BE-%D1%87%D0%BE%D1%80%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE +
, http://lmo.dbpedia.org/resource/RB-alber +
, http://es.dbpedia.org/resource/%C3%81rbol_rojo-negro +
, http://da.dbpedia.org/resource/R%C3%B8d-sort_tr%C3%A6 +
, http://ru.dbpedia.org/resource/%D0%9A%D1%80%D0%B0%D1%81%D0%BD%D0%BE-%D1%87%D1%91%D1%80%D0%BD%D0%BE%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE +
, http://sv.dbpedia.org/resource/R%C3%B6d-svart_tr%C3%A4d +
, http://fr.dbpedia.org/resource/Arbre_bicolore +
, http://babelnet.org/rdf/s01996181n +
, http://he.dbpedia.org/resource/%D7%A2%D7%A5_%D7%90%D7%93%D7%95%D7%9D_%D7%A9%D7%97%D7%95%D7%A8 +
, http://fa.dbpedia.org/resource/%D8%AF%D8%B1%D8%AE%D8%AA_%D8%B3%D8%B1%D8%AE-%D8%B3%DB%8C%D8%A7%D9%87 +
, http://sr.dbpedia.org/resource/%D0%A6%D1%80%D0%B2%D0%B5%D0%BD%D0%BE-%D1%86%D1%80%D0%BD%D0%BE_%D1%81%D1%82%D0%B0%D0%B1%D0%BB%D0%BE +
, http://commons.dbpedia.org/resource/Category:Red-black_trees +
, http://ko.dbpedia.org/resource/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC +
, http://lt.dbpedia.org/resource/Raudonai_juodas_medis +
, http://g.co/kg/m/06kyj +
, http://it.dbpedia.org/resource/RB-Albero +
, http://nl.dbpedia.org/resource/Rood-zwartboom +
, http://ja.dbpedia.org/resource/%E8%B5%A4%E9%BB%92%E6%9C%A8 +
, http://de.dbpedia.org/resource/Rot-Schwarz-Baum +
, http://www.wikidata.org/entity/Q506496 +
, http://th.dbpedia.org/resource/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B9%81%E0%B8%94%E0%B8%87%E0%B8%94%E0%B8%B3 +
, http://bg.dbpedia.org/resource/%D0%A7%D0%B5%D1%80%D0%B2%D0%B5%D0%BD%D0%BE-%D1%87%D0%B5%D1%80%D0%BD%D0%BE_%D0%B4%D1%8A%D1%80%D0%B2%D0%BE +
, http://ma-graph.org/entity/126248847 +
, http://pt.dbpedia.org/resource/%C3%81rvore_rubro-negra +
, http://no.dbpedia.org/resource/R%C3%B8d-svart_tre +
, http://hu.dbpedia.org/resource/Piros-fekete_fa +
, http://vi.dbpedia.org/resource/C%C3%A2y_%C4%91%E1%BB%8F_%C4%91en +
, http://pl.dbpedia.org/resource/Drzewo_czerwono-czarne +
, http://fi.dbpedia.org/resource/Punamusta_puu +
, http://cs.dbpedia.org/resource/%C4%8Cerveno-%C4%8Dern%C3%BD_strom +
, http://hr.dbpedia.org/resource/Crveno-crno_stablo +
, http://az.dbpedia.org/resource/Qara-q%C4%B1rm%C4%B1z%C4%B1_a%C4%9Fac +
, http://dbpedia.org/resource/Red%E2%80%93black_tree +
, http://tr.dbpedia.org/resource/K%C4%B1rm%C4%B1z%C4%B1-siyah_a%C4%9Fa%C3%A7 +
|
| rdfs:comment |
Un arbre bicolore[réf. nécessaire], ou arb … Un arbre bicolore[réf. nécessaire], ou arbre rouge-noir ou arbre rouge et noir[réf. nécessaire] est un type particulier d'arbre binaire de recherche équilibré, qui est une structure de données utilisée en informatique théorique. Les arbres bicolores ont été inventés en 1972 par Rudolf Bayer qui les nomme symmetric binary B-trees (littéralement « arbres B binaires symétriques »). Chaque nœud de l'arbre possède en plus de ses données propres un attribut binaire qui est souvent interprété comme sa « couleur » (rouge ou noir). Cet attribut permet de garantir l'équilibre de l'arbre : lors de l'insertion ou de la suppression d'éléments, certaines propriétés sur les relations entre les nœuds et leurs couleurs doivent être maintenues, ce qui empêche l'arbre de devenir trop déséquilibré, y compris e de devenir trop déséquilibré, y compris
|
| rdfs:label |
Красно-чёрное дерево
, Cây đỏ đen
, 赤黒木
, Rood-zwartboom
, Червоно-чорне дерево
, RB-Albero
, Red–black tree
, Röd-svart träd
, Árvore rubro-negra
, Arbre bicolore
, Rot-Schwarz-Baum
|
| rdfs:seeAlso |
https://www.zhihu.com/topic/19648609 +
, http://mathworld.wolfram.com/Red-BlackTree.html +
, https://commons.wikimedia.org/wiki/Category:Red-black_trees +
|
