数组和二叉搜索树在效率上有什么区别？
我想知道什么是最好的：数组或二叉搜索树（插入、删除、查找最大值和最小值）以及如何改进它们？
I want know what is the best : Array OR Binary search tree in ( insert , delete , find max and min ) and how can I Improve both of them ?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
数组允许随机访问其中的每个元素。因此，您可以在
O(1)中插入、删除和查找特定元素，并在O(n)中进行最大/最小、删除。 [您也可以将 max/min 设置为O(1)并删除O(n)]。如果你保持数组排序，它将导致插入/删除的时间为O(n)，但你将获得O(logn)查找和O (1)最小/最大。BST 按定义排序，对于常规的[不平衡] BST，您会得到
O(n)最坏情况行为。对于平衡 BST，您可以获得O(logn)插入/删除/查找。您可以通过任何方式获得O(1)min/max 两者。数组通常也可以更快地迭代[假设迭代顺序并不重要]，因为你可以获得更好的< a href="http://en.wikipedia.org/wiki/Cache" rel="noreferrer">缓存性能。此外，与 BST（本质上具有无限大小）不同，数组在数组已满时需要重新分配和复制数据。
改进 BST 可以通过使其平衡来完成 - 就像AVL 或 红黑树。
哪个更好？这取决于应用程序。通常，当您计划插入数据并保持其排序时，BST 会是首选。如果随机访问或迭代是主要目的：您通常使用数组。
An array allows random access to each element in it. so you get insert, delete and look for a specific element in
O(1), and max/min, delete inO(n). [you can also make max/minO(1)and deleteO(n)instead]. If you are keeping your array sorted, it will cause insert/delete to beO(n), but you will gainO(logn)find, andO(1)min/max.A BST is sorted by definition, and for a regular [unbalanced] BST, you get
O(n)worst case behavior. For balanced BST, you getO(logn)insert/delete/find. You can getO(1)min/max any how for both.Arrays are also usually faster to iterate [assuming order of iteration is not important] since you gain better cache performance. Also, unlike BST - which has unbounded size by nature, an array requires reallocation and copying the data when your array is full.
Improving a BST can be done by making it balanced - like AVL or red-black-trees.
Which is better? it depends on the application. Usually when you are planning to insert data and keep it sorted, BST will be prefered. If random access or iteration is the main purpose: you usually use an array.
数组和二叉搜索树的性能比较：
*假设二分搜索**需要额外的指向 min 和 max 的指针，否则为 O(log n)Performance comparison of Arrays and Binary search trees:
*assuming binary search**requires extra pointers to min and max, otherwise it's O(log n)