有人可以解釋我這種遞歸嗎？

-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

有人可以解釋我這種遞歸嗎？

回答

相關問題