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

Articles by others on the same topic (0)

There are currently no matching articles.