data-structures - BST 和 RBT 插入更坏的情况

Question

RBT 和 BST 的插入复杂度为 O(logn)。我已经用 Java 实现了它们，并给了它们很多数字，并以秒为单位测量了时间来分析性能。我绘制的数字似乎表明它是 O(n)。任何人都可以考虑一下并评论为什么会这样？

Answer 1

BST 可能有 O (n) 的插入时间，例如，如果您以递增或递减的顺序插入元素。
RBT 也可能有 O (n) 的插入时间，因为树需要额外的时间来重新平衡。
O (log n) 是插入的平均复杂度（不是最坏情况）。