ok i havent fully tested this yet as my head is beginning to thump and i need t get off the pc and sit quite for a while. But although i still need to make it update the balance factor (im not sure why it isn't) i think i have severely broken the back of the issues
a new main
Code:
#include "bst.h"
void slr(Bin_Node **root); //root is the troubled node
void srr(Bin_Node **root);
void dlr(Bin_Node **root);
void drr(Bin_Node **root);
int main()
{ //10,6, 3, 9, 2, 3, 13, 54, 20, 43
int i, nums[] = {9, 5, 10, 1, 7, 8};
Bin_Tree *tree;//, *tree_trunk;
tree = create_tree();
for (i = 0; i < 6; i++)
{
insert(tree, nums[i]);
}
print(tree);
destroy(tree);
return 0;
}
void slr(Bin_Node **root) //single left rotate
{
Bin_Node *A = *root;
Bin_Node *B = A->right;
Bin_Node *C = B->left;
//perform the rotation
B->left = A;
*root = B;
// assigns B's left child to A->right as it must be bigger than A else if C = NULL sets A->right = NULL
A->right = C;
//call this to update balance factors of the moved nodes.
balance(&(*root));
}
void srr(Bin_Node **root)
{
Bin_Node *A = *root;
Bin_Node *B = A->left;
Bin_Node *C = B->right;
//perform the rotation
B->right = A;
*root = B;
//Assign B's right child to A->left as it must be smaller than A else if C = NULL sets A->left = NULL
A->left = C;
//call this to update balance factors of the moved nodes.
balance(&(*root));
}
void dlr(Bin_Node **root)
{
Bin_Node *A = *root;
Bin_Node *B = A->right;
Bin_Node *C = B->left;
Bin_Node *CL = C->left;
Bin_Node *CR = C->right;
A->right = CL;
B->left = CR;
C->left = A;
C->right = B;
*root = C;
balance(&(*root));
}
void drr(Bin_Node **root)
{
Bin_Node *A = *root;
Bin_Node *B = A->left;
Bin_Node *C = B->right;
Bin_Node *CL = C->left;
Bin_Node *CR = C->right;
B->right = CL;
A->left = CR;
C->left = B;
C->right = A;
*root = C;
balance(&(*root));
}
void balance( Bin_Node **parent )
{
int balance = differences( *parent );
if ( balance > 1 )
{
//if ( differences( (*parent)->left ) > 0 )
if ((*parent)->left->balance_factor > 0)
{
printf("parent->left is > 0 'single rotate right'\n");
srr(&(*parent));
}
else
{
// some rotation here( parent )
printf("parent->left <= 0 'double rotate right'\n");
drr(&(*parent));
}
}
else if ( balance < -1 )
{
//if ( differences( (*parent)->right ) > 0 )
if ((*parent)->right->balance_factor > 0)
{
printf("parent->right > 0 'double rotate left'\n");
dlr(&(*parent));
}
else
{
printf("parent->right <= 0 'single rotate left\n");
slr(&(*parent));
}
}
}
int differences( Bin_Node *node )
{
int lh = countlevels( node->left );
int rh = countlevels( node->right );
node->balance_factor = lh - rh;
return node->balance_factor;
}
int countlevels(Bin_Node *node)
{
if (!node)
{
return 0;
}
int lh = countlevels( node->left );
int rh = countlevels( node->right );
return max( lh, rh ) + 1;
}
int max(int x, int y)
{
if (x > y)
{
return x;
}
return y;
}