TY - GEN
T1 - Weighted dynamic finger in binary search trees
AU - Iacono, John
AU - Langerman, Stefan
PY - 2016
Y1 - 2016
N2 - It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight wi and bounding the search cost of an item in the search sequence si,..., sm (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.
AB - It is shown that the online binary search tree data structure GreedyASS performs asymptotically as well on a sufficiently long sequence of searches as any static binary search tree where each search begins from the previous search (rather than the root). This bound is known to be equivalent to assigning each item i in the search tree a positive weight wi and bounding the search cost of an item in the search sequence si,..., sm (Equation presented) This result is the strongest finger-type bound to be proven for binary search trees. By setting the weights to be equal, one observes that our bound implies the dynamic finger bound. Compared to the previous proof of the dynamic finger bound for Splay trees, our result is significantly shorter, stronger, simpler, and has reasonable constants.
UR - http://www.scopus.com/inward/record.url?scp=84963522569&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84963522569&partnerID=8YFLogxK
U2 - 10.1137/1.9781611974331.ch49
DO - 10.1137/1.9781611974331.ch49
M3 - Conference contribution
AN - SCOPUS:84963522569
T3 - Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms
SP - 672
EP - 691
BT - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
A2 - Krauthgamer, Robert
PB - Association for Computing Machinery
T2 - 27th Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2016
Y2 - 10 January 2016 through 12 January 2016
ER -