Source code
All we need is… An AVL tree! Ok, may be not, or not always at least. 🙂 But many times we do need self balancing binary search tree, and C source code, never to be found. Now you have it. The project include the files:
src/binary_tree.h src/binary_tree.c src/avl_tree.h src/avl_tree.c src/unit_test.c converter.sh Makefile test_avl_tree.sh
The basic binary tree can be used as stand alone complete implementation, with functions to Insert, Delete, Search, FindMin, FindMax, Print in different orders. Very nice indeed. 🙂 I tried to make this module convenient for more advanced uses, so functions for allocation/free/print are actually callback functions given to the tree in initialization function. Also this module contain built in support export for “dot” files graphical visualization of the tree. I use Graphviz on Ubuntu, it works fine most of the time.
Example of graph produced by this method: 
Tree module also initialized with “FixBalance” function, that may be NULL, or be actual balancing function. In this project the “FixBalance” is AVL balancing algorithm we all love and cherish. How to use it? Compile the code, in terminal: “make”. Then run the executable: test_avl_tree, it creates AVL tree, add 256 nodes to it, with ids 0-255, then it delete the nodes using pseudo-random function. For each 16 deletions the test creates a dot graph of the tree before and after deletion. Also you may use test_avl_tree.sh Linux script, but you need to install dot from Graphviz, and use some image viewer( I use “eog” – GNOME image viewer ). The source code of the project:
binary_tree.h:
#ifndef _binary_tree_h
#define _binary_tree_h
#include <stdint.h>
#define MAX(x, y) (((x) > (y)) ? (x) : (y))
typedef enum
{
TREE_MESSAGE_FAILED_ALLOCATE_NODE = 1,
TREE_MESSAGE_ID_NOT_FOUND = 2,
}Messages_T;
typedef struct
{
int info;
}Data_T;
typedef struct TreeNode
{
struct TreeNode* left;
struct TreeNode* right;
int height;
int id;
Data_T data;
} TreeNode_T;
typedef TreeNode_T* ( AllocateNode_T ) ( void );
typedef void ( FreeNode_T ) ( TreeNode_T* );
typedef void ( PrintMessage_T ) ( Messages_T );
typedef TreeNode_T* ( TREE_FixBalance_T ) ( TreeNode_T* currentNode );
typedef struct
{
TreeNode_T* root;
PrintMessage_T* printMessage;
AllocateNode_T* allocateNode;
FreeNode_T* freeNode;
TREE_FixBalance_T* fixBalance;
int size;
}TREE_t;
typedef void ( TREE_Init_T ) ( TREE_t* tree, PrintMessage_T* printMessage, AllocateNode_T* allocateNode, FreeNode_T* freeNode, TREE_FixBalance_T* fixBalance );
typedef void ( TREE_InsertNode_T ) ( TREE_t* tree, int id, Data_T* data );
typedef void ( TREE_DeleteNode_T ) ( TREE_t* tree, int id );
typedef TreeNode_T* ( TREE_FindNode_T ) ( TREE_t* tree, int id );
typedef int ( TREE_Height_T ) ( TREE_t* tree );
typedef void ( TREE_Delete_T ) ( TREE_t* tree );
typedef void ( TREE_DotGraphPrint_T ) ( char* string );
typedef void ( TREE_DotGraphPrintInit_T ) ( void );
typedef void ( TREE_DotGraphPrintDest_T ) ( void );
TreeNode_T* TREE_FindMinNode ( TreeNode_T* node );
TreeNode_T* TREE_FindMaxNode ( TreeNode_T* node );
void TREE_PrintInorder ( TreeNode_T* node );
void TREE_PrintPreorder ( TreeNode_T* node );
void TREE_PrintPostorder ( TreeNode_T* node );
void TREE_Init ( TREE_t* tree, PrintMessage_T* printMessage, AllocateNode_T* allocateNode, FreeNode_T* freeNode, TREE_FixBalance_T* fixBalance );
void TREE_DeleteSubTree ( TREE_t* tree, TreeNode_T* currentNode );
void TREE_Delete ( TREE_t* tree );
void TREE_InsertNode ( TREE_t* tree, int id, Data_T* data );
void TREE_DeleteNode ( TREE_t* tree, int id );
TreeNode_T* TREE_FindNode ( TREE_t* tree, int id );
int TREE_Height ( TREE_t* tree );
void TREE_CreateDotGraph ( TreeNode_T* node, TREE_DotGraphPrintInit_T* dotGraphInit, TREE_DotGraphPrintDest_T* dotGraphDest, TREE_DotGraphPrint_T* dotGraphPrint );
int TREE_GetSize ( TREE_t* tree );
void TREE_GetSonsHeight ( TreeNode_T* currentNode, int* heightLeft, int* heightRight );
void TREE_UpdateHeight ( TreeNode_T* currentNode );
#endif
binary_tree.c:
#include "binary_tree.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
void TREE_GetSonsHeight( TreeNode_T* currentNode, int* heightLeft, int* heightRight )
{
if ( NULL != currentNode->left )
{
*heightLeft = currentNode->left->height;
}
if ( NULL != currentNode->right )
{
*heightRight = currentNode->right->height;
}
}
void TREE_UpdateHeight( TreeNode_T* currentNode )
{
if ( NULL != currentNode )
{
int heightLeft = 0;
int heighRight = 0;
TREE_GetSonsHeight( currentNode, &heightLeft, &heighRight );
currentNode->height = 1 + MAX( heightLeft, heighRight );
}
}
TreeNode_T* TREE_FindMinNode( TreeNode_T* node )
{
if ( node == NULL )
{
return NULL;
}
else
{
if ( node->left == NULL )
{
return node;
}
else
{
return TREE_FindMinNode( node->left );
}
}
}
TreeNode_T* TREE_FindMaxNode( TreeNode_T* node )
{
if ( node == NULL )
{
return NULL;
}
else
{
if ( node->right == NULL )
{
return node;
}
else
{
return TREE_FindMaxNode( node->right );
}
}
}
void TREE_PrintInorder(TreeNode_T *node)
{
if(node==NULL)
{
return;
}
TREE_PrintInorder(node->left);
printf( "%d[h:%d] ", node->id ,node->height );
TREE_PrintInorder(node->right);
}
void TREE_PrintPreorder(TreeNode_T *node)
{
if(node==NULL)
{
return;
}
printf( "%d[h:%d] ", node->id ,node->height );
TREE_PrintPreorder(node->left);
TREE_PrintPreorder(node->right);
}
void TREE_PrintPostorder(TreeNode_T *node)
{
if(node==NULL)
{
return;
}
TREE_PrintPostorder(node->left);
TREE_PrintPostorder(node->right);
printf( "%d[h:%d] ", node->id ,node->height );
}
void TREE_Init( TREE_t* tree, PrintMessage_T* printMessage, AllocateNode_T* allocateNode, FreeNode_T* freeNode, TREE_FixBalance_T* fixBalance )
{
tree->root = NULL;
tree->printMessage = printMessage;
tree->allocateNode = allocateNode;
tree->freeNode = freeNode;
tree->fixBalance = fixBalance;
tree->size = 0;
}
void TREE_DeleteSubTree( TREE_t* tree, TreeNode_T* currentNode )
{
if ( NULL != currentNode )
{
TREE_DeleteSubTree( tree, currentNode->left );
TREE_DeleteSubTree( tree, currentNode->right );
tree->freeNode(currentNode);
tree->size--;
}
}
void TREE_Delete( TREE_t* tree )
{
TREE_DeleteSubTree( tree, tree->root );
tree->root = NULL;
}
static TreeNode_T* tree_InsertNodeHelper( TREE_t* tree, TreeNode_T* currentNode, int id, Data_T* data )
{
if( NULL == currentNode )
{
TreeNode_T *tempNode;
tempNode = tree->allocateNode();
tree->size++;
if ( NULL != tempNode)
{
tempNode->id = id;
memcpy( &tempNode->data, data, sizeof(tempNode->id) );
tempNode->height = 1; // leaf has height 1, to be more convenient for TREE_ tree purposes
tempNode->left = NULL;
tempNode->right = NULL;
}
else
{
tree->printMessage( TREE_MESSAGE_FAILED_ALLOCATE_NODE );
}
return tempNode;
}
else
{
currentNode->height++;
if( id >= ( currentNode->id ) )
{
currentNode->right = tree_InsertNodeHelper( tree, currentNode->right, id, data );
}
else if( id < ( currentNode->id ) )
{
currentNode->left = tree_InsertNodeHelper( tree, currentNode->left, id, data );
}
TREE_UpdateHeight( currentNode );
if ( NULL != tree->fixBalance )
{
currentNode = tree->fixBalance( currentNode );
}
return currentNode;
}
}
void TREE_InsertNode( TREE_t* tree, int id, Data_T* data )
{
tree->root = tree_InsertNodeHelper( tree, tree->root, id, data );
}
static TreeNode_T* tree_DeleteNodeHelper( TREE_t* tree, TreeNode_T* currentNode, int id )
{
if( NULL == currentNode )
{
tree->printMessage( TREE_MESSAGE_ID_NOT_FOUND );
}
else if( id < currentNode->id )
{
currentNode->left = tree_DeleteNodeHelper( tree, currentNode->left, id );
}
else if( id > currentNode->id )
{
currentNode->right = tree_DeleteNodeHelper( tree, currentNode->right, id );
}
else
{
TreeNode_T *tempNode;
if( currentNode->right && currentNode->left )
{
tempNode = TREE_FindMinNode( currentNode->right );
currentNode->id = tempNode->id;
currentNode->right = tree_DeleteNodeHelper( tree, currentNode->right, tempNode->id );
}
else
{
tempNode = currentNode;
if( currentNode->left == NULL )
{
currentNode = currentNode->right;
}
else if( currentNode->right == NULL )
{
currentNode = currentNode->left;
}
tree->freeNode( tempNode );
tree->size--;
}
}
TREE_UpdateHeight( currentNode );
if ( NULL != tree->fixBalance )
{
currentNode = tree->fixBalance( currentNode );
}
return currentNode;
}
void TREE_DeleteNode ( TREE_t* tree, int id )
{
tree->root = tree_DeleteNodeHelper( tree, tree->root, id );
}
static TreeNode_T* tree_FindNodeHelper( TREE_t* tree, TreeNode_T* currentNode, int id )
{
if( NULL == currentNode )
{
return NULL;
}
if( id > currentNode->id)
{
return tree_FindNodeHelper( tree, currentNode->right, id );
}
else if( id < currentNode->id )
{
return tree_FindNodeHelper( tree, currentNode->left, id );
}
else
{
return currentNode;
}
}
TreeNode_T* TREE_FindNode ( TREE_t* tree, int id )
{
return tree_FindNodeHelper( tree, tree->root, id );
}
int TREE_Height( TREE_t* tree ) // leaf height is 1
{
if ( tree->root == NULL )
{
return 0;
}
else
{
return tree->root->height;
}
}
static void TREE_CreateDotGraphHelper( TreeNode_T* node, TREE_DotGraphPrint_T* dotGraphPrint )
{
static char stringToPrintBuffer[64];
static char* stringToPrint = (char*)&stringToPrintBuffer;
if ( NULL != node )
{
sprintf( stringToPrint, "n%d [label=\"id: %d, h: %d\"];\n", node->id, node->id, node->height );
dotGraphPrint( stringToPrint );
if ( NULL != node->left )
{
TREE_CreateDotGraphHelper( node->left, dotGraphPrint );
sprintf( stringToPrint, "n%d -> n%d[label=\"L\"];\n", node->id, node->left->id);
dotGraphPrint( stringToPrint );
}
else
{
sprintf( stringToPrint, "nll%d [label=\"null\",shape=\"box\"];\n", node->id );
dotGraphPrint( stringToPrint );
sprintf( stringToPrint, "n%d -> nll%d[label=\"L\"];\n", node->id, node->id );
dotGraphPrint( stringToPrint );
}
if ( NULL != node->right )
{
TREE_CreateDotGraphHelper( node->right, dotGraphPrint );
sprintf( stringToPrint, "n%d -> n%d[label=\"R\"];\n", node->id, node->right->id );
dotGraphPrint( stringToPrint );
}
else
{
sprintf( stringToPrint, "nlr%d [label=\"null\",shape=\"box\"];\n", node->id );
dotGraphPrint( stringToPrint );
sprintf( stringToPrint, "n%d -> nlr%d[label=\"R\"];\n", node->id, node->id );
dotGraphPrint( stringToPrint );
}
}
}
void TREE_CreateDotGraph( TreeNode_T* node, TREE_DotGraphPrintInit_T* dotGraphInit, TREE_DotGraphPrintDest_T* dotGraphDest, TREE_DotGraphPrint_T* dotGraphPrint )
{
//char graph;
dotGraphInit();
dotGraphPrint("digraph tree {\n");
TREE_CreateDotGraphHelper( node, dotGraphPrint );
dotGraphPrint("}");
dotGraphDest();
}
int TREE_GetSize( TREE_t* tree )
{
return tree->size;
}
avl_tree.h:
#ifndef __avl_tree_h__ #define __avl_tree_h__ #include "binary_tree.h" void AVL_Init ( TREE_t* tree, PrintMessage_T* printMessage, AllocateNode_T* allocateNode, FreeNode_T* freeNode ); void AVL_InsertNode ( TREE_t* tree, int id, Data_T* data ); void AVL_DeleteNode ( TREE_t* tree, int id ); TreeNode_T* AVL_FindNode ( TREE_t* tree, int id ); #endif /* AVL_TREE_H_ */
avl_tree.c:
#include <stdint.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include "avl_tree.h"
TreeNode_T* avl_RotateRight( TreeNode_T* currentNode )
{
/*
+---+ +---+
|K1 | |K2 |
+---+ +---+
+ + + +
+---+ + + +---+
|K2 | + + + |K1 |
+---+ + + + + +---+
+ + | | + + + +
+ + | | | | + +
+ + + + | | | | + + + +
+ + + + | C | Rotate Right | | + + + +
| | | | | | -----------> | | | | | |
| | | | | | | A | | | | |
-----| |---| B |---+++++------------------| |---| B |---| C |----------
| | | | | | | | | |
| A | | | | | | | | |
-----| |---+++++--------------------------+++++---+++++---+++++----------
| |
| |
-----+++++-----------------------------------------------------------------
*/
TreeNode_T* K1 = currentNode;
TreeNode_T* K2 = currentNode->left;
TreeNode_T* A = K2->left;
TreeNode_T* B = K2->right;
TreeNode_T* C = K1->right;
K2->left = A;
K2->right = K1;
K1->left = B;
K1->right = C;
TREE_UpdateHeight( K1 );
TREE_UpdateHeight( K2 );
return K2;
}
TreeNode_T* avl_RotateLeft( TreeNode_T* currentNode )
{
/*
+---+ +---+
|K1 | |K2 |
+---+ +---+
+ + + +
+ +---+ +---+ +
+ + |K2 | |K1 | +
+ + +---+ +---+ + +
| | + + + + + +
| | + + + + | |
| | + + + + + + + + | |
| A | + + + + Rotate Left + + + + | |
| | | | | | ----------> | | | | | |
| | | | | | | | | | | C |
-----+++++--| B |---| |-----------------| A |---| B |--| |-------------
| | | | | | | | | |
| | | C | | | | | | |
----------- +++++---| |-----------------+++++---+++++--+++++-------------
| |
| |
--------------------+++++--------------------------------------------------
*/
TreeNode_T* K1 = currentNode;
TreeNode_T* K2 = currentNode->right;
TreeNode_T* A = K1->left;
TreeNode_T* B = K2->left;
TreeNode_T* C = K2->right;
K2->left = K1;
K2->right = C;
K1->left = A;
K1->right = B;
TREE_UpdateHeight( K1 );
TREE_UpdateHeight( K2 );
return K2;
}
TreeNode_T* avl_RotateLeftThenRight( TreeNode_T* currentNode )
{
/*
+---+
+---+ +---+ |K2 |
|K3 | |K3 | +---+
+---+ +---+ + +
+ + + + + +
+---+ + +---+ + +---+ +---+
|K1 | + |K2 | + |K1 | |K3 |
+---+ + + +---+ + + +---+ +---+
+ + + + + + + + + + + +
+ + | | + + | | + + + +
+ +---+ | | +---+ + | | + + + + + + + +
+ |K2 | | D | |K1 | + | D | + + + + + + + +
+ + +---+ | | Rotate Left +---+ + + | | Rotate Right | | | | | | | |
+ + + + | | on K1 + + + + | | on K3 | | | | | | | |
| | + + | | ----------> + + | | | | -----------> | A | | B | | C | | D |
| | + + + + | | + + + + | | | | | | | | | | | |
--| A |--+ +--+ +-+++++---------------+ +--+ +--| C |---+++++------------------| |----| |---| |---| |------
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | | | | | | | | | | | |
--+++++--| B |--| C |---------------------| A |--| B |--+++++--------------------------+++++----+++++---+++++---+++++------
| | | | | | | |
| | | | | | | |
---------+++++--+++++---------------------+++++--+++++---------------------------------------------------------------------
*/
TreeNode_T* K3 = currentNode;
TreeNode_T* K1 = K3->left;
K3->left = avl_RotateLeft( K1 );
return avl_RotateRight( K3 );
}
TreeNode_T* avl_RotateRightThenLeft( TreeNode_T* currentNode )
{
/*
+---+ +---+ +---+
|K1 | |K1 | |K2 |
+---+ +---+ +---+
+ + + + + +
+ + + +---+ + +
+ + + |K2 | +---+ +---+
+ +---+ + +---+ |K1 | |K3 |
+ |K3 | + + + +---+ +---+
+ +---+ + + +---+ + + + +
+ + + + + + + |K3 | + + + +
+ + +---+ + + + + + + +---+ + + + + + + + +
| | |K2 | + + | | + + + + + + + + + + + +
| | +---+ | | Rotate Right | | | | + + Rotate Left | | | | | | | |
| A | + + | | on K1 | A | | | + + + + on K3 | | | | | | | |
| | + + | D | ----------> | | | B | + + + + -----------> | A | | B | | C | | D |
| | + + + + | | | | | | | | | | | | | | | | | |
---+++++--+ +--+ +--| |----------------+++++----| |-| |--| |------------------| |----| |---| |---| |---
| | | | | | | | | | | | | | | | | | | |
| | | | | | | | | C | | D | | | | | | | | |
----------| B |--| C |--+++++-------------------------+++++-| |--| |------------------+++++----+++++---+++++---+++++---
| | | | | | | |
| | | | | | | |
----------+++++--+++++--------------------------------------+++++--+++++---------------------------------------------------
*/
TreeNode_T* K1 = currentNode;
TreeNode_T* K3 = K1->right;
K1->right = avl_RotateRight( K3 );
return avl_RotateLeft( K1 );
}
static TreeNode_T* AVL_FixBalance( TreeNode_T* currentNode )
{
if ( NULL != currentNode )
{
if ( currentNode->height > 1 )
{
int heightLeft = 0;
int heightRight = 0;
signed int balance = 0;
TREE_GetSonsHeight( currentNode, &heightLeft, &heightRight );
balance = heightLeft - heightRight;
if ( abs(balance) > 1 )
{
if ( balance > 0 )
{
int heighLeftLeft = 0;
int heighLeftRight = 0;
TREE_GetSonsHeight( currentNode->left, &heighLeftLeft, &heighLeftRight );
if ( heighLeftLeft >= heighLeftRight )
{
currentNode = avl_RotateRight( currentNode );
}
else
{
currentNode = avl_RotateLeftThenRight( currentNode );
}
}
else
{
int heighRightLeft = 0;
int heighRightRight = 0;
TREE_GetSonsHeight( currentNode->right, &heighRightLeft, &heighRightRight );
if ( heighRightRight >= heighRightLeft )
{
currentNode = avl_RotateLeft( currentNode );
}
else
{
currentNode = avl_RotateRightThenLeft( currentNode );
}
}
}
}
}
return currentNode;
}
void AVL_Init( TREE_t* tree, PrintMessage_T* printMessage, AllocateNode_T* allocateNode, FreeNode_T* freeNode )
{
TREE_Init( tree, printMessage, allocateNode, freeNode, AVL_FixBalance);
}
void AVL_InsertNode( TREE_t* tree, int id, Data_T* data )
{
TREE_InsertNode( tree, id, data );
}
void AVL_DeleteNode ( TREE_t* tree, int id )
{
TREE_DeleteNode( tree, id );
}
TreeNode_T* AVL_FindNode( TREE_t* tree, int id )
{
return TREE_FindNode( tree, id );
}
unit_test.c:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "avl_tree.h"
#define TREE_GRAPH_FORMAT_NAME "./graphs/graph%03d.dot"
static TreeNode_T* dynamicAllocationNode( void )
{
return (TreeNode_T*)malloc(sizeof(TreeNode_T));
}
static void dynamicFreeNode( TreeNode_T* node )
{
free(node);
}
FILE *graphFile;
void dotGraphPrint( char* string )
{
fprintf( graphFile, string);
}
static int savedGraphsCounter = 0;
void dotGraphPrintInit( void )
{
char fileNameBuffer[sizeof(TREE_GRAPH_FORMAT_NAME)+3];
char* fileName = (char*)&fileNameBuffer;
sprintf( fileName, TREE_GRAPH_FORMAT_NAME, savedGraphsCounter++ );
graphFile = fopen( fileName, "w");
if ( graphFile == NULL )
{
printf("Unable to open file.");
}
}
void dotGraphPrintDest( void )
{
fclose(graphFile);
}
static void dynamicPrintMessage( Messages_T m )
{
printf("Error message: %d\n", m);
}
#define TEST_AMOUNT_OF_NODEX (0x10 * 0x10)
void testTree( char* title, TREE_Init_T* treeInit, TREE_Delete_T* treeDelete, TREE_InsertNode_T* treeInsert , TREE_DeleteNode_T* treeDeleteNode, TREE_FindNode_T* treeFindNode, TREE_Height_T* treeHeight )
{
printf("%s", title);
Data_T data;
TREE_t tree;
treeInit( &tree, dynamicPrintMessage, dynamicAllocationNode, dynamicFreeNode, NULL );
int i;
int id = 0;
for( i = 0; i < TEST_AMOUNT_OF_NODEX; i++ ) { treeInsert( &tree, id++ , &data); } TREE_CreateDotGraph( tree.root, dotGraphPrintInit, dotGraphPrintDest, dotGraphPrint ); #define FIRST_TO_DELETE 77 #define NEXT_TO_DELETE(__current) ((((__current) * 13241) + 83261) % TEST_AMOUNT_OF_NODEX) #define REPORT_DELETION_EVERY 0x10 int nextToDelete = ((FIRST_TO_DELETE) % (TEST_AMOUNT_OF_NODEX)); int reportCounter = 0; while ( TREE_GetSize(&tree) > 0 )
{
if ( NULL == treeFindNode( &tree, nextToDelete ) )
{
nextToDelete = ((nextToDelete + 1) % (TEST_AMOUNT_OF_NODEX));
}
else
{
bool needToReport = (reportCounter % (REPORT_DELETION_EVERY)) == 0;
id = nextToDelete;
if ( needToReport )
{
TREE_CreateDotGraph( tree.root, dotGraphPrintInit, dotGraphPrintDest, dotGraphPrint );
}
treeDeleteNode( &tree, id );
if ( needToReport )
{
printf("Delete %d (savedGraphsCounter: %d)\n", id, savedGraphsCounter);
TREE_CreateDotGraph( tree.root, dotGraphPrintInit, dotGraphPrintDest, dotGraphPrint );
}
nextToDelete = NEXT_TO_DELETE(nextToDelete);
reportCounter++;
}
}
}
void avlInitWithExtraArgument( TREE_t* tree, PrintMessage_T* printMessage, AllocateNode_T* allocateNode, FreeNode_T* freeNode, TREE_FixBalance_T* fixBalance  )
{
AVL_Init( tree, printMessage, allocateNode, freeNode);
}
int main(void)
{
//My "dot" crush on that: testTree( "\nTest tree data structure:\n" Â Â , TREE_Init, TREE_Delete, TREE_InsertNode, TREE_DeleteNode, TREE_FindNode, TREE_Height );
testTree( "\nTest avl tree data structure:\n", avlInitWithExtraArgument, Â TREE_Delete, AVL_InsertNode , AVL_DeleteNode , AVL_FindNode , TREE_Height );
return EXIT_SUCCESS;
}
rapture84 
Written
on 2013.08.14