有人可以解释我这种递归吗？

-1

我想了解递归。我理解愚蠢的数学例子，但我不知道它的本质。有人可以解释我这种递归吗？

我有1个例，我不明白，它是如何工作的：

TREE-ROOT-INSERT(x, z) 

if x = NIL 
    return z 
if z.key < x.key 
    x.left = TREE-ROOT-INSERT(x.left, z) 
    return RIGHT-ROTATE(x) 
else 
    x.right = TREE-ROOT-INSERT(x.right, z) 
    return LEFT-ROTATE(x)

我知道这个代码做什么：首先在BST插入一个节点，然后使新节点成为了每一次旋转根。

但在我脑海中分析代码，我想它插入节点，它必须去，然后只是1时间它旋转树。

树每次都可以旋转吗？

来源

2016-06-08 ymmayg

这可能是一个更好的例子http://stackoverflow.com/questions/6323656/multiple-avl-tree-rotation?rq=1 –

此外这个例子*插入15 *表示可能需要多个轮换https://jriera.webs.ull.es/Docencia/avl_handout.pdf –

您需要在树的每个级别的递归调用中保持您的位置。当你第一次打return RIGHT-ROTATE（或左）时，你还没有完全完成;你把树作为ROTATE函数的结果，并将其放置在递归调用TREE-ROOT-INSERT的代码中堆栈中较高一级的代码中。然后再次旋转，然后将当前的树返回到堆栈中上一级，直到您击中树的原始根。

来源

2016-06-08 22:15:17

理解递归的重要之处在于将递归函数想象成一个抽象黑盒子。换句话说，在阅读或推理递归函数时，您应该关注当前的迭代，将递归函数的调用看作原子（假设它可以做它应该做的事情），看看它是如何实现的其结果可以用来解决当前的迭代。

你已经知道你的TREE-ROOT-INSERT(x, z)合同：

插入ž成X为根的二叉搜索树，转换树，以使z将成为新的根。

让我们来看看这个片断：

if z.key < x.key 
     x.left = TREE-ROOT-INSERT(x.left, z) 
     return RIGHT-ROTATE(x)

这是说z小于X如此这般的左子树（因为它是BST）。 TREE-ROOT-INSERT被再次调用，但我们不会追踪它。相反，我们假设它可以完成它所要做的事情：它会将z插入以x.left为根的树，并使z成为新的根。然后你会得到波纹管结构的树：

 
    x 
    /\ 
    z ... 
/\ 
... ...

同样，你不知道究竟怎么叫TREE-ROOT-INSERT(x.left, z)将让你的z扎根子树。在这一刻你不在乎，因为真正重要的部分是：如何让这棵树扎根于z？答案是RIGHT-ROTATE(x)

但在我的脑海分析代码我想它插入节点，在它去，然后就1次旋转时的树。

树每次都可以旋转吗？

如果我正确理解你，你仍然在想如何以非递归的方式解决问题。确实，您可以使用标准BST插入过程将z插入以x为根的BST。这将使z处于正确的位置。但是要将z从该位置移到根部，则需要多于1次旋转。

在递归版本中，在得到一个以z为根的子树后，需要旋转以将z带到根。但是为了从原始的x.left rooted子树中获取z-rooted子树，还需要旋转。旋转被称为多次，但在不同的子树上。

来源

2016-08-16 17:51:58 Xinchao

有人可以解释我这种递归吗？

回答

相关问题