バイナリ検索ツリー削除（C++）

Question

C++でバイナリ検索ツリー削除アルゴリズムを実装する際に問題があります。私がルートを削除しようとすると、またはルートの子を直接、それは正しく動作します。しかし、より深いレベルでは機能しません（削除せずに同じツリーを出力するだけです）。私のコードで何が間違っていますか？

typedef struct Node { 
    int key; 
    Node *left = NULL; 
    Node *right = NULL; 
} Node; 

... 

/* 
* Delete <key> from BST rooted at <node> and return modified <node>. 
*/ 
Node* BST::pop(Node *node, int key) { 
    // If <node> is a null pointer, return. 
    // If <node> doesn't contain the key, traverse down the tree. 
    // If <node> contains the key, perform deletion. 
    if (node == NULL) { 
    } else if (key < node->key) { 
     node->left = pop(node->left, key); 
    } else if (key > root->key) { 
     node->right = pop(node->right, key); 
    } else { 
     // If <node> is a leaf, just delete it 
     if (node->left == NULL && node->right == NULL) { 
      delete node; // deallocate memory (note: node still points to a memory address!) 
      node = NULL; // node points to null 
     } 
     // If <node> has a single child, replace <node> with its child 
     else if (node->left == NULL && node->right != NULL) { 
      Node *tmp = node; 
      node = node->right; 
      delete tmp; 
      tmp = NULL; 
     } else if (node->right == NULL && node->left != NULL) { 
      Node *tmp = node; 
      node = node->left; 
      delete tmp; 
      tmp = NULL; 
     } else { 
      node->key = findMax(node->left); 
      node->left = pop(node->left, node->key); 
     } 
    } 
    return node; 
} 

int BST::findMax(Node *root) { 
    if (root->left == NULL && root->right == NULL) { 
     return root->key; 
    } else { 
     int max = root->key; 
     if (root->left != NULL) { 
      int leftMax = findMax(root->left); 
      if (leftMax > max) { 
       max = leftMax; 
      } 
     } 
     if (root->right != NULL) { 
      int rightMax = findMax(root->right); 
      if (rightMax > max) { 
       max = rightMax; 
      } 
     } 
     return max; 
    } 
} 

Answer 1

物事のカップル：

• 他の第二else if (key > node->key)

• あなたfindMax機能するかどう非常に複雑です。あるルートからのBSTの最大値は、右の子がなくなるまで右の子をたどるだけです（左のサブツリー内のものは現在評価中のキーより小さくなければならないので、leftMaxは決して> maxになることはありません）。したがって、それは限り、ツリーのバランスを維持する必要がありませんよう

  int BST::findMax(Node *root) { 
      int max = root->key; 
      while (root->right != NULL) { 
       root = root->right; 
       max = root->key; 
      } 
      return max; 
  } 
  

• をすることができ、あなたの一般的なただ一つだけ存在する場合に唯一の子供を交換し、葉の場合に除去するアルゴリズム、および場合2人の子供は、INORDERの隣人を見つけ交換し、そのノードを削除すると音れるべきである：BSTからノードを削除する（このリンクを見つけたかどうかわからないが、http://quiz.geeksforgeeks.org/binary-search-tree-set-2-delete/）