紅黑樹 - 旋轉方法實現 - C++

我正在C++中實現紅黑樹，但我遇到了旋轉方法的麻煩。插入方法工作得很好，沒有任何平衡，但只要我嘗試旋轉，我的樹就會丟失信息。我的猜測是我沒有以正確的方式設置節點的指針，但我不完全明白這裏出了什麼問題。紅黑樹 - 旋轉方法實現 - C++

這裏是我的旋轉正確的方法：

void RedBlackTree::rotateRight(RedBlackNode *localRoot) { 
cout << "rotateRight - local root " << localRoot->data << endl; 
RedBlackNode *temp = localRoot->left; 
localRoot->left = temp->right; 
temp->right = localRoot; 
localRoot = temp; 
}

正在發生的事情的一個例子是我插入C，B，和。樹最初看起來像這樣：

c 
/
    b 
/
a

旋轉後，樹只會打印出根節點c。

關於可能會發生什麼的任何想法？謝謝！

來源

2012-12-12 Jordan

我會懷疑使用調試器可能會告訴你發生了什麼...... – Caribou

你需要通過引用傳遞'localRoot'指針，而不是通過值...最後一行沒有任何作用！ –

@Caribou我知道visual studio有一個運行時錯誤調試器。不幸的是，我無法使用視覺。知道具體哪些會有所幫助？我只是使用文本編輯器和命令行。 – Jordan

根據代碼段很難區分，但是localRoot是一個本地指針，當你離開函數時它的變化被遺忘了。如果要在調用函數的上下文中更改它，則要麼將其傳遞爲RedBlackNode*&，要麼將結果作爲結果返回。

來源

2012-12-12 22:16:28

我做了這個改變，但它仍然在做同樣的事情。通過引用來修復它是有道理的，但它仍然存在相同的問題。 – Jordan

你沒有告訴你打電話給你的功能。因此，不可能知道發生了什麼問題，但我猜想'localRoot'也來自調用函數中的輔助指針。但是，您需要更新指針來自的位置，例如樹的根（如果這三個節點是整個try）或父節點的相應指針（如果這三個節點是某個節點的子樹掛起）。 –

是的，你是對的。我在插入方法中調用了rotate，其中root被作爲指針傳遞。修復和工作。感謝您的巨大幫助！ – Jordan

紅黑樹 - 旋轉方法實現 - C++

回答

相關問題