为什么要添加不平衡的二叉搜索树 O(n)?
Why is add in unbalanced Binary Search Tree O(n)?
这是从 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) 的数学吗?
树不平衡:
1
\
2
\
3
\
4
\
5
\
...
您每次操作都将树切成两半的直觉不再适用。这种不平衡树是不平衡二叉搜索树的最坏情况。要在列表底部搜索 10
,您必须进行 10
操作,对树中的每个元素进行一次操作。这就是为什么不平衡二叉搜索树的搜索操作是 O(n) - 这个不平衡二叉搜索树相当于一个链表。每个操作不会砍掉一半的树——只是你已经访问过的一个节点。
这就是为什么特殊版本的二叉搜索树(例如红黑树和 AVL 树)很重要:它们维护的树足够平衡,因此所有操作(搜索、插入、删除)仍然 O(log n).
BST 中的 O(n)
情况发生在顶部有最小值或最大值时,有效地将 BST 变成链表。假设你添加元素为:1, 2, 3, 4, 5
,生成你的 BST,由于每个元素只有一个 right child
,这将是一个链表。添加 6 必须在每个节点上向下,遍历所有元素,因此使得 add O(n)
的渐近复杂性
这是从 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) 的数学吗?
树不平衡:
1
\
2
\
3
\
4
\
5
\
...
您每次操作都将树切成两半的直觉不再适用。这种不平衡树是不平衡二叉搜索树的最坏情况。要在列表底部搜索 10
,您必须进行 10
操作,对树中的每个元素进行一次操作。这就是为什么不平衡二叉搜索树的搜索操作是 O(n) - 这个不平衡二叉搜索树相当于一个链表。每个操作不会砍掉一半的树——只是你已经访问过的一个节点。
这就是为什么特殊版本的二叉搜索树(例如红黑树和 AVL 树)很重要:它们维护的树足够平衡,因此所有操作(搜索、插入、删除)仍然 O(log n).
BST 中的 O(n)
情况发生在顶部有最小值或最大值时,有效地将 BST 变成链表。假设你添加元素为:1, 2, 3, 4, 5
,生成你的 BST,由于每个元素只有一个 right child
,这将是一个链表。添加 6 必须在每个节点上向下,遍历所有元素,因此使得 add O(n)