问2-3BST树的查找算法

EN

不是的。

假设这是可能的，使用算法f，我们将展示我们可以对具有O(n*logn/loglogn)时间复杂度的数组进行排序。

sort array A of length n:
(1) Create an  2-3 tree of size n, with no importance to keys. let it be T.
(2) store all pointers to nodes in T in a second array B.
(3) for each i from 0 to n:
   (3.1) f(B[i],A[i]) //modify the tree: pointer: B[i] new value: A[i]
(4) extract elements from T back to A inorder.

正确性：

每次激活f后，树都是合法的。在T的所有元素和A的所有元素上激活f后，树是合法的，并包含所有元素。因此，从A中提取元素，我们将得到排序后的数组。

复杂性：

(1)创建一棵树无关紧要我们把哪个键放入O(n)我们可以在所有元素中放入0，这并不重要

(2)迭代T并创建B是O(n)

(3)激活f为O(logn/loglogn)，因此n次调用为O(n*logn/loglogn)

(4)提取元素只是一次遍历：O(n)

因此:总复杂度为O(n*logn/loglogn)

但是，对于基于比较的算法，排序是一个Omega(nlogn)问题。矛盾。

结论：所需的f不存在。