Mam mały problem nie wiem dlaczego ale mój kod źle balansuje drzewo AVL według testu przeprowadzonego przez server :(
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "blatt11.h"
void print_node(AVLNode* node);
int calculate_height(AVLNode* node);
int get_node_height(AVLNode* node);
int max(int a, int b);
void AVL_in_order_walk(AVLTree* avlt)
{
if (avlt->root != NULL) print_node(avlt->root);
printf("\n");
}
void print_node(AVLNode* node)
{
if (node->left != NULL)
{
print_node(node->left);
}
printf(" %d", node->value);
if (node->right != NULL)
{
print_node(node->right);
}
}
void AVL_rotate_left(AVLTree* avlt, AVLNode* x)
{
AVLNode* parent = x->parent;
AVLNode* old_top = x;
AVLNode* old_right = x->right;
AVLNode* old_bottom = x->right->right;
old_top->right = NULL;
old_top->parent = old_right;
old_right->left = old_top;
old_right->parent = parent;
if (parent == NULL) avlt->root = old_right;
else
{
if (parent->left == old_top) parent->left = old_right;
if (parent->right == old_top) parent->right = old_right;
}
old_top->height = calculate_height(old_top);
old_bottom->height = calculate_height(old_bottom);
old_right->height = calculate_height(old_right);
if (parent != NULL) parent->height = calculate_height(parent);
}
void double_rotate_left(AVLTree* avlt, AVLNode* x)
{
AVLNode* parent = x->parent;
AVLNode* old_top = x;
AVLNode* old_right = x->right;
AVLNode* old_bottom = x->right->left;
old_top->right = NULL;
old_right->left = NULL;
old_bottom->left = old_top;
old_top->parent = old_bottom;
old_right->parent = old_bottom;
old_bottom->right = old_right;
old_bottom->parent = parent;
if (parent == NULL) avlt->root = old_bottom;
else
{
if (parent->left == old_top) parent->left = old_bottom;
if (parent->right == old_top) parent->right = old_bottom;
}
old_top->height = calculate_height(old_top);
old_right->height = calculate_height(old_right);
old_bottom->height = calculate_height(old_bottom);
if (parent != NULL) parent->height = calculate_height(parent);
}
void AVL_rotate_right(AVLTree* avlt, AVLNode* y)
{
AVLNode* parent = y->parent;
AVLNode* old_top = y;
AVLNode* old_left = y->left;
AVLNode* old_bottom = y->left->left;
old_top->left = NULL;
old_top->parent = old_left;
old_left->right = old_top;
old_left->parent = parent;
if (parent == NULL) avlt->root = old_left;
else
{
if (parent->right == old_top) parent->right = old_left;
if (parent->left == old_top) parent->left = old_left;
}
old_top->height = calculate_height(old_top);
old_bottom->height = calculate_height(old_bottom);
old_left->height = calculate_height(old_left);
if (parent != NULL) parent->height = calculate_height(parent);
}
void double_rotate_right(AVLTree* avlt, AVLNode* y)
{
AVLNode* parent = y->parent;
AVLNode* old_top = y;
AVLNode* old_left = y->left;
AVLNode* old_bottom = y->left->right;
old_top->left = NULL;
old_left->right = NULL;
old_bottom->right = old_top;
old_top->parent = old_bottom;
old_left->parent = old_bottom;
old_bottom->left = old_left;
old_bottom->parent = parent;
if (parent == NULL) avlt->root = old_bottom;
else
{
if (parent->right == old_top) parent->right = old_bottom;
if (parent->left == old_top) parent->left = old_bottom;
}
old_top->height = calculate_height(old_top);
old_left->height = calculate_height(old_left);
old_bottom->height = calculate_height(old_bottom);
if (parent != NULL) parent->height = calculate_height(parent);
}
void AVL_balance(AVLTree* avlt, AVLNode* node)
{
if (get_node_height(node->left) > get_node_height(node->right) + 1)
{
if (node->left->right != NULL)
{
double_rotate_right(avlt, node);
}
else if (node->left->left != NULL)
{
AVL_rotate_right(avlt, node);
}
}
else if (get_node_height(node->right) > get_node_height(node->left) + 1)
{
if (node->right->left != NULL)
{
double_rotate_left(avlt, node);
}
else if (node->right->right != NULL)
{
AVL_rotate_left(avlt, node);
}
}
}
AVLNode* new_node(int value)
{
AVLNode* node = malloc(sizeof(AVLNode));
node->value = value;
node->height = 1;
node->left = NULL;
node->right = NULL;
node->parent = NULL;
return node;
}
void AVL_insert_value(AVLTree* avlt, int value)
{
AVLNode* parent = avlt->root;
if (parent == NULL)
{
AVLNode* node = new_node(value);
avlt->root = node;
avlt->numberOfNodes = 1;
return;
}
while (parent != NULL)
{
if (value < parent->value)
{
if (parent->left == NULL)
{
AVLNode* node = new_node(value);
parent->left = node;
node->parent = parent;
avlt->numberOfNodes++;
parent->height = calculate_height(parent);
break;
}
else
{
parent = parent->left;
}
}
else if (value > parent->value)
{
if (parent->right == NULL)
{
AVLNode* node = new_node(value);
parent->right = node;
node->parent = parent;
avlt->numberOfNodes++;
parent->height = calculate_height(parent);
break;
}
else
{
parent = parent->right;
}
}
else
{
break;
}
}
while (parent != NULL) {
parent->height = calculate_height(parent);
AVL_balance(avlt, parent);
parent = parent->parent;
}
}
void free_node(AVLNode* node);
void AVL_remove_all_elements(AVLTree* avlt)
{
free_node(avlt->root);
}
void free_node(AVLNode* node)
{
if (node == NULL) return;
free_node(node->left);
free_node(node->right);
free(node);
}
int calculate_height(AVLNode* node)
{
return max(get_node_height(node->left), get_node_height(node->right)) + 1;
}
int get_node_height(AVLNode* node)
{
if (node == NULL) return 0;
return node->height;
}
int max(int a, int b)
{
if (a > b) return a;
return b;
}
Jak ktoś pomoże będę całował po nogach :D