Drzewo

Odpowiedz Nowy wątek
2016-02-05 19:16
Tol
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

edytowany 1x, ostatnio: Tol, 2016-02-05 19:20

Pozostało 580 znaków

2016-02-05 19:28
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.

Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-02-05 19:29
Tol
0

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

Pozostało 580 znaków

2016-02-05 19:55
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.

edytowany 1x, ostatnio: nalik, 2016-02-05 19:56

Pozostało 580 znaków

2016-02-05 20:13
Tol
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.

Pozostało 580 znaków

2016-02-05 20:18
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;

edytowany 1x, ostatnio: nalik, 2016-02-05 20:19

Pozostało 580 znaków

2016-02-05 20:22
Tol
0

Też nie :)

Pozostało 580 znaków

2016-02-05 20:29
0

Ehe, bo jeszcze dla podwojnych rotacji :D

Pozostało 580 znaków

2016-02-05 21:29
Tol
0
nalik napisał(a):

Ehe, bo jeszcze dla podwojnych rotacji :D

Też nie :D hehe

Pozostało 580 znaków

2016-02-05 21:30
0

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


Wykonuję programy na zamówienie, pisać na Priv.
Asm/C/C++/Pascal/Delphi/Java/C#/PHP/JS oraz inne języki.

Pozostało 580 znaków

2016-02-05 21:31
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.

edytowany 1x, ostatnio: nalik, 2016-02-05 21:31

Pozostało 580 znaków

Odpowiedz
Liczba odpowiedzi na stronę

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