2026-09-30T09:24:39Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25747 2026-09-23T23:49:14Z ddc:004 open_access

Weak Binary Search Trees Lauer, Tobias Binary search trees weak data structures relaxed in-order invariant balancing 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tobias Lauer 2026 Is Part Of LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FUN.2026.28 urn:nbn:de:0030-drops-257474 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.28 eng https://creativecommons.org/licenses/by/4.0/legalcode