I am attempting to create an AVL tree data structure which can handle duplicate element keys. I have based my insertion algorithm on the following: https://www.sanfoundry.com/c-program-implement-avl-tree/#google_vignette.
However, my avl_tree_insert implementation cannot seem to handle certain duplicate keys, and I do not know why; basically, I have determined that the insertion works unless all the following conditions are met:
- The key being inserted already exists within the tree (I think this is correct?)
- The root node has null
leftandrightchild fields. - The root node is unbalanced (meaning a right rotation on the root node is required).
- The key being inserted is greater than or equal to the key to the left of the root (meaning a left rotation on the left node is required).
When the code checks for 4, a left rotation on the left node is invoked, which crashes because of a null pointer dereference (because ( *root ).left and ( *root ).right are null, see 2).
What confuses me is how to figure out how this tree state actually comes about, as well as how to fix it; for example, invoking avl_tree_insert with random keys usually works hundreds or thousands of times, for many different randomized states of the tree, but then suddenly the tree reaches a state like the one described above, and everything fails abruptly; this is what I do not know how to debug.
Below is some test driver code which will cause a crash using avl_tree_insert operations. I attempted to include all relevant parts of the tree data structure and insertion algorithm below, while omitting anything extraneous, and also included some debug print statements.
#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 )
// Print line binding.
// Requires compiler support for __VA_ARGS__.
#define println(formatting,...)
printf ( formatting"n" , ##__VA_ARGS__ )
// Evaluates to the maximum of two values.
// Requires compiler support for __typeof__.
#define MAX(a,b)
({
__typeof__ ( (a) ) a__ = (a);
__typeof__ ( (b) ) b__ = (b);
( a__ > b__ ) ? a__ : b__;
})
/** @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 )
{
println ( "avl_tree_create: Value of element_width argument must be non-zero." );
return false;
}
if ( !tree_ )
{
println ( "avl_tree_create: Missing argument: tree (output buffer)." );
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 MAX ( 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 ) println ( "Failure on append #%llu. No node to the right of %i." , 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 ) println ( "Failure on append #%llu. No node to the left of %i." , 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;
println ( "Keys match: %i, left key: %i, right key: %i"
, 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 ) println ("Rotate left required." );
( *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
);
}
// Alias for calling _avl_tree_insert on a literal value.
// Requires compiler support for __typeof__.
#define avl_tree_insert(tree,value,key)
do
{
__typeof__ ( (value) ) tmp = (value);
_avl_tree_insert ( (tree) , &tmp , (key) );
}
while ( 0 )
// 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.
}
println ( "Num elements in tree: %llu" , ( *tree ).element_count );
return 0;
}
Sample output:
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)