Drzewo

0

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

0
  1. Zapisujesz sobie seed oraz zerujesz licznik
  2. Genierujesz liczbę i wstawiasz do drzewa
  3. Rekurencyjnie mierzysz wysokość lewego i prawego drzewa dla każdego węzła jeżeli jest źle kończysz program.
  4. Zwiększasz licznik
  5. Zapisujesz licznik
  6. Przechodzisz do pkt 2.
    Po zakończeniu działania takiego algorytmu masz seed oraz ile liczbę bezpiecznych kroków, więc:
  7. Odpalasz debugier
  8. Odczytujesz i odtwarzasz seed
  9. Ustawiasz z ilość kroków z odczytanego licznika
  10. Przechodzisz tyle kroków w trybie przyśpieszonym
  11. Zaczynasz iść krok po kroku.
0

Problem w tym, że mam 30min na oddanie tego :D

0

Tak na szybko bez sprawdzania, wez sprawdz to:

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_top->left = old_left->right;

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

Dodalem ** old_top->left = old_left->right;**
i analoicznie dla lewej rotacji. Moge sie mylic, nie sprawdzilem.

0
nalik napisał(a):

Tak na szybko bez sprawdzania, wez sprawdz to:

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_top->left = old_left->right;

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

Dodalem ** old_top->left = old_left->right;**
i analoicznie dla lewej rotacji. Moge sie mylic, nie sprawdzilem.

No niestety nie :( ale dzięki za próbę pomocy.

0

Aaa, w zlym miejscu dodałem:

 
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_top->left = old_left->right;
    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);
}

Tzn nie
old_left->right = old_top;
old_top->left = old_left->right;

a
old_top->left = old_left->right;
old_left->right = old_top;

0

Też nie :)

0

Ehe, bo jeszcze dla podwojnych rotacji :D

0
nalik napisał(a):

Ehe, bo jeszcze dla podwojnych rotacji :D

Też nie :D hehe

0

algorytm który podałem zająłby max 15 min.

0

Tzn że coś jeszcze jest źle. Nie możesz ustawiać wskaźników do dzieci na NULL przy rotacjach, bo nie wiesz na jakim poziomie się wywoła rotacja. Dla drzewa o głębokości 3 kod może się wydawać poprawny, ale dla głębszych już nie.

1 użytkowników online, w tym zalogowanych: 0, gości: 1