Rav*_*pta 6 binary-tree binary-search-tree data-structures
我正在读二叉搜索树,并且在想我们为什么需要BST呢？据我所知,所有的事情也可以使用简单的排序数组来实现.例如 - 为了构建具有n个元素的BST,我们需要n*O(log n)时间,即O(nlog n)查找时间O(log n).但是这个东西也可以用数组来实现.我们可以有一个排序数组(需要O(nlog n)时间),查找时间也O(log n)就是二进制搜索算法.那为什么我们需要另一个数据结构呢？是否有其他使用/应用BST使它们如此特别？
--Ravi
whe*_*ies 10
如果您正在谈论一次写入,多次读取类型的交互,那么数组很棒.当你开始插入,交换和删除时,BST真正开始闪耀,而不是阵列.由于它们是基于节点的,而不是基于连续的内存块,因此将元素移动到集合中或从集合中移出的成本很快,同时仍然保持集合的排序特性.
可以想象一下,链接列表与数组之间的插入差异.这是过于简单化,但它突出了我上面提到的优势的一个方面.
小智 7
想象一下,你有一个拥有一百万个元素的数组.
您想在位置5插入元素.
所以你插入数组的末尾然后排序.
假设阵列已满; 这是O(nlog n),即1,000,000*6 = 6,000,000次操作.
想象一下,你有一棵平衡的树.
那是O(log n),加上一点平衡= 6 +一点,称之为10次操作.
所以,你刚刚花了6,000,000个操作来排序你的阵列.然后,您想要找到该元素.你是做什么？二进制搜索 - O(log n) - 这与您在树中搜索时要执行的操作完全相同!
现在想象你想要分配-another-元素.
你的阵列已满!你是做什么？用n个额外的元素重新分配数组并memcpy该批次？你真的想记住4mbytes吗？
在树中,您只需添加另一个元素......