紅黑樹插入 - 遞歸問題 - C++

Question

我有一個在紅黑樹中實現的遞歸插入方法。從遞歸調用返回後，我試圖查看本地根的孩子是否是紅色的。但實際發生的是我正在檢查樹的根，而不是子樹（最近插入的地方）。

這裏的代碼，我看該段會在insertNode方法內：

this->insertNode(root->right, value); 
if(root->right->is_red) { 
    cout << "color again & " << root->data << endl; 
    root->right->is_red = false; 
    root->is_red = true; 
    this->rotateLeft(root); 
} 

我怎麼能在這裏最後插入發生的子樹的根操作？在我從遞歸調用回來之前，是否需要確保完成此操作？

Answer 1

修改insertNode，使其返回實際插入的節點。在插入後，您將能夠輕鬆地獲得其父項（假設該節點知道其父項）。