c++ - 红黑树插入 - 递归问题 - 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，使其返回实际插入的节点。插入后，您将能够轻松到达其父节点（假设该节点知道其父节点）。