在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*logn/loglogn)
（4）提取的元素僅僅是一個遍歷：O(n)
因此：總的複雜性是O(n*logn/loglogn)

但排序是基於比較的算法Omega(nlogn)問題。矛盾。
結論：想要的f不存在。