License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ESA.2018.38
URN: urn:nbn:de:0030-drops-95017
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9501/
Go to the corresponding LIPIcs Volume Portal

Golin, Mordecai ; Iacono, John ; Langerman, Stefan ; Munro, J. Ian ; Nekrich, Yakov

Dynamic Trees with Almost-Optimal Access Cost

pdf-format:
LIPIcs-ESA-2018-38.pdf (0.5 MB)

Abstract

An optimal binary search tree for an access sequence on elements is a static tree that minimizes the total search cost. Constructing perfectly optimal binary search trees is expensive so the most efficient algorithms construct almost optimal search trees. There exists a long literature of constructing almost optimal search trees dynamically, i.e., when the access pattern is not known in advance. All of these trees, e.g., splay trees and treaps, provide a multiplicative approximation to the optimal search cost.
In this paper we show how to maintain an almost optimal weighted binary search tree under access operations and insertions of new elements where the approximation is an additive constant. More technically, we maintain a tree in which the depth of the leaf holding an element e_i does not exceed min(log(W/w_i),log n)+O(1) where w_i is the number of times e_i was accessed and W is the total length of the access sequence.
Our techniques can also be used to encode a sequence of m symbols with a dynamic alphabetic code in O(m) time so that the encoding length is bounded by m(H+O(1)), where H is the entropy of the sequence. This is the first efficient algorithm for adaptive alphabetic coding that runs in constant time per symbol.

BibTeX - Entry

@InProceedings{golin_et_al:LIPIcs:2018:9501,
  author =	{Mordecai Golin and John Iacono and Stefan Langerman and J. Ian Munro and Yakov Nekrich},
  title =	{{Dynamic Trees with Almost-Optimal Access Cost}},
  booktitle =	{26th Annual European Symposium on Algorithms (ESA 2018)},
  pages =	{38:1--38:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-081-1},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{112},
  editor =	{Yossi Azar and Hannah Bast and Grzegorz Herman},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9501},
  URN =		{urn:nbn:de:0030-drops-95017},
  doi =		{10.4230/LIPIcs.ESA.2018.38},
  annote =	{Keywords: Data Structures, Binary Search Trees, Adaptive Alphabetic Coding}
}

Keywords: Data Structures, Binary Search Trees, Adaptive Alphabetic Coding
Collection: 26th Annual European Symposium on Algorithms (ESA 2018)
Issue Date: 2018
Date of publication: 14.08.2018

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI