algorithm - 2-3 BST树中查找算法

Question

是否有一种算法可以使用给定的 2-3 tree T 和指向所述树中某个节点 v 的指针，算法可以更改节点 v 的键，因此 T 将保持合法的 2-3 树，在 O(logn/loglogn) 摊销效率中？

Answer 1

没有。
假设有可能，使用算法 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 *登录/登录登录)
(4) 提取元素只是遍历:O(n)
因此:总复杂度为O(n*logn/loglogn)

但是排序是基于比较的算法的 Omega(nlogn) 问题。矛盾。
结论:所需的f不存在。