A-sort如何运作？

Question

有人可以对A-sort(不是asort())的工作有所了解,它使用(a,b)树来排序部分排序的序列？

Answer 1

算法本身非常简单 - 基本上你在树中插入所有元素,然后遍历树以按顺序读取元素.

为了获得几乎已经排序的序列的更好性能,它使用以下修改:

1. 树必须是(a,b)树b>2a-1,具有O(1)分摊的插入重新平衡时间.
2. 该树包含指向同一级别(整个树)上节点的兄弟节点的链接

要利用O(1)插入时间,您只需快速找到下一个元素所属的位置,假设序列几乎已排序(因此它与前一个元素插入的位置相差不远).这大致如下:

• 你从插入的前一个元素开始
• 检查下一个元素是否不属于此节点或该节点的任何子树; 如果没有,你看看兄弟姐妹(让我们说新元素更小,所以它将是左兄弟)
• 如果兄弟姐妹的价值仍然太大,你上升一级并重复
• 如果新元素属于兄弟的子树,则从那里进行正常搜索
• 如果新元素属于兄弟节点和此节点之间,则转到最左边的子节点并重复搜索,直到找到正确的子树

这样,您可以逐步遍历a^k树的元素k,因此,您将花费O(log(distance(current, previous))时间为新元素找到合适的位置.考虑到摊销的O(1)再平衡,你可以比O(n log n)几乎排序的序列更好,同时保持O(n log n)最坏情况.