Weighted dynamic finger in binary search trees

DOI10.1137/1.9781611974331.CH49MaRDI QIDQ4575627zbMATH OpenOpenAlexFDO

Authors John Iacono, Stefan Langerman

Publication date 16 July 2018

Published in Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1810.01785

Mathematics Subject Classification ID

Data structures (68P05) Searching and sorting (68P10)

Abstract: 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 $w_i$ and bounding the search cost of an item in the search sequence $s_1,ldots,s_m$ by ${\displaystyle }$Oleft(1+ log frac{displaystyle sum_{min(s_{i-1},s_i) leq x leq max(s_{i-1},s_i)}w_x}{displaystyle min(w_{s_i},w_{s_{i-1}})} ight)${\displaystyle }$ amortized. 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.

Recommendations

• The geometry of binary search trees
• Weighted Binary Trees for Concurrent Searching
• scientific article; zbMATH DE number 5237331
• Combining binary search trees

Cited in

(11)

• Better analysis of binary search tree on decomposable sequences
• The geometry of binary search trees
• Weighted Binary Trees for Concurrent Searching
• Multi-Finger Binary Search Trees
• Smooth heaps and a dual view of self-adjusting data structures
• Combining binary search trees
• scientific article; zbMATH DE number 7651167 (Why is no real title available?)
• Belga B-trees
• Competitive Online Search Trees on Trees
• The group access bounds for binary search trees
• On minimum generalized Manhattan connections

This page was built for publication: Weighted dynamic finger in binary search trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4575627)