BST и RBT в худшем случае

Question

Сложность вставки RBT и BST равна O (logn).Я реализовал оба из них на Java и дал им много цифр и измерил время в секундах для анализа производительности. Представленные мной цифры показывают, что это O (n).Кто-нибудь может подумать об этом и прокомментировать, почему это так?

Answer 1

BST может иметь время вставки O (n), например, если вы вставляете элементы в возрастающем или убывающем порядке.
RBT также может иметь время вставки O (n), потому чтодереву требуется дополнительное время для восстановления баланса.
O (log n) - это средняя сложность для вставки (не в худшем случае).