1 つの AVL ツリーを 2 つの AVL ツリーに分割 (分割) して、1 つの AVL ツリーに KEY よりも低いキーが含まれ、もう 1 つの AVL ツリーにそれより大きなキーが含まれるようにする方法について、ヘルプを探しています。そこから派生する 2 本の木は AVL でなければなりません (したがって、高さは完全にバランスが取れている必要があります)。
私の考え:
1. If KEY is inside tree T, find it. If not - insert it.
NODE_K is pointer to node with KEY.
2. Using rotations lift up NODE_K up to the root
cleaning after myself so that both subtrees of NODE_K are AVL.
3. Once NODE_K reaches root, in left subtree there is a TREE
with all smaller nodes that is stil AVL, and same thing is in right subtree,
only elements are bigger.
時間はツリーの高さである O(log n) です (ノードを持ち上げるだけで、サブツリーのバランスを毎回復元するために一定の回転を使用するため)。
私の懸念は、それがサブツリーのバランスを適切に保ち、高さが異なる問題がどんどん大きくなり続け、ルートに到達すると、高さの差<= 1よりも大きくなる可能性があるかどうかはわかりません。 .
その問題について他のアイデアがある場合は、提案を受け付けていますが、問題がなければ「アルゴリズム」を最初に確認したいと思います。