algorithm - 在两棵 AVL 树中划分一个 AVL，其中一棵包含低于 K 个元素，其余位于另一棵

Question

我正在寻找有关在两棵 AVL 树中分区（拆分）一棵 AVL 树的帮助，这样一棵树包含低于 KEY 的键，而另一个包含更大的键。来自它的那两棵树必须是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 .

如果您对这个问题有任何其他想法，我愿意接受建议，但如果它还可以，我更愿意先检查我的“算法”。