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

Question

添加到二叉搜索树中的实现

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

树不平衡：

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

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

Answer 2

BST 中的 O(n) 情况发生在顶部有最小值或最大值时，有效地将 BST 变成链表。假设你添加元素为：1, 2, 3, 4, 5，生成你的 BST，由于每个元素只有一个 right child，这将是一个链表。添加 6 必须在每个节点上向下，遍历所有元素，因此使得 add O(n)

的渐近复杂性

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

Why is add in unbalanced Binary Search Tree O(n)?

java

algorithm

data-structures

binary-tree

binary-search-tree