Depurando uma operação errônea de 'inserção' de árvore AVL

Estou tentando criar uma estrutura de dados em árvore AVL que possa lidar com chaves de elementos duplicadas. Baseei meu algoritmo de inserção no seguinte: https://www.sanfoundry.com/c-program-implement-avl-tree/#google_vignette .

No entanto, minha avl_tree_insertimplementação parece não conseguir lidar com certas chaves duplicadas e não sei por quê; basicamente, determinei que a inserção funciona a menos que todas as condições a seguir sejam atendidas* (*Isso vem do meu próprio entendimento das verificações realizadas pelo meu código, combinadas com a saída de depuração. Pode ser uma lógica defeituosa, conforme observado por pelo menos um comentário. Leia o código para detalhes reais):

1. A chave inserida já existe na árvore.
2. O nó raiz possui campos nulos lefte rightfilhos.
3. O nó raiz está desequilibrado (o que significa que é necessária uma rotação para a direita no nó raiz).
4. A chave que está sendo inserida é maior ou igual à chave à esquerda da raiz (o que significa que é necessária uma rotação para a esquerda no nó esquerdo).

Quando o código verifica 4, uma rotação para a esquerda no nó esquerdo é invocada, que falha devido a uma desreferência de ponteiro nulo (porque ( *root ).lefte ( *root ).rightsão nulos, consulte 2).

O que me confunde é como descobrir como esse estado de árvore realmente surge e como corrigi-lo; por exemplo, invocar avl_tree_insertcom chaves aleatórias geralmente funciona centenas ou milhares de vezes, para muitos estados aleatórios diferentes da árvore, mas de repente a árvore atinge um estado como o descrito acima e tudo falha abruptamente; é isso que não sei depurar.

Abaixo está um código de driver de teste que causará uma falha ao usar avl_tree_insertoperações. Tentei incluir todas as partes relevantes da estrutura de dados em árvore e do algoritmo de inserção abaixo, omitindo qualquer coisa estranha, e também incluí algumas instruções de depuração de impressão.

#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;
}

Exemplo de saída (-1 indica chave nula):

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)