Почему мои функции баланса AVL теряют данные?

Question

Всякий раз, когда число узлов в AVL проходит 8 узлов, и алгоритм пытается перебалансировать, при вставке 9-го узла большинство узлов в дереве теряются

Я реализовал дерево AVL в c, и функция вставки проверяет баланс деревьев после каждой вставки. Функция контрольного баланса пытается перебалансировать дерево при вызове (при необходимости) и делает это вращением (как стандартно для деревьев AVL), либо вращением влево, либо вращением вправо, либо комбинацией обоих. Однако всякий раз, когда количество узлов превышает 8 (хотя это, вероятно, произвольно), некоторые из узлов теряются. После каждого поворота обнаруживается родитель предыдущего корня поддерева, и его левый или правый указатель соответственно изменяются, например: если у меня есть дерево, подобное

        97                                        97                 
       /                                          /
     96                                         95
    /          Right                           /  \
   95          ====>                         94    96
  /            Rotate on 96
 94    

96 был предыдущим родителем поддерева, но после поворота он равен 95, поэтому «левый» указатель 97 с должен измениться с 96 на 95.

Итак, процесс вставки: значение места => проверить баланс => повернуть (при необходимости)

функция значения места:

void place_value(node_t* root, node_t* in) {
    if(root->val > in->val) {
        if(root->left == NULL)
            root->left = in;
        else
            place_value(root->left, in);
    }
    else if(root->val < in->val) {
        if(root->right == NULL)
            root->right = in;
        else
            place_value(root->right, in);
    } else {
        /*kill the node*/
    }
    if(check_balance(root) == 1) {
        fflush(stdout);
    }
}

функция проверки баланса:

int check_balance(node_t* root) {
    int flag = 0;

    if((height(root->left, 0)- height(root->right, 0))>1) {
        if((height(root->left->left, 0)- height(root->left->right, 0))>0) {
            right_rotate(root);
            flag = 1;
        } else {
            left_right(root);
            flag = 1;
        }
    }

    if((height(root->left, 0)- height(root->right, 0))<-1) {
        if((height(root->right->left, 0)- height(root->right->right, 0))<0)    {
            left_rotate(root);
            flag = 1;
        } else {
            right_left(root);
            flag = 1;
        }
    }

    return flag;

}

левый и правый поворот более или менее следуют одному и тому же шаблону:

void left_rotate(node_t* root) {
    if(root == NULL || root->right == NULL)
        return;
    node_t* parent = find_parent(root->val, root->bst_l->Head);
    node_t* right_node = root->right;
    root->right = right_node->left;
    right_node->left = root;
    if(parent == NULL) {
        root->bst_l->Head = right_node;
        return;
    }
    if(root->val > parent->val)
        parent->right = right_node;
    else
        parent->left = right_node;
}

Пример комбинированного вращения:

void left_right(node_t* root) {
    left_rotate(root->left);
    right_rotate(root);
}

Итак, я делал предварительный обход BST после каждой вставки, и вот как выглядело это дерево:

100 
100 99  
99  98  100 
98  97  99  100 
98  97  96  99  100 
98  96  95  97  99  100 
96  95  94  99  98  97  100 
98  96  94  93  95  97  99  100 
94  96  97  

Вставка 92 сломала дерево и потеряла некоторые данные

перед потерей данных, обход предзаказа показывает, что дерево выглядит так:

                         98
                        /  \
                      96    99
                     /  \    \
                   94    97  100
                  /  \
                93    95

, который сбалансирован. После вставки 92 я ожидаю, что дерево будет выглядеть так:

                         ---98---
                        /        \
                      95         99
                     /  \          \
                   93    96        100
                  /  \     \
                92    94    97

Но вместо этого это выглядит так:

                         94
                           \
                            96
                              \
                              97

Сначала я думал, что операционная система произвольно очищала память, хотя она и не использовалась, но это не имеет смысла, потому что процесс, которому принадлежит память, все еще выполняется. Другие возможные причины перерывов:

Функция поиска родительского элемента:

node_t* find_parent(int value, node_t* start) {
    int val = value;
    if(start == NULL)
        return NULL;

    if(val == start->val)
        return NULL;

    if(val < start->val) {
        if(start->left == NULL)
            return NULL;
        else if(start->left->val == val)
            return start;
        else
            find_parent(value, start->left);
    } else if(val > start->val){
        if(start->right == NULL)
            return NULL;
        else if(start->right->val == val)
            return start;
        else
            find_parent(value, start->right);
    } else {  }

    return NULL;
}

Я попытался пошагово пройти по коду, но не смог точно указать, что именно вызвало проблему, хотя я обнаружил, что BST обрывается, когда алгоритм пытается повернуть налево-направо на 96 с BST в этом состоянии:

                         98
                        /  \
                      96    99
                     /  \    \
                   94    97  100
                  /  \
                93    95

при вводе 92.