DROPS

Document

DOI: 10.4230/LIPIcs.FUN.2026.28

Weak Binary Search Trees

Authors: Tobias Lauer

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract

Binary Search Trees (BST) have probably been studied more extensively than any other data structure in computer science. Their central property is the in-order invariant, which enables search for a key in time proportional to the height of the tree. Quite interestingly, the need for this strict invariant for efficient search seems to have always been taken for granted. In this paper, we introduce Weak Binary Search Trees (WST) and show that the in-order invariant can be relaxed substantially without sacrificing the O(log n) runtime bounds for search known from BST. We provide a simple and efficient search algorithm and list methods for insertion and deletion of keys in time proportional to the height of the tree. For balancing WST, rotations are less efficient than in BST. We adapt a rotation-free balancing scheme to WST, which can keep update operations in O(log n) overall time in the amortized average case.

Cite as

Tobias Lauer. Weak Binary Search Trees. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{lauer:LIPIcs.FUN.2026.28,
  author =	{Lauer, Tobias},
  title =	{{Weak Binary Search Trees}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.28},
  URN =		{urn:nbn:de:0030-drops-257474},
  doi =		{10.4230/LIPIcs.FUN.2026.28},
  annote =	{Keywords: Binary search trees, weak data structures, relaxed in-order invariant, balancing}
}

Search Results

Documents authored by Lauer, Tobias

Weak Binary Search Trees

Abstract

Cite as

Thanks for your feedback!

Could not send message