Open main menu
Home
Random
Recent changes
Special pages
Community portal
Preferences
About Wikipedia
Disclaimers
Incubator escapee wiki
Search
User menu
Talk
Dark mode
Contributions
Create account
Log in
Editing
Splay tree
(section)
Warning:
You are not logged in. Your IP address will be publicly visible if you make any edits. If you
log in
or
create an account
, your edits will be attributed to your username, along with other benefits.
Anti-spam check. Do
not
fill this in!
== Performance theorems == There are several theorems and conjectures regarding the worst-case runtime for performing a sequence ''S'' of ''m'' accesses in a splay tree containing ''n'' elements. {{Math theorem|Balance Theorem|The cost of performing the sequence ''S'' is <math>O\left[m \log n + n\log n\right]</math>. {{Math proof|Take a constant weight, e.g. {{tmath|1=w(x)=1}} for every node ''x''. Then {{tmath|1=W=n}}.}} This theorem implies that splay trees perform as well as static balanced binary search trees on sequences of at least ''n'' accesses.<ref name="SleatorTarjan" />}} {{Math theorem|Static Optimality Theorem|Let <math>q_x</math> be the number of times element ''x'' is accessed in ''S''. If every element is accessed at least once, then the cost of performing ''S'' is <math>O\left[m + \sum_{x\in tree} q_x\log\frac{m}{q_x}\right]</math> {{Math proof|Let <math>w(x)=q_x</math>. Then <math>W=m</math>.}} This theorem implies that splay trees perform as well as an optimum static binary search tree on sequences of at least ''n'' accesses.<ref>{{harvnb|Knuth|1997|p=478}}</ref> They spend less time on the more frequent items.<ref name="SleatorTarjan" /> Another way of stating the same result is that, on input sequences where the items are drawn independently at random from a non-uniform [[probability distribution]] on ''n'' items, the amortized expected ([[average-case analysis|average case]]) cost of each access is proportional to the [[Entropy (information theory)|entropy]] of the distribution.{{sfnp|Grinberg|Rajagopalan|Venkatesan|Wei|1995}}}} {{Math theorem|Static Finger Theorem|Assume that the items are numbered from 1 through ''n'' in ascending order. Let ''f'' be any fixed element (the 'finger'). Then the cost of performing ''S'' is <math>O\left[m + n\log n + \sum_{x\in sequence} \log(|x-f| + 1)\right]</math>. {{Math proof|Let <math>w(x)=1/(|x-f|+1)^2</math>. Then {{tmath|1=W=O(1)}}. The net potential drop is ''O'' (''n'' log ''n'') since the weight of any item is at least {{tmath|1=1/n^2}}.<ref name="SleatorTarjan" />}} }} {{Math theorem|Dynamic Finger Theorem|Assume that the 'finger' for each step accessing an element ''y'' is the element accessed in the previous step, ''x''. The cost of performing ''S'' is <math>O\left[m + n + \sum_{x,y\in sequence}^m \log(|y-x| + 1)\right]</math>.<ref name="ColeEtAl">{{harvnb|Cole|Mishra|Schmidt|Siegel|2000}}.</ref><ref name="Cole">{{harvnb|Cole|2000}}.</ref>}} {{Math theorem|Working Set Theorem|At any time during the sequence, let <math>t(x)</math> be the number of distinct elements accessed before the previous time element x was accessed. The cost of performing ''S'' is <math>O\left[m + n\log n + \sum_{x\in sequence} \log(t(x) + 1)\right]</math> {{Math proof|Let <math>w(x)=1/(t(x)+1)^2</math>. Note that here the weights change during the sequence. However, the sequence of weights is still a permutation of {{tmath|1=1, \tfrac 1 4, \tfrac 1 9, \cdots, \tfrac 1 {n^2} }}. So as before {{tmath|1=W=O(1)}}. The net potential drop is ''O'' (''n'' log ''n'').}} This theorem is equivalent to splay trees having [[key-independent optimality]].<ref name="SleatorTarjan" />}} {{Math theorem|Scanning Theorem|Also known as the '''Sequential Access Theorem''' or the '''Queue theorem'''. Accessing the ''n'' elements of a splay tree in symmetric order takes ''O''(''n'') time, regardless of the initial structure of the splay tree.<ref name="Tarjan">{{harvnb|Tarjan|1985}}.</ref> The tightest upper bound proven so far is <math>4.5n</math>.<ref name="Elmasry">{{harvnb|Elmasry|2004}}.</ref>}}
Edit summary
(Briefly describe your changes)
By publishing changes, you agree to the
Terms of Use
, and you irrevocably agree to release your contribution under the
CC BY-SA 4.0 License
and the
GFDL
. You agree that a hyperlink or URL is sufficient attribution under the Creative Commons license.
Cancel
Editing help
(opens in new window)