特定意图的二进制搜索树

Question

我们都知道有很多自平衡二分查找树(BST),最着名的是红黑和AVL.看看AA树和替罪羊树也许有用.

我想删除插入和搜索,就像任何其他BST一样.但是,删除给定范围内的所有值或删除整个子树是很常见的.所以:

1. 我想在O(log n)(平衡树)中插入,搜索,删除值.
2. 我想删除一个子树,保持整个树平衡,在O(log n)(最坏情况或摊销)
3. 在平衡树之前,删除行中的多个值可能很有用
4. 我通常会一次插入2个值,但这不是一个规则(如果有一个树数据结构考虑到这一点,只是一个提示)

是否有AVL或RB的变体可以帮助我吗？替罪羊树看起来更像这样,但也需要一些改变,任何有经验的人都可以分享一些东西？

更准确地说,哪种平衡程序和/或删除程序可以帮助我保持这项行动的时间效率？

Answer 1

可以在O(logn +对象num)中删除BST的值范围.

我所知道的最简单的方法是使用确定性跳过列表数据结构(您可能希望在继续之前阅读有关此数据结构的内容).在确定性跳过列表中,所有实际值都存储在底层,并且在它们的上层有指针.插入,搜索和删除都在O(logn)中完成.

范围删除操作可以根据以下算法完成:

• 找到范围中的第一个元素 - O(logn)
• 在链表中前进,并删除仍在范围内的所有元素.如果有指向上层指针的元素 - 也将它们删除,直到达到最高层(从链表中删除) - O(已删除对象的数量)
• 修复指针以适合确定性跳过列表(每个指针向上之间2-3个元素)

范围删除的总复杂度为O(logn +范围内的对象数).请注意,如果您选择使用随机跳过列表,则会获得相同的复杂性,但平均而言,并非最坏情况.优点是你不必修复上层指针来满足2-3的需求.

确定性跳过列表具有1-1到2-3树的映射,因此通过更多工作,上述过程也可以用于2-3树.