2-3 BST木のアルゴリズムを見つける

Question

与えられた2-3 tree Tとその木のあるノードvを指すポインタがあると、アルゴリズムはノードの鍵を変えることができるので、 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）このようにしてそれをn回呼び出し、fO(logn/loglogn)され活性化されO(n*logn/loglogn)
（4）要素を抽出するだけトラバースある：従ってO(n)
。総複雑度はO(n*logn/loglogn)

ですが、ソートは比較ベースのアルゴリズムではOmega(nlogn)の問題です。矛盾。
結論：希望fは存在しません。