Splayboom
Uit Wikipedia, de vrije encyclopedia
Een splayboom is een zelf-balancerende binaire zoekboom, met de extra eigenschap dat vaak bezochte toppen dichter bij de wortel zitten (en dus sneller gevonden worden). Standaardbewerkingen zoals toevoegen, opzoeken en verwijderen van een top worden uitgevoerd in O(n) tijd voor één bewerking, maar geamortiseerd in O(log(n)) tijd voor een reeks van n bewerkingen. Voor vele niet (volledig) willekeurig reeksen van bewerkingen presteren splaybomen beter dan standaard binaire zoekbomen, voornamelijk wanneer een relatief kleine deelverzameling van de toppen van de boom vaak bezocht worden. Alle bewerkingen op een splayboom worden uitgevoerd zoals bij een normale binaire zoekboom, maar ze worden gevolgd door een splaystap. De splayboom is ontwikkeld door Daniel Sleator en Robert Tarjan