AVL tree (C++), программа продолжает сбой

Question

Я работаю над упражнением в обработке дерева AVL. Отладчик не показывает ошибок. Я запускал программу, и она должна выводить выходной текстовый файл. Однако программа вылетает каждый раз.

#include <stdio.h> 
#include <assert.h> 
#include <algorithm> 
#include <vector> 
using namespace std; 

struct node 
{ 
    int key; 
    int height; 
    node *left, *right; 
    node(int k) 
    { 
     key = k; 
     height = 1; 
     left = right = 0; 
    } 
}; 


void pre_order(node* root) 
{ 
    if(root == 0) return; 
    printf("%d", root->key); 
    printf(" "); 
    pre_order(root->left); 
    pre_order(root->right); 
} 

void in_order(node* root) 
{ 
    in_order(root->left); 
    printf("%d", root->key); 
    printf(" "); 
    in_order(root->right); 
} 

int height(node* r) 
{ 
    return r ? r->height : 0; 
} 

void update_height(node* root) 
{ 
    if(root == 0) return; 
    int hl = height(root->left), hr = height(root->right); 
    root->height = std::max(hl, hr) + 1; 
} 


node* right_rotate(node* ref_root) 
{ 
    assert(ref_root && ref_root->left); 
    node *a = ref_root, *b = ref_root->left; 
    a->left = b->right; 
    b->right = a; 

    update_height(a); 
    update_height(b); 
    return b; 
} 

node* left_rotate(node* ref_root) 
{ 
    assert(ref_root && ref_root->right); 
    node *c = ref_root, *d = ref_root->right; 
    c->right = d->left; 
    d->left = c; 
    update_height(c); 
    update_height(d); 
    return d; 
} 


node* maintain(node* ref_root) 
{ 
    if(ref_root == 0) return ref_root; 
    update_height(ref_root); 
    node* ret = ref_root; 
    if(height(ref_root->left) > height(ref_root->right) + 1) 
    { 
     node* p = ref_root->left; 
     if(height(p->left) < height(p->right)) 
      ref_root->left = left_rotate(p); 
     ret = right_rotate(ref_root); 
    } 
    else if(height(ref_root->right) > height(ref_root->left) + 1) 
    { 
     node* p = ref_root->right; 
     if(height(p->right) < height(p->left)){ 
      ref_root->right = right_rotate(p); 
     } 
     ret = left_rotate(ref_root); 
    } 
    return ret; 
} 


node* insert_key(int key, node* ref_root) 
{ 
    if(ref_root == 0) 
    { 
     return ref_root = new node(key); 
    } 
    if(key < ref_root->key){ 
     node* child = insert_key(key, ref_root->left); 
     ref_root->left = child; 
     }  
    else if(key > ref_root->key){ 
     node* child = insert_key(key, ref_root->right); 
     ref_root->right = child; 
    } 
    else 
     assert(0); 

    return maintain(ref_root); 
} 

vector<node*> minimum(node* T) { 
    vector<node*> x; 
    node* y = T; 
    while (y->left != NULL) { 
     x.push_back(y->left); 
    } 
    return x; 
} 

node* delete_key(int key, node* ref_root) 
{ 
    if(key < ref_root->key){ 
     node* child = delete_key(key, ref_root->left); 
     ref_root->left = child; 
     } 
    else if(key > ref_root->key){ 
     node* child = delete_key(key, ref_root->right); 
     ref_root->right = child; 
     } 
    else 
    { 
     if(ref_root->left && ref_root->right) 
     { 
      vector <node*> y = minimum(ref_root->right); 
      node* successor = y.back(); 
      node* sParent = y[y.size()-2]; 
      ref_root->key = successor->key; 
      sParent->left = successor->right; 
     } 
     else 
     { 
      if(ref_root->left != NULL){ 
       ref_root = ref_root->left; 
      } 
      else if(ref_root->right != NULL){ 
       ref_root = ref_root->right; 
      } 
     } 
    } 

    return maintain(ref_root); 
} 

int main() 
{ 
    node *root = 0; 
    char op[10] = ""; 
    int k; 
    while(true) 
    { 
     scanf("%s", op); 
     if(op[0] == 'E') break; 
     switch(op[0]) 
     { 
     case 'A': scanf("%d", &k); root = insert_key(k, root); break; //Insert 
     case 'D': scanf("%d", &k); root = delete_key(k, root); break;//Delete 
     case 'P': pre_order(root); printf("\n"); break;//preorder 
     case 'I': in_order(root); printf("\n"); break;//inorder 
     default: assert(0); 
     } 
    } 
    return 0; 
} 

Answer 1

В функции in_order нет подтверждения, что корень не равен NULL.