| http://dbpedia.org/ontology/abstract
|
Un arbre splay (ou arbre évasé) est un arb … Un arbre splay (ou arbre évasé) est un arbre binaire recherche auto-balancé possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas ou les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue. Cette structure de données a été inventée par (en) et Robert Tarjan en 1985. Toutes les opérations courantes sur les structures de données sont suivies d'une opération basique nommée évasement (splaying en anglais). Évaser un arbre autour d'un certain élément consiste à réarranger l'arbre afin que cet élément soit placé à la racine tout en conservant la structure ordonnée de l'arbre. Une manière d'obtenir cela est d'effectuer une recherche ordinaire sur un arbre binaire en mémorisant le chemin suivi, puis d'effectuer une série de rotations d'arbre afin d'amener l'élément à la racine. D'autres implémentations permettent d'effectuer ces deux opérations en une seule passe.er ces deux opérations en une seule passe.
|
| http://dbpedia.org/ontology/thumbnail
|
http://commons.wikimedia.org/wiki/Special:FilePath/Zig.gif?width=300 +
|
| http://dbpedia.org/ontology/wikiPageExternalLink
|
http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf +
|
| http://dbpedia.org/ontology/wikiPageID
|
611080
|
| http://dbpedia.org/ontology/wikiPageLength
|
6059
|
| http://dbpedia.org/ontology/wikiPageRevisionID
|
178814541
|
| http://dbpedia.org/ontology/wikiPageWikiLink
|
http://fr.dbpedia.org/resource/Analyse_amortie +
, http://fr.dbpedia.org/resource/Principe_de_localit%C3%A9_%28informatique%29 +
, http://fr.dbpedia.org/resource/Structure_de_donn%C3%A9es +
, http://fr.dbpedia.org/resource/Arbre_AVL +
, http://fr.dbpedia.org/resource/Rotation_d%27un_arbre_binaire_de_recherche +
, http://fr.dbpedia.org/resource/Fichier:Zig.gif +
, http://fr.dbpedia.org/resource/Fichier:Zigzag.gif +
, http://fr.dbpedia.org/resource/Fichier:Zigzig.gif +
, http://fr.dbpedia.org/resource/Arbre_binaire_de_recherche +
, http://fr.dbpedia.org/resource/1985 +
, http://fr.dbpedia.org/resource/Journal_of_the_ACM +
, http://fr.dbpedia.org/resource/Robert_Tarjan +
, http://fr.dbpedia.org/resource/M%C3%A9moire_cache +
, http://fr.dbpedia.org/resource/Cat%C3%A9gorie:Arbre_%28structure_de_donn%C3%A9es%29 +
, http://fr.dbpedia.org/resource/Ramasse-miettes_%28informatique%29 +
|
| http://fr.dbpedia.org/property/année
|
1985
|
| http://fr.dbpedia.org/property/doi
|
10.1145
|
| http://fr.dbpedia.org/property/fr
|
Daniel Sleator
|
| http://fr.dbpedia.org/property/langue
|
en
|
| http://fr.dbpedia.org/property/lireEnLigne
|
http://www.cs.cmu.edu/~sleator/papers/self-adjusting.pdf +
|
| http://fr.dbpedia.org/property/nom
|
Sleator
, Tarjan
|
| http://fr.dbpedia.org/property/numéro
|
3
|
| http://fr.dbpedia.org/property/passage
|
652
|
| http://fr.dbpedia.org/property/prénom
|
Robert E.
, Daniel D.
|
| http://fr.dbpedia.org/property/périodique
|
http://fr.dbpedia.org/resource/Journal_of_the_ACM +
|
| http://fr.dbpedia.org/property/titre
|
Self-Adjusting Binary Search Trees
|
| http://fr.dbpedia.org/property/volume
|
32
|
| http://fr.dbpedia.org/property/wikiPageUsesTemplate
|
http://fr.dbpedia.org/resource/Mod%C3%A8le:Article +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:%C3%89bauche +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Palette +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Lien +
, http://fr.dbpedia.org/resource/Mod%C3%A8le:Portail +
|
| 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_splay?oldid=178814541&ns=0 +
|
| http://xmlns.com/foaf/0.1/depiction
|
http://commons.wikimedia.org/wiki/Special:FilePath/Zigzig.gif +
, http://commons.wikimedia.org/wiki/Special:FilePath/Zigzag.gif +
, http://commons.wikimedia.org/wiki/Special:FilePath/Zig.gif +
|
| http://xmlns.com/foaf/0.1/isPrimaryTopicOf
|
http://fr.wikipedia.org/wiki/Arbre_splay +
|
| owl:sameAs |
http://ma-graph.org/entity/163155148 +
, http://cs.dbpedia.org/resource/Splay_strom +
, http://sr.dbpedia.org/resource/%D0%A0%D0%B0%D1%88%D0%B8%D1%80%D0%B5%D0%BD%D0%BE_%D0%B4%D1%80%D0%B2%D0%BE +
, http://th.dbpedia.org/resource/%E0%B8%95%E0%B9%89%E0%B8%99%E0%B9%84%E0%B8%A1%E0%B9%89%E0%B8%AA%E0%B9%80%E0%B8%9B%E0%B8%A5%E0%B8%A2%E0%B9%8C +
, http://vi.dbpedia.org/resource/C%C3%A2y_splay +
, http://ru.dbpedia.org/resource/Splay-%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE +
, http://ja.dbpedia.org/resource/%E3%82%B9%E3%83%97%E3%83%AC%E3%83%BC%E6%9C%A8 +
, http://de.dbpedia.org/resource/Splay-Baum +
, http://fa.dbpedia.org/resource/%D8%AF%D8%B1%D8%AE%D8%AA_%DA%AF%D8%B3%D8%AA%D8%B1%D8%AF%D9%87 +
, http://g.co/kg/m/070w4 +
, http://pl.dbpedia.org/resource/Drzewo_splay +
, http://es.dbpedia.org/resource/%C3%81rbol_biselado +
, http://pt.dbpedia.org/resource/%C3%81rvore_splay +
, http://zh.dbpedia.org/resource/%E4%BC%B8%E5%B1%95%E6%A0%91 +
, http://he.dbpedia.org/resource/%D7%A2%D7%A5_Splay +
, http://nl.dbpedia.org/resource/Splayboom +
, http://dbpedia.org/resource/Splay_tree +
, http://it.dbpedia.org/resource/Albero_splay +
, http://fi.dbpedia.org/resource/Splay-puu +
, http://www.wikidata.org/entity/Q80729 +
, http://fr.dbpedia.org/resource/Arbre_splay +
, http://uk.dbpedia.org/resource/%D0%A0%D0%BE%D0%B7%D1%88%D0%B8%D1%80%D1%8E%D0%B2%D0%B0%D0%BD%D0%B5_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE +
|
| rdfs:comment |
Un arbre splay (ou arbre évasé) est un arb … Un arbre splay (ou arbre évasé) est un arbre binaire recherche auto-balancé possédant en outre la propriété que les éléments auxquels on a récemment accédé (pour les ajouter, les regarder ou les supprimer) sont rapidement accessibles. Ils disposent ainsi d'une complexité amortie en O(log n) pour les opérations courantes comme insertion, recherche ou suppression. Ainsi dans le cas ou les opérations possèdent une certaine structure, ces arbres constituent des bases de données ayant de bonnes performances, et ceci reste vrai même si cette structure est a priori inconnue. Cette structure de données a été inventée par (en) et Robert Tarjan en 1985.nventée par (en) et Robert Tarjan en 1985.
|
| rdfs:label |
Árvore splay
, Splay-дерево
, Splay-Baum
, Розширюване дерево
, Splayboom
, Cây splay
, Albero splay
, Arbre splay
, スプレー木
, Splay tree
|
