Weighted dynamic finger in binary search trees

DOI10.1137/1.9781611974331.CH49zbMATH Open1410.68101arXiv1810.01785OpenAlexW2949923424MaRDI QIDQ4575627FDOQ4575627

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)

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.

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

Recommendations

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

Mathematics Subject Classification ID

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

Cited In (10)

• On minimum generalized Manhattan connections
• Competitive Online Search Trees on Trees
• Weighted Binary Trees for Concurrent Searching
• Title not available (Why is that?)
• Multi-Finger Binary Search Trees
• Combining binary search trees
• Belga B-trees
• The geometry of binary search trees
• Better analysis of binary search tree on decomposable sequences
• Smooth heaps and a dual view of self-adjusting data structures

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)