Изменения
→деревни >> деревья
===Вставка===
Рассмотрим рекурсивный алгоритм вставки ключа <tex>x</tex> в RBST, состоящее из <tex>n</tex> вершин. С вероятностью <tex>\dfrac{1}{n+1}</tex> вставим ключ в корень дерева (разделим дерево по данному ключу и подвесим получившиеся деревни деревья к новому корню), используя процедуру <tex>\mathrm{insertAtRoot}</tex>. С вероятностью <tex>1 - \dfrac{1}{n+1} = \dfrac{n}{n+1}</tex> вставим его в правое поддерево, если он больше корня, или в левое поддерево, если меньше.
Ниже приведён псевдокод процедуры вставки <tex>\mathrm{insert}</tex>, процедуры <tex>\mathrm{insertAtRoot}</tex>, а также процедуры <tex>\mathrm{split(k)}</tex>, разбивающей дерево на два поддерева, в одном из которых все ключи строго меньше <tex>k</tex>, а в другом больше, либо равны; приведена достаточно очевидная рекурсивная реализация (через <tex>Node</tex> обозначен тип вершины дерева, дерево представляется как указатель на корень).
