Weak Binary Search Trees

Traditionally, a binary search tree (BST) $T$ is a binary tree with the following property, known as in-order invariant:

For each node $N$ in $T$, all keys stored in the left subtree of $N$ are less than the key stored in $N$, and all keys stored in the right subtree of $N$ are greater than the key stored in $N$. (Throughout this paper, we assume that all keys are distinct.)

This property allows a search algorithm to use the key in each node as a router, (or, pivot) to direct the search, i.e. to decide the subtree in which the search is continued. A simple, iterative lookup procedure is given in Algorithm 1.

The search can be imagined like a “probe” traveling down one path in the tree by following one child pointer on each level. Clearly, $key(N)$ plays a crucial part in the algorithm, as it is not only a data element but also serves as a split key or router for the lookup process. One main question this paper addresses is whether the search for $x$ can be directed efficiently without $key(N)$ or any augmented field in $N$ acting as a split key.

Weak variants of data structures have been proposed especially in the context of heaps. Dutton uses weak heaps to improve heap sort [5]. Hinze introduced semi-heaps to implement priority search queues [8].

Binary search trees are among the earliest and most basic data structures and are covered in virtually every introductory computer science textbook. Research on the topic has been going on for more than 60 years, and countless data structures have evolved from BST or been built upon them. A comprehensive overview would be far beyond the scope of this paper and is not required as background for our work. For balanced trees, very good overviews are provided in [2] and [9].

Despite the abundance of research on search trees, surprisingly little work can be found about whether and how the in-order invariant can be modified or relaxed without breaking the complexity bounds of standard search tree operations. To the best of our knowledge, the only published research related to the topic was done by De et al. in their work on an “in-place” version of priority search trees [3][4]. They propose an array-based structure supporting certain 2D range queries on point sets, and requiring only $O(1)$ extra memory for construction from an input array. In some of their range query algorithms, the authors use a similar dual-probing approach as we do.

We define weak binary search trees as follows:

Notice that no condition is imposed on the key $key(N)$ stored in $N$ itself. Hence, the tree shown in Figure 1 is a WST, but not a BST. (Since the strict in-order invariant of BSTs obviously satisfies the weaker invariant, any BST is of course also a WST.)

We observe that the relaxed invariant still ensures that all keys stored on the same tree level are in ascending order from left to right. This follows directly from the WST invariant. However, a WST loses the ability to produce a sorted list of all keys by an in-order (i.e. depth-first) traversal of the tree. In addition, the key stored in a node $N$ cannot be used as a split key in order to direct the further search.

Hence, it may seem that efficient search is not possible because in the worst case a search algorithm will always need to visit both subtrees of $N$, effectively increasing the number of inspected nodes on each level. This point is also typically made in adversary arguments put forward by large language models (LLMs) when presented with the definition of the WST data structure and asked about efficient search in it. We invite the reader to stop and think about why this argument is insufficient, and to try and find an efficient search algorithm.

In order to explain our search in a WST, we introduce the following binary relation among nodes in a tree.

It follows from the definition that the in-sight relation is symmetric, i.e. $M\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-05-22-17-05-46-page-1.pdf2svg.svg" id="S4.SS1.p2.m1.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="9" height="5" style="width: 18px; height: unset; max-width: 100\%"></object>}N\iff N\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-05-22-17-05-46-page-1.pdf2svg.svg" id="S4.SS1.p2.m1.g2nest" class="ltx\_graphics ltx\_img\_landscape" width="9" height="5" style="width: 18px; height: unset; max-width: 100\%"></object>}M$. We can therefore also say that two nodes $M$ and $N$ are, or are not, in sight (of each other). It also follows straight from the definition that the relation is reflexive: $\forall N\in T:N\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-05-22-17-05-46-page-1.pdf2svg.svg" id="S4.SS1.p2.m4.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="9" height="5" style="width: 18px; height: unset; max-width: 100\%"></object>}N$.

Obviously, any two sibling nodes in a binary tree are in sight of each other. In addition, nodes down on deeper levels of neighbouring subtrees can be in sight of each other. In Figure 1, the two grandchildren of the root with keys $43$ and $73$ are in sight of each other, as are those with keys $42$ and $59$. Furthermore, two nodes with only empty subtrees between them are also in sight. For instance, the nodes with keys $15$ and $44$ on the bottom level in Figure 1 are in sight of each other.

We now outline how lookup of a key $x$ can be implemented efficiently on a WST $T$. Instead of using a single pointer for searching, we keep a pair $(L,R)$ of node pointers that are updated together during each step down the tree, such that $key(L)\le key(R)$, $L\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-05-22-17-05-46-page-1.pdf2svg.svg" id="S4.SS2.p1.m5.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="9" height="5" style="width: 18px; height: unset; max-width: 100\%"></object>}R$ and $x\in T(L)\cup T(R)$. Algorithm 2 gives an iterative approach, while Algorithm 3 lists a recursive variant of the same procedure when initially called with the pair $(root(T),root(T))$.

Note: In line 5, the condition is assumed to return $false$ if $L_{right}=null$. The same goes for the condition in line 7 if $R_{left}=null$. The functions $leftmost(N)$ and $rightmost(N)$ return the leftmost/rightmost existing child node of node $N$, or $null$ if no child exists.

When inserting a new key $k$ in a WST, a suitable insert position can be located via a variant of the lookup operation returning the last visited pair of nodes on the search path if $k\notin T$. Note that due to the relaxed in-order invariant, there may be more than one possible insert position for $k$. For instance, when arriving at a leaf node $L$, the new node containing $k$ can be inserted as either left or right child of $L$ without violating the WST invariant.

A recursive Insert procedure is listed in Algorithm 4. In addition to key $k$, it takes as its input a pair $(L,R)$ of nodes (either $L\text{<object type="image/svg+xml" data="dagpub-standalone-manual-2026-05-22-17-05-46-page-1.pdf2svg.svg" id="S5.SS1.p2.m3.g1nest" class="ltx\_graphics ltx\_img\_landscape" width="9" height="5" style="width: 18px; height: unset; max-width: 100\%"></object>}R\wedge key(L)\le key(R)$, or one of them $null$) and descends down the tree recursively using the pair-walk technique. As $L$ and $R$ move down one level of the tree in each recursive call and attaching the new node is a constant-time operation, the overall time for an insertion is obviously in $O(h)$.

Deletion of a key $x$ from a WST $T$ is particularly easy. First, we locate the node $N$ containing $x$ with a search that also keeps track of the parent(s) of the last visited pair of nodes. If $N$ is a leaf, we can remove it from its parent and are done.

If $N$ is an internal node, we replace $key(N)$ by the key stored in any leaf node of $T(N)$ (and remove that leaf). This will not violate the WST invariant, as the swapped key is only moving upward on its search path.

Clearly, this way of deletion of a key can be carried out in time $O(h)$, as it requires at most one pass down the tree, swap of a key, and removal of one leaf node. A listing of the corresponding algorithm is left as an exercise to the reader.

Quite surprisingly, a simple rotation can destroy the (weaker) WST invariant. Nodes changing their parent-child relationship in the tree and becoming siblings during a rotation may be out of order with their sibling. An example is shown in Figures 4 and 5.

The reason is that while the in-order invariant is a relationship directly between parent and child keys, the WST invariant is only concerned with neighboring subtrees and oblivious of the key in the common parent node of those subtrees.

Even worse, the possible violation of the WST invariant is not purely local and can affect more than just the two sibling nodes. In Figure 5, subtree $B$ and even subtree $A$ may contain keys larger than $43$, which can destroy the WST on a larger scale. Hence, simply swapping the two sibling keys $43$ and $18$ is not sufficient for restoring the WST invariant in the given example.

Fixing the WST after such a rotation therefore involves a larger number of nodes and requires additional passes down the tree. In order to remain in $O(\log n)$ total time for an update operation, a single rotation must remain in $O(\log n)$ time (including subsequent fixes of the invariant) and the number of rotations per update must be bounded by a constant.

We briefly sketch the procedure for fixing the WST invariant after rotations, using the example of the right-rotation from Figure 5:

1. 1.

   Arrange the keys of the nodes $A,B,C$ involved in the right-rotation such that the maximum key $m$ is stored in the right sibling node $X$.

2. 2.

   Find the maximum key $ma{x}_B$ in subtree $B$ (for subtree designations, cf. Figure 5).

3. 3.

   If $ma{x}_B>m$, remove $m$ from $X$ and replace it by any key from either subtree $C$ or $D$ (all of which are guaranteed to be greater then $ma{x}_B$). Then insert key $m$ in $T$ (it will be inserted either in subtree $A$ or $B$).

This restores the WST invariant, but may in turn unbalance the subtree where $m$ was inserted. In fact, in the worst case a whole cascade of fixes might be caused until the WST is balanced. The number of steps in the cascade is bounded by the height of $T$, which, in the balanced case, is $O(\log n)$. Since each restore step also takes time $O(\log n)$, a complete rebalancing operation may take up to $O({\log }^{2}n)$ time.

This makes rebalancing more expensive than in BST, and it is an open question whether it is possible in WST to keep updates in $O(\log n)$ worst-case time when using rotations.

As an alternative to rotations, rebalancing can be achieved by restructuring the unbalanced subtree in a different way. A well-known example are scapegoat trees [6], which have the additional charm that they require no balancing information at all in nodes, but only a global integer to maintain information about the tree size. Scapegoat trees are (loosely) weight-balanced, and rebalancing after an update is delayed until a certain threshold of unbalancedness has been reached. In this case the complete unbalanced subtree $S$ is rebuilt from scratch into a perfectly balanced tree. This requires sorting all keys in $S$, which breaks the logarithmic worst-case time bound of a single update, but due to delayed rebalancing, the complexity of updates remains in $O(\log n)$ amortized time for standard BST. Also note that rebuilding $S$ requires some extra memory (cf. [6] for details).

The above logarithmic time bound is possible since a sorted list of all keys of a subtree $S$ in a BST can easily be produced in linear time, as it merely requires an in-order traversal of $S$. In WST, however, keys are not arranged in-order and hence sorting the keys of a subtree is not straightforward. We outline a procedure to turn the keys of a WST subtree $S$ into a sorted list. We then show that this can be carried out in $O(|S|)$ average time, as long as $S_{left}$ and $S_{right}$ are each balanced. (This is the case if $root(S)$ is the first unbalanced node above the position of the update causing the unbalance.)

Algorithm 5 recursively creates sorted key lists from both subtrees of $N$, joins them (i.e. appends one to the other) and then inserts $key(N)$ at its appropriate position, such that the resulting list is sorted again. Both $join$ and $insert$ can be achieved in average logarithmic time using skip lists [10].