c++ - 红黑树插入 - 递归问题 - C++

Question

我有一个在红黑树中实现的递归插入方法。从递归调用返回后，我试图查看本地根的 child 是否为红色。但实际发生的是我正在检查树的根，而不是子树(最近插入发生的地方)。

这是我正在查看的位于 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，使其返回实际插入的节点。插入后您将能够轻松到达其父节点(假设该节点知道其父节点)。