Изменения

Очевидно, что время работы приведённых алгоритмов пропорционально глубине дерева. Но т.к. математическое ожидание глубины рандомизированного бинарного дерева поиска есть <tex>O (\log n)</tex>, где <tex>n</tex> {{---}} число вершин в дереве<ref>Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stei, "Introduction to Algorithms", Second Edition {{---}} Chapter 12.4</ref>, то математическое ожидание времени работы поиска, вставки и удаления {{---}} также <tex>O (\log n)</tex>.