最有效的数据结构：快速排序插入，最接近的值搜索

Question

基本上：

• 快速，排序插入件。
• 返回物品在数据结构中未找到的位置。

一个二进制搜索的数组满足了我的第二个要求，但它仍然非常缓慢地插入。什么解决方案最适合？

Answer 1

Red-black trees和skip lists符合您的要求，等等。对于C++中的示例，请查看std :: set，std :: map等及其lower_/upper_bound和equal_range方法。

Answer 2

许多风格的搜索树符合您的要求。我会使用2-3树，或者如果我感到懒惰，也许会用树枝。

Answer 3

二叉搜索树。