为什么不平衡二叉搜索树O（n）被添加？(Why is add in unbalanced Binar

这是附加在二叉搜索树从实现BST添加

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，我们的log 2（X），所以LOGN来自于搜索。
下面是演讲幻灯片堆 ，讨论运行时间不平衡的二进制搜索。

我的问题是，即使二叉搜索树是不平衡的，不会用于分析添加的运行时同样的策略的工作？ 你有多少削减已经做出。 不会运行时仍然是O（log n）的，而不是为O（n）？ 如果是这样，有人可以证明的，为什么它会为O（n）的数学吗？

Answer 1:

随着不平衡的树：

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

您与每个操作切割树中一半的直觉不再适用。 这种不平衡的树是一种不平衡的二叉搜索树的最坏情况。 要搜索10在列表的底部，你必须做出10的操作，一个是树中的每个元素。 这就是为什么不平衡二叉搜索树的搜索操作是O（n） -这种不平衡的二叉搜索树就相当于一个链表。 每个操作不砍下一半 - 只是你访问过的一个节点。

这就是为什么二叉搜索树的专门版本，如红黑树和AVL树是很重要的：他们认为，是平衡的不够好，使所有操作树-查找，插入，删除-仍然是O（log n）的。

Answer 2:

在O(n) ，当你有最低或顶部最大，有效地将您的BST到链表的BST情况发生。 假设你添加的元素为： 1, 2, 3, 4, 5 ，生成您的BST，这将是一个链表，由于只具有每一个元素right child 。 添加6将不得不降权的每一个节点上，通过所有的元素去，因此使得添加的渐近复杂度O(n)

文章来源: Why is add in unbalanced Binary Search Tree O(n)?