java - 为什么要添加不平衡的二叉搜索树 O(n)？

Question

这是从 BST Add 添加到二叉搜索树中的实现

private IntTreeNode add(IntTreeNode root, int value) {
        if (root == null) {
            root = new IntTreeNode(value);
        } else if (value <= root.data) {
            root.left = add(root.left, value);
        } else {
            root.right = add(root.right, value);
        }

        return root;
    }

我理解为什么这在 O(log n) 中运行。我是这样分析的。我们的树大小为 n。有多少次 2 的切割，或半切割，将使这棵树的大小减少到 1。所以我们有表达式 n(1/2)^x = 1，其中 1/2 代表每个半切割。为 x 解决这个问题，我们有 log2(x) 所以 logn 来自搜索。
这是来自 Heap 的讲座幻灯片讨论不平衡二进制搜索的运行时。

我的问题是，即使二叉搜索树是不平衡的，同样的策略对分析 add 的运行时间是否有效？你必须做多少削减。运行时间不会仍然是 O(log n)，而不是 O(n) 吗？如果是这样，有人可以展示为什么它会是 O(n) 的数学吗？

Answer 1

对于不平衡的树:

1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          ...

每次操作将树切成两半的直觉不再适用。这种不平衡树是不平衡二叉搜索树的最坏情况。要在列表底部搜索 10，您必须进行 10 操作，对树中的每个元素进行一次操作。这就是为什么不平衡二叉搜索树的搜索操作是 O(n) - 这个不平衡二叉搜索树相当于一个链表。每个操作不会切断树的一半——只是您已经访问过的一个节点。

这就是为什么特殊版本的二叉搜索树(例如红黑树和 AVL 树)很重要:它们维护的树足够平衡，因此所有操作(搜索、插入、删除)仍然 O(log n)。