Отладка ошибочной операции «вставки» дерева AVL

Я пытаюсь создать древовидную структуру данных AVL, которая может обрабатывать повторяющиеся ключи элементов. Я основал свой алгоритм вставки на следующем: https://www.sanfoundry.com/c-program-implement-avl-tree/#google_vignette.

Однако моя реализация avl_tree_insert, похоже, не может обрабатывать некоторые повторяющиеся ключи, и я не знаю, почему; по сути, я определил, что вставка работает, если не выполняются все следующие условия* (*Это исходит из моего собственного понимания проверок, выполняемых моим кодом, в сочетании с выводом отладки. Это может быть ошибочная логика, как отметил по крайней мере один комментарий, чтобы узнать подробности).

1. Вставляемый ключ уже существует в дереве.
2. Корневой узел имеет нулевые дочерние поля left и right.
3. Корневой узел несбалансирован (это означает, что корневому узлу необходимо вращение вправо).
4. Вставляемый ключ больше или равен ключу слева от корня (это означает, что требуется вращение влево на левом узле).

Когда код проверяет наличие 4, вызывается вращение влево на левом узле, что приводит к сбою из-за разыменования нулевого указателя (поскольку ( *root ).left и ( *root ).right имеют значение null, см. 2).

Что меня смущает, так это то, как понять, как на самом деле возникает это состояние дерева, а также как его исправить; например, вызов avl_tree_insert со случайными ключами обычно работает сотни или тысячи раз для множества различных рандомизированных состояний дерева, но затем внезапно дерево достигает состояния, подобного описанному выше, и все резко выходит из строя; это то, что я не знаю, как отладить.

Ниже приведен код тестового драйвера, который приведет к сбою при использовании операций avl_tree_insert. Я попытался включить все соответствующие части древовидной структуры данных и алгоритм вставки ниже, опуская при этом все постороннее, а также включил некоторые операторы отладочной печати.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

// Adjust for your hardware.
typedef unsigned long long int  u64;
typedef signed long long int    i64;
typedef signed short int        i16;

/** @brief Type and instance definitions for generic boolean type. */
typedef _Bool bool;
#define true    ( ( bool ) 1 )
#define false   ( ( bool ) 0 )

/** @brief Type definition for an AVL tree node. */
typedef struct node_t
{
    i64             key;
    u64             depth;

    struct node_t*  left;
    struct node_t*  right;

    void*           content;
}
node_t;

/** @brief Type definition for an AVL tree. */
typedef struct
{
    u64         element_width;
    u64         element_count;

    u64         node_count;
    node_t*     root;
}
avl_tree_t;

// Global op count.
static u64 op_count = 0;

// Global debug flag.
static bool debug_flag;

bool
avl_tree_create
(   u64             element_width
,   avl_tree_t**    tree_
)
{
    if ( !element_width )
    {
        printf ( "avl_tree_create: Value of element_width argument must be non-zero.\n" );
        return false;
    }
    if ( !tree_ )
    {
        printf ( "avl_tree_create: Missing argument: tree (output buffer).\n" );
        return false;
    }

    avl_tree_t* tree = malloc ( sizeof ( avl_tree_t ) );
    tree->element_width = element_width;
    tree->element_count = 0;
    tree->node_count = 0;
    tree->root = 0;
    
    *tree_ = tree;
    return true;
}

u64
avl_tree_recompute_depth
(   node_t* root
)
{
    u64 left;
    u64 right;
    
    if ( !root )
    {
        return 0;
    }

    if ( !root->left )
    {
        left = 0;
    }
    else
    {
        left = 1 + root->left->depth;
    }

    if ( !root->right )
    {
        right = 0;
    }
    else
    {
        right = 1 + root->right->depth;
    }

    return ( left > right ) ? left : right;
}

i64
avl_tree_balance_factor
(   node_t* root
)
{
    u64 left;
    u64 right;
    
    if ( !root )
    {
        return 0;
    }

    if ( !root->left )
    {
        left = 0;
    }
    else
    {
        left = 1 + root->left->depth;
    }

    if ( !root->right )
    {
        right = 0;
    }
    else
    {
        right = 1 + root->right->depth;
    }

    return left - right;
}

node_t*
avl_tree_rotate_left
(   node_t* root
)
{
    // Rotate left.
    node_t* right = root->right;
    if ( !right ) printf ( "Failure on append #%llu. No node to the right of %i.\n" , op_count , root->key );
    root->right = right->left;
    right->left = root;

    // Update depth.
    root->depth = avl_tree_recompute_depth ( root );
    right->depth = avl_tree_recompute_depth ( right );

    return right;
}

node_t*
avl_tree_rotate_right
(   node_t* root
)
{
    // Rotate right.
    node_t* left = root->left;
    if ( !left ) printf ( "Failure on append #%llu. No node to the left of %i.\n" , op_count , root->key );
    root->left = left->right;
    left->right = root;

    // Update depth.
    root->depth = avl_tree_recompute_depth ( root );
    left->depth = avl_tree_recompute_depth ( left );

    return left;
}

node_t*
_avl_tree_insert
(   avl_tree_t* tree
,   node_t*     root
,   const void* src
,   const i64   key
)
{
    // CASE: End of branch.
    if ( !root )
    {
        // Initialize a new element node.
        node_t* node = malloc ( sizeof ( node_t ) + tree->element_width );
        memset ( node , 0 , sizeof ( node_t ) );
        ( *node ).key = key;
        ( *node ).content = ( void* )( ( ( u64 ) node ) + sizeof ( node_t ) );
        memcpy ( node->content , src , tree->element_width );

        // Insert the node into the tree.
        root = node;

        // Update state.
        tree->node_count += 1;
        tree->element_count += 1;
    }

    // CASE: Key > root key (recurse right).
    else if ( key > root->key )
    {
        root->right = _avl_tree_insert ( tree
                                       , root->right
                                       , src
                                       , key
                                       );

        // Rebalance? Y/N
        if ( avl_tree_balance_factor ( root ) < -1 )
        {
            if ( key <= root->right->key )
            {
                root->right = avl_tree_rotate_right ( root->right );
            }
            root = avl_tree_rotate_left ( root );
        }
    }

    // CASE: Key <= root key (recurse left).
    else
    {
        if ( key == root->key )
        {
            debug_flag = true;
            printf ( "Keys match: %i, left key: %i, right key: %i\n"
                   , key
                   , ( root->left ? root->left->key : -1 )
                   , ( root->right ? root->right->key : -1 )
                   );
        }
        root->left = _avl_tree_insert ( tree
                                      , root->left
                                      , src
                                      , key
                                      );

        // Rebalance? Y/N
        if ( avl_tree_balance_factor ( root ) > 1 )
        {
            if ( key >= root->left->key )
            {
                if ( debug_flag ) printf ("Rotate left required.\n" );
                root->left = avl_tree_rotate_left ( root->left );
            }
            root = avl_tree_rotate_right ( root );
        }
    }
    
    root->depth = avl_tree_recompute_depth ( root );
    return root;
}

void
avl_tree_insert
(   avl_tree_t* tree
,   const void* src
,   const i64   key
)
{
    debug_flag = false;
    tree->root = _avl_tree_insert ( tree
                                  , tree->root
                                  , src
                                  , key
                                  );
}

// Test driver.
int
main
( void )
{
    srand ( time ( 0 ) );

    avl_tree_t* tree;
    avl_tree_create ( sizeof ( i16 ) , &tree );

    for ( u64 i = 0; i < 1000000; ++i )
    {
        i16 key;
        do
        {
            key = rand ();
        }
        while ( key == -1 );
        op_count += 1;
        avl_tree_insert ( tree , &key , key ); // Value can just be same as key here.
    }
    printf ( "Num elements in tree: %llu\n" , tree->element_count );

    return 0;
}

Пример вывода (-1 указывает на нулевой ключ):

Keys match: 2214, left key: -1, right key: -1
Keys match: 5145, left key: -1, right key: -1
Keys match: 7141, left key: -1, right key: -1
Keys match: 16453, left key: -1, right key: -1
Keys match: 15365, left key: -1, right key: -1
Keys match: 22779, left key: 22764, right key: 22816
Keys match: 11855, left key: -1, right key: -1
Rotate left required.
Failure on append #857. No node to the right of 11855.
// (OS crashes the program)