TY - GEN
T1 - On the Dynamic Finger Conjecture for splay trees extended abstract
AU - Cole, Richard
PY - 1990
Y1 - 1990
N2 - The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree is O(m + n + Σ log(|ij - ij-1$/|), where the sum is from i = 1 to m and the jth access is to the ijth item in symmetric order (the i0th item is the item originally at the root of the tree). In other words, the amortized cost of an access is O(1 + log d), where the current access is at distance d from the previous access (distance being measured in terms of the number of items straddled by the two successive accesses); in addition, there is an additive O(n) initialization cost. A bound on the cost is obtained.
AB - The Dynamic Finger Conjecture for splay trees states that the cost of m searches on an n-node splay tree is O(m + n + Σ log(|ij - ij-1$/|), where the sum is from i = 1 to m and the jth access is to the ijth item in symmetric order (the i0th item is the item originally at the root of the tree). In other words, the amortized cost of an access is O(1 + log d), where the current access is at distance d from the previous access (distance being measured in terms of the number of items straddled by the two successive accesses); in addition, there is an additive O(n) initialization cost. A bound on the cost is obtained.
UR - http://www.scopus.com/inward/record.url?scp=0025137205&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0025137205&partnerID=8YFLogxK
M3 - Conference contribution
AN - SCOPUS:0025137205
SN - 0897913612
T3 - Proc 22nd Annu ACM Symp Theory Comput
SP - 8
EP - 17
BT - Proc 22nd Annu ACM Symp Theory Comput
PB - Publ by ACM
T2 - Proceedings of the 22nd Annual ACM Symposium on Theory of Computing
Y2 - 14 May 1990 through 16 May 1990
ER -