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

Question

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

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

0

data-structures time-complexity binary-search-tree red-black-tree red-black-tree-insertion

Источник

user7566984 13 май '18 в 12:24

1 ответ

Другие вопросы по тегам data-structures time-complexity binary-search-tree red-black-tree red-black-tree-insertion

user1556820 13 май '18 в 12:29 2018-05-13 12:29 · Answer 1 · 2018-05-13 12:29

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