Raw thoughts: Open Technology Vision for sake of all Humanity

Open source is software that open and free for use and change by anyone, it can work or be adapted to work almost on any piece of hardware. Open source projects are made upon thousands of work hours of experts, all over the world, with ideological idea that technology could be shared to promote the humanity as whole. A few examples: UNIX, GNU, Linux, Wikipedia, Android, Firefox, OpenOffice and many many others. Nowadays we are living in era of prosper for open source idea, any individual can create something that seemed impossible before. Today we are sitting on the shoulders of giants, and we almost can touch the sky. But I think that we can progress even further with open source ideology. A few ideas I have on that matter:

1. Why don’t we legislate laws to make any piece of software, to be available as open source, for sake of humanity, after some period of time? But I don’t think that this period of time should be more then 10 years, because of huge progress in technology. Basically same idea as patents registrations.
2. To apply open source ideology on hardware, and any other aspect of technology like chemistry and biology, and maybe even on all the knowledge we have? Of course our private knowledge shouldn’t be included, for example diaries ( And maybe it should? Deserve a debates… ) , but almost anything else should.
3. Limit the period of time in which royalties required to be paid due to patent, and limit creators rights ownership time. I don’t understand why we let record labels own the creator rights that should belong to singers, writers and composers, and not to the record labels. I am not even sure, why should we allow patents and creators rights to be sold or inherited, and be used by huge companies to collect money for basically nothing, without helping somehow to the creation process itself. To me all these laws seems as legislated for already very powerful and rich elements in our society, and for them alone, in very injustice and illogical way, and they don’t helping or promoting somehow the society. These laws are taxes for true parasitism, why don’t we change them?

Is it about socialism vs capitalism? It seems to me that both of them failed in execution, in their pure forms. For example communistic USSR, where I was born and lived for 7 years, everything belonged to the state. Almost everybody was having roughly the same salary, of course the people with more connections got more. And people with more power got exponentially more than common people. But this system was wrong and deeply corrupted. Today I can compare this regime, with the one that I’m living in today, Israeli, which is much more capitalistic, and largely very similar to the US. It’s flawed and corrupted too, in different but also somehow similar manner. In a way, that already rich people, that own most of the companies at state, have a huge influence over politicians, and eventually force legislation in their favor. So the wealth going from poor and middle class people to tycoons. Each year we pay more for having less, and government just preserves the inequality. So we need to think logically, what can promote us as human society, to be better, as whole and as better place for each and single individual. Technology and knowledge should belong to everyone, and not just to the people who can bribe the politicians.

AVL tree full implementation in C ( Insert, Delete and Find )

Aside

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