= Consecutive keys in a binary search tree
Two stored keys $a<b$ are consecutive when no stored key lies strictly between them. Their numerical difference need not be one. After <splaying> on $a$ followed by <splaying> on $b$, the node $a$ is the left child of $b$ with an empty right <subtree>. To prove this, after the first call $b$ is the minimum of the right <subtree> of $a$. The last step crossing $a$ is either a <zig step> or a right-left <zig-zag step>; both make $a$ the left child of $b$. A nonempty right <subtree> of $a$ would require a stored key strictly between them.
Back to article page
