Изменения

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