Извлеките узел из BST, сохранив поддельный узел. ⇐ C++
-
Гость
Извлеките узел из BST, сохранив поддельный узел.
I am writing a binary search tree (BST) with bidirectional iterator. To present .end() I have "fake node", that is the rightest son of the tree. I have problem with extract: my code works incorrectly whenever it gets to "fake node". I made a flag in the node, in order to mark it as fake one, but I just don't know, how to check this condition. I tried placing several "if" statements, but they didn't work. Can anybody help me with that?? Here is my code:
node_type* ExtractHelper(node_type* root, Key key) { if (root == nullptr) { return root; } else if (key < root->value) { root->left = ExtractHelper(root->left, key); } else if (key > root->value) { root->right = ExtractHelper(root->right, key); } else { if (root->left == nullptr) { value_type* temp = root->right; DeleteNode(root); if (temp) { temp->parent = root->parent; } return temp; } else if (root->right == nullptr) { value_type* temp = root->left; DeleteNode(root); if (temp) { temp->parent = root->parent; } return temp; } value_type* temp = GetLeftest(root->right); root->value = temp->value; root->right = ExtractHelper(root->right, temp->value); } return root; } i tried writing something like this:
if (temp) { temp->parent = cur->parent; temp->right = cur->right; cur->right->parent = temp } but this doesn't work. So I am actually waiting for suggestion of some modifications.
Источник: https://stackoverflow.com/questions/781 ... -fake-node
I am writing a binary search tree (BST) with bidirectional iterator. To present .end() I have "fake node", that is the rightest son of the tree. I have problem with extract: my code works incorrectly whenever it gets to "fake node". I made a flag in the node, in order to mark it as fake one, but I just don't know, how to check this condition. I tried placing several "if" statements, but they didn't work. Can anybody help me with that?? Here is my code:
node_type* ExtractHelper(node_type* root, Key key) { if (root == nullptr) { return root; } else if (key < root->value) { root->left = ExtractHelper(root->left, key); } else if (key > root->value) { root->right = ExtractHelper(root->right, key); } else { if (root->left == nullptr) { value_type* temp = root->right; DeleteNode(root); if (temp) { temp->parent = root->parent; } return temp; } else if (root->right == nullptr) { value_type* temp = root->left; DeleteNode(root); if (temp) { temp->parent = root->parent; } return temp; } value_type* temp = GetLeftest(root->right); root->value = temp->value; root->right = ExtractHelper(root->right, temp->value); } return root; } i tried writing something like this:
if (temp) { temp->parent = cur->parent; temp->right = cur->right; cur->right->parent = temp } but this doesn't work. So I am actually waiting for suggestion of some modifications.
Источник: https://stackoverflow.com/questions/781 ... -fake-node
