我必须实现一种特定类型的BST：将具有多个交互的节点保持在上部。特别是：1每次在树中插入或搜索K键时，都会通过一系列称为CLIMB的上升操作将其移动到根(保持BST的特性(。2如果在FST中搜索K元素并在给定节点N中找到，则对其应用CLIMB操作。如果元素K不存在，则对搜索结束的叶应用该操作。3如果某个节点被删除，则CLIMB操作将应用于被删除节点的父节点。
我几天来一直在努力实现它，但我没有能力。我想到了一个算法：用新根替换旧根，如果旧根较小，则将其钩到新根的左侧；如果旧根较大，则将旧根钩到右侧。此外，如果它是旧根小于新根，则在旧根的右分支上查找新根的第一个最大元素，并通过将其作为新根右分支来移动它。如果它更大，反之亦然。
但我不能执行。有人能帮我吗？我确信，对于一个专家来说，这是一件微不足道的事，但对我来说，这却是一场噩梦。
这不是我问的第一个问题，在过去的一个问题中，我也输入了代码，但即使投票结果是肯定的，也没有人能回答我，现在提交的代码我意识到这不是正确的方式。
我没有'；我不知道如何移动树的部分
帮助。
假设我们正在调用climb(n)。从树中删除以n为根的子树，并将其作为新根放置。不幸的是，我们不能把整棵老树放在n的任何一个子树上，并就此结束。
我们唯一可以确定的是，如果[l, u]是存储在根为n的子树中的值的范围，那么该子树之外的所有节点都在该范围之外。事实上，这适用于所有子树。然而，你的方法的关键也在于：你假设"老树"中的所有值都位于该范围的一侧，而事实上它们可以围绕该范围排列。即，想象在根(7(的右子项的左子项上调用climb：
5
3 8
... 7 9
... 6 ...
无论你把5放在节点7的哪一边，它都是错误的。5或8必须放错地方。
利用这个事实，我们可以从parent(n)回溯，直到到达旧根，并使用标准BST插入：将沿着路径遇到的所有子树放置在新树中
climb(n):
// get the new-root and remove it from the tree rooted at old_root
old_root = root(n)
new_root = n
remove_node(old_root, n)
// iterate ancestors of n up to root
node = parent(n)
while node != nil do
// remove current ancestor (node) from the original tree
next = parent(node)
remove_child(parent(node), node)
// insert node into the new tree (all nodes that are still appended remain children of node)
insert_node(new_root, node)
node = next
done
return new_root
由于上述关于范围的规则，这将在每次迭代后产生有效的BST。然而，在每次迭代中，都会添加一个新的子树，作为根在new_root的树的最右边叶子的最右边的子树或最左边叶子的最左边的子树，因此重新平衡根在left_child(new_root)和right_child(new_root)的子树可能是个好主意，因为树很快就会变得相当不平衡。