English
O(log n). Get the i-th element of the set by left-to-right order. If i is out of range, return none.
Русский
O(log n). Получить i-й элемент множества слева направо; если i выходит за пределы, вернуть none.
LaTeX
$$$$ \\mathrm{nth}: \\ Ordnode\\; \\alpha \\to \\mathbb{N} \\to \\mathrm{Option}\\; \\alpha, \\quad \\mathrm{nth}(\\nil, i)=\\mathrm{none}, \\\\ \\mathrm{nth}(\\text{node}\\; \\_\\; l\\; x\\; r, i) = \\begin{cases} \\mathrm{some}\\; x \\quad \\text{если } i = |l| \\\\ \\mathrm{nth}(l,i) \\quad \\text{если } i < |l| \\\\ \\mathrm{nth}(r,i-|l|-1) \\quad \\text{если } i > |l| \\end{cases} $$$$
Lean4
/-- O(log n). Get the `i`th element of the set, by its index from left to right.
nth {a, b, c, d} 2 = some c
nth {a, b, c, d} 5 = none -/
def nth : Ordnode α → ℕ → Option α
| nil, _ => none
| node _ l x r, i =>
match Nat.psub' i (size l) with
| none => nth l i
| some 0 => some x
| some (j + 1) => nth r j
