二叉搜索树 vs 排序双向链表

Question

我想知道，在使用二分查找对排序的链表进行插入和搜索时，它们之间的性能是否有差异。在哪些情况下它们表现不同，或者说为了哪些目的，列表将无法使用或相反。

- dhblah

Answer 1

您无法对链表（单向或双向）进行二分查找，因为没有办法在中间位置上停留，除非从一端遍历了一半的列表。

可能有一种多级跳跃列表可以实现这一点，但我认为这只是用更复杂的结构模拟二叉树。

按顺序排列的链表搜索、插入和删除通常是O(n)（实际插入/删除本身是O(1)，但您仍然需要首先查找插入或删除点）。

或者，平衡二叉树的搜索、插入和删除都是O(log n)（这些操作均与树的高度成比例）。

- paxdiablo

---

所以，如果我理解你的意思正确的话，对于链表来说，在执行二分查找时，每次移动到当前中间元素都会增加开销，是吗？因此，二分查找的复杂度将是logn * logn而不是logn，对吗？ - dhblah

@dhblah，是的，至少开销位是正确的。它是否为(log N)^2，我不确定，但肯定比log N更糟糕。 - paxdiablo

@dhblah 如果您当前的“感兴趣区间”长度为n，则移动到中间的成本为O(n)。随着二分查找的进行，每次迭代中感兴趣的区间长度减半，因此所有迭代的总和仍然相当于O(n)。但是，常数比线性搜索要差得多。简而言之，我无法想出任何理由，为什么对于链表来说，二分查找比线性查找更可取。 - Erik P.