在O（ln n）的有序序列中插入一个值

Question

我正在寻找python中的数据结构（在本例中由%分隔），它可以高效地（O（ln n）或更好地…）按顺序执行插入：

insert ( 6, % 3, 4, 9 %) ->  % 3, 4, 6, 9 %

对于list和np.ndarray，它是O（n）。dict或set无序。你知道吗

有没有一个内在的（或没有）方法来做到这一点？你知道吗

Answer 1

有多种数据结构，可以做你想做的，但我不认为有任何内置版本的。您可以使用skip list或自平衡二进制搜索树（例如red-black树，AVL tree）。有包含这些结构的边包。例如bintrees有avl和红黑树的实现。你知道吗

Answer 2

列表？你知道吗

^{}可以帮助您，至少在查找应该插入元素的位置时（O(log n)）：

import bisect
l = [3, 4, 9]
bisect.insort_left(l , 6)
print(l)
# [3, 4, 6, 9]

但从文件来看：

Keep in mind that the O(log n) search is dominated by the slow O(n) insertion step.

所以列表确实是个问题，而不是搜索本身。PythonTimeComplexity's table没有显示任何O（logn）插入的替代方法。你知道吗

二叉搜索树

从这个table可以看出，“二叉搜索树”有O（logn）用于访问、搜索和插入。还有其他一些结构也符合这一要求，但这可能是最为人所知的。你知道吗

这个answer (Implementing binary search tree)应该对你有帮助。例如：

r = Node(3)
binary_insert(r, Node(9))
binary_insert(r, Node(4))
binary_insert(r, Node(6))

in_order_print(r)
# 3
# 4
# 6
# 9