ang*_*rge 5 language-agnostic algorithm binary-tree skip-lists data-structures
不确定问题应该在这里还是在程序员(或其他一些SE网站)上,但我对平衡二叉树和可索引的跳过列表之间的相关差异感到好奇.问题出现在这个问题的背景下.来自维基百科:
跳过列表是一种概率数据结构,似乎可能取代平衡树作为许多应用程序选择的实现方法.跳过列表算法与平衡树具有相同的渐近预期时间界限,并且更简单,更快速并且使用更少的空间.
跳过列表的空间要求是否取决于层次结构的深度？并且二叉树不是更容易使用,至少对于搜索(在平衡BST中授予,插入和删除可能是棘手的)？跳过列表还有其他优点/缺点吗？
(问题的某些部分(易用性,简单性等)有点主观,我会在本文末尾回答它们.)
我们来看看空间使用情况.首先,假设您有一个包含n个节点的二叉搜索树.所需的总空间使用量是多少？好吧,每个节点都存储一些数据和两个指针.您可能还需要一些信息来维护余额信息.这意味着总空间使用量是
n*(2*sizeof(指针)+ sizeof(数据)+ sizeof(余额信息))
所以让我们考虑一个等效的跳转列表.你是绝对正确的,由skiplist使用的内存的实际数量取决于节点的高度,但我们可以谈论的预期由skiplist使用的空间量.通常,您从跳过列表中选择一个节点的高度,从1开始,然后重复翻转一个公平的硬币,只要翻转头部就会增加高度,并在翻转尾部时立即停止.鉴于此设置,跳过列表中预期的指针数量是多少？
从概率论的一个有趣的结果是,如果你有一系列以概率p独立事件,则需要大约1/P试验(在期望)之前将要发生的事件.在我们的硬币翻转示例中,我们正在翻转硬币直到它出现尾巴,并且因为硬币是一个公平的硬币(头部概率为50%),所以在我们翻尾之前所需的预期试验次数是2次.由于最后一次翻转结束了增长,节点在跳过列表中增长的预期次数是1.因此,在期望中,我们期望平均节点中只有两个指针 - 一个初始指针和一个添加指针.这意味着预期的总空间使用量是
n*(2*sizeof(指针)+ sizeof(数据))
将其与平衡二叉搜索树中节点的大小进行比较.如果存储余额信息需要非零空间,则跳过列表确实会使用(预期)比平衡BST更少的内存.请注意,许多类型的平衡BST(例如treap)需要大量的余额信息,而其他(红/黑树,AVL树)具有平衡信息但可以在其指针的低位中隐藏该信息,而其他(splay trees)根本没有任何余额信息.因此,这不是一个有保证的胜利,但在许多情况下它将使用空间.
至于你关于简单,轻松等的其他问题:这真的取决于.我个人发现在BST中查找元素的代码比在skiplist中进行查找的代码要容易得多.然而,平衡BST中的旋转逻辑通常比跳过列表中的插入/删除逻辑复杂得多; 尝试看看你是否可以在没有咨询参考的情况下在红/黑树中发出所有可能的旋转情况,或者看看你是否能够记住一个展开树中的所有zig/zag与zag/zag情况.从这个意义上说,记住用于插入或删除跳过列表的逻辑可能会更容易一些.
希望这可以帮助!