为什么在不平衡的二叉搜索树中添加O（n）？

Question

这是BST Add中二进制搜索树中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;
    }

我的问题是，即使二元搜索树是不平衡的，同样的策略是否也能用于分析add的运行时？你要做多少次切割。运行时不是仍然是O（logn），而不是O（n）吗？如果是这样的话，有人能证明为什么它会是O（n）吗？

Answer 1

BST中的< code>O(n)情况发生在顶部有最小值或最大值时，实际上将BST变成了一个链表。假设您将元素添加为:< code>1，2，3，4，5，生成BST，由于每个元素只有一个< code>right子元素，所以它将是一个链表。添加6必须在每个节点上向下，通过所有元素，因此使得add O(n)的渐近复杂度

Answer 2

对于不平衡的树：

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

你的直觉是每次操作都要把树砍成两半，这已经不适用了。这种不平衡树是不平衡二叉搜索树的最坏情况。要在列表底部搜索10，您必须对树中的每个元素执行10操作。这就是为什么非平衡二叉搜索树的搜索操作是O（n）-这个非平衡二元搜索树等价于链表。每一次操作都不会砍掉树的一半——只会砍掉您已经访问过的一个节点。

这就是为什么特殊版本的二分搜索法树，如红黑树和AVL树很重要:它们保持树的平衡，使得所有的操作——搜索、插入、删除——仍然是O(log n)。