【C++】ポインタのポインタに間接参照演算子をつけたものへの代入がうまく行かない

実現しようとしていること

AOJ ALDS1_8_Cの二分探索木を以下のように実装しようとしましたが、void binaryTree::erase(int) 内の、子を持たない節点 **ppV の削除のところで、メモリ解放後に親節点からの参照を切りたいです。

わからないこと

ppV は削除する節点への親節点からのポインタ(pParent->left || pParent->right)のポインタなので、v に nullptr を代入すればいいと考えて実装してみたのですが、親節点に反映されなくて困っています。
私の認識では、ポインタはある値を格納している変数のメモリのアドレスで、それにをつけたものへの代入は変数そのものへの代入と同じ動作をするものと思っていたのですが、違うのでしょうか？
ご教授願います。

該当のソースコード

c++
1#include <iostream>
2
3using namespace std;
4
5struct node {
6    int key;
7    node *parent;
8    node *left;
9    node *right;
10};
11
12void walkInOrder(node *cur) {
13    if (cur == nullptr) return;
14    walkInOrder(cur->left);
15    printf(" %d", cur->key);
16    walkInOrder(cur->right);
17}
18
19void walkPreOrder(node *cur) {
20    if (cur == nullptr) return;
21    printf(" %d", cur->key);
22    walkPreOrder(cur->left);
23    walkPreOrder(cur->right);
24}
25
26struct binaryTree {
27    node *root;
28
29    binaryTree() {
30        root = nullptr;
31    }
32
33    void insert(int x) {
34        node *pParent = nullptr;
35        node **v = &root;
36        node *nodeX = (node *) malloc(sizeof(node));
37        nodeX->key = x;
38        nodeX->left = nodeX->right = nullptr;
39        while (*v != nullptr) {
40            pParent = *v;
41            v = &((*v)->key <= x ? (*v)->right : (*v)->left);
42        }
43        nodeX->parent = pParent;
44        *v = nodeX;
45    }
46
47    void erase(int x) {
48        node *pParent = nullptr;
49        node **ppV = &root;
50        while (*ppV != nullptr && (*ppV)->key != x) {
51            pParent = *ppV;
52            ppV = &((*ppV)->key <= x ? (*ppV)->right : (*ppV)->left);
53        }
54        if ((*ppV) == nullptr) return;
55        if ((*ppV)->left != nullptr && (*ppV)->right != nullptr) {
56            pParent = *ppV;
57            node *nextNode = pParent->right;
58            while (nextNode->left != nullptr) {
59                pParent = nextNode;
60                nextNode = pParent->left;
61            }
62            (*ppV)->key = nextNode->key;
63            ppV = &nextNode;
64        }
65        if ((*ppV)->left == nullptr && (*ppV)->right == nullptr) {
66            free((*ppV));
67            *ppV = nullptr;
68        } else {
69            node *vChild = (*ppV)->left != nullptr ? (*ppV)->left : (*ppV)->right;
70            free((*ppV));
71            *ppV = vChild;
72            vChild->parent = pParent;
73        }
74    }
75
76    void find(int x) {
77        node *v = root;
78        while (v != nullptr) {
79            if (x < v->key) v = v->left;
80            else if (v->key < x) v = v->right;
81            else break;
82        }
83        printf("%s\n", v == nullptr ? "no" : "yes");
84    }
85
86    void print() {
87        walkInOrder(root);
88        printf("\n");
89        walkPreOrder(root);
90        printf("\n");
91    }
92};
93
94int main() {
95    int n, x;
96    string op;
97    binaryTree tree;
98    cin >> n;
99    for (int i = 0; i < n; ++i) {
100        cin >> op;
101        if (op[0] == 'p') {
102            tree.print();
103        } else {
104            cin >> x;
105            if (op[0] == 'i') tree.insert(x);
106            else if (op[0] == 'f') tree.find(x);
107            else tree.erase(x);
108        }
109    }
110    return 0;
111}

行動規範の内容に同意します

回答1件

ベストアンサー

問題はその上の

ppV = &nextNode;

ではないかと思います。
これによって、*ppv=nullptrはnextNode=nullptrとなります。

投稿2020/03/04 22:20

asm

総合スコア15149

退会済みユーザー

2020/03/04 22:58 編集

削除する節点に２つの子がある時に、次節点の値をコピーして、代わりに次節点の方を削除するというアルゴリズムが http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_8_C&lang=ja で指定されているので、そのように実装していますが問題でしょうか？デバッガーも使いながら、各変数の値の遷移に異常がないことは確かめているのでないとは思いますが、