我一直在研究二叉搜索树与数组,并且很好奇我的假设是否正确。所以我会解释一下我的理解,如果你这么认为,请纠正我。我们还假设我们想要创建一个数据结构,它可以:
问题: 不过,唯一的区别是,对于数组,插入更耗时 - 即 O(n) > O(log(n))。除此之外,甚至可以在 O(1) 时间内找到特定元素,并且找到最大/最小元素。排序数组的插入时间是我们决定使用二叉搜索树的原因吗?O(n) 真的对我们有影响吗,所以我们改用 O(log(n)) 的二叉搜索树?
我一直在研究二叉搜索树与数组,并且很好奇我的假设是否正确。所以我会解释一下我的理解,如果你这么认为,请纠正我。我们还假设我们想要创建一个数据结构,它可以:
问题: 不过,唯一的区别是,对于数组,插入更耗时 - 即 O(n) > O(log(n))。除此之外,甚至可以在 O(1) 时间内找到特定元素,并且找到最大/最小元素。排序数组的插入时间是我们决定使用二叉搜索树的原因吗?O(n) 真的对我们有影响吗,所以我们改用 O(log(n)) 的二叉搜索树?
在树表示中,没有什么可以阻止您存储指向
min
和max
元素的指针,因此它可能O(1)
取决于实现。数据集越大,差异越大,但
O(log(N))
通常更1
接近于N
:N = 1
vslog(N) = 1
N = 10
vslog(N) = 4
N = 1000
vslog(N) = 10
N = 1000000
vslog(N) = 20
N = 10000000000
vslog(N) = 30