SearchTree

In Kone, search trees are structures that consist of:

1. an order on values called "priorities" (thus, search tree is contextful)

2. and a tree (in computer science sense of the word) that holds several pairs of one priority value and one corresponding element in each its vertex and satisfies search tree property:

• each vertex's children are linearly ordered,

• each non-leaf vertex contains one pair less than the number of its children,

• for any given non-leaf vertex \(A\), if \(C_0\), ..., \(C_n\) are children of \(A\) sorted increasingly and \(P_1\), ..., \(P_n\) are \(A\)'s priorities sorted increasingly as well, then \(C_0 \leqslant P_1 \leqslant C_1 \leqslant ... \leqslant C_{n-1} \leqslant P_n \leqslant C_n\) where \(C \leqslant P\) (\(P \leqslant C\)) means that all the priorities in a subtree with root \(C\) are less (greater) or equal to \(P\).

This interface's inheritors must have some specific structure that provides optimised search. Without it (or with bad time complexity like \(O(n)\)) the interface should not be used.

Inheritors