Splay strom je samovyvažující se binární vyhledávací strom mající tu vlastnost, že prvky, k nimž se nedávno přistupovalo, jsou rychle znovu dostupné. Provádí základní operace jako vkládání, vyhledávání a odstraňování prvků v amortizovaném čase O(log n). Pro mnoho nerovnoměrných posloupností operací pracují splay stromy lépe než ostatní vyhledávací stromy, a to i v případě, že charakteristika posloupnosti není předem známá.
| Property | Value |
|---|
| prop-cs:wikiPageUsesTemplate
| |
| dbpedia-owl:abstract
|
- Splay strom je samovyvažující se binární vyhledávací strom mající tu vlastnost, že prvky, k nimž se nedávno přistupovalo, jsou rychle znovu dostupné. Provádí základní operace jako vkládání, vyhledávání a odstraňování prvků v amortizovaném čase O(log n). Pro mnoho nerovnoměrných posloupností operací pracují splay stromy lépe než ostatní vyhledávací stromy, a to i v případě, že charakteristika posloupnosti není předem známá. Splay strom byl vynalezen Danielem Sleatorem a Robertem Tarjanem.Všechny obvyklé operace na binárních vyhledávacích stromech jsou spojeny s jednou základní, které se říká splay. Splay uzlu přeuspořádá strom tak, že se daný uzel dostane do kořene. Způsob, jak toho docílit, je provést standardní vyhledávání daného uzlu v binárním stromu a následně provést speciální rotace stromu takové, aby se uzel dostal do kořene.
|
| dbpedia-owl:wikiPageExternalLink
| |
| dbpedia-owl:wikiPageID
| |
| dbpedia-owl:wikiPageLength
| |
| dbpedia-owl:wikiPageOutDegree
| |
| dbpedia-owl:wikiPageRevisionID
| |
| dbpedia-owl:wikiPageWikiLink
| |
| dbpedia-owl:wikiPageWikiLinkText
| |
| dcterms:subject
| |
| rdfs:comment
|
- Splay strom je samovyvažující se binární vyhledávací strom mající tu vlastnost, že prvky, k nimž se nedávno přistupovalo, jsou rychle znovu dostupné. Provádí základní operace jako vkládání, vyhledávání a odstraňování prvků v amortizovaném čase O(log n). Pro mnoho nerovnoměrných posloupností operací pracují splay stromy lépe než ostatní vyhledávací stromy, a to i v případě, že charakteristika posloupnosti není předem známá.
|
| rdfs:label
| |
| prov:wasDerivedFrom
| |
| foaf:isPrimaryTopicOf
| |
| is dbpedia-owl:wikiPageRedirects
of | |
| is dbpedia-owl:wikiPageWikiLink
of | |
| is foaf:primaryTopic
of | |
