What does this research mean for the field?

The strict in-order invariant of binary search trees can be substantially relaxed to create Weak Binary Search Trees that maintain O(log n) runtime bounds for search. Novelty: ClaimNovelty.METHODOLOGICAL. Consensus alignment: ConsensusAlignment.CHALLENGES_CONSENSUS.

What question did this study set out to answer?

This research aims to explore and establish the concept of Weak Binary Search Trees, demonstrating that search efficiency can be maintained with a relaxed in-order invariant.

May 17, 2026Open Access

Weak Binary Search Trees

Key Points

This research aims to explore and establish the concept of Weak Binary Search Trees, demonstrating that search efficiency can be maintained with a relaxed in-order invariant.
Introduced Weak Binary Search Trees (WST) with relaxed in-order constraints.
Developed a simple yet efficient search algorithm for WST.
Adapted a rotation-free balancing scheme to maintain performance in insertion and deletion.
The search algorithm maintains O(log n) runtime bounds despite relaxed in-order invariant.
Insertion and deletion methods achieve optimal performance proportional to the height of the tree.
Overall update operations remain O(log n) in the amortized average case.

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.

KI fragen

Bookmark

View Full Paper