struct node *delete(struct node *root, int key)
{
struct node *remove_node;
if (root == NULL){
return root;
}
if ( key < root->key) {
root->left = delete(root->left, key);
} else if ( key > root->key) {
root->right = delete(root->right,key);
} else {
if ((root->left == NULL) && (root->right != NULL)){
remove_node = root->right;
*root = *remove_node;
deletetree(remove_node); // this is for free-ing the memory
} else if ((root->right == NULL) && (root->left != NULL)){
remove_node = root->left;
*root = *remove_node;
deletetree(remove_node);
} else if ((root->right == NULL) && (root->left == NULL)){
remove_node = root;
root = NULL;
} else {
remove_node = successor(root);
root->key = remove_node->key;
root->right = delete(root->right, remove_node->key);
}
}
if (root == NULL) {
return root;
if (balance_factor(root) == 2){
if (balance_factor(root->left) == -1) {
return single_right_rotation(root);
} else if (balance_factor(root->left) == 1) {
return double_left_rotation(root);
}
}
if (balance_factor(root) == -2) {
if (balance_factor(root->right) == -1) {
return single_left_rotation(root);
}
else if (balance_factor(root->right) == 1) {
return double_right_rotation(root);
}
}
}
return root;
}
これがAVLツリーの要素を削除するための私のコードです。すべてが正常に機能しているように見えます。ノードnに子がなく、1つの子と2つの子がある場合は、すべて処理されます。しかし、奇妙な理由で、ツリーのバランスが取れておらず、そのコードブロックに到達していません。
うまくいけば、誰かがコードのデバッグを手伝ってくれるといいのですが、エラーが「正確に」どこから来ているのかわからないからです。
前もって感謝します
PS：後継関数は、削除するノードの右側のツリーの最小要素を返すだけで、deletetreeはメモリ割り当ての解放を処理します。また、挿入機能で完全に機能したため、回転が機能することは100％です。