Двоичные деревья, СИ, Помогите с балансировкой, пожалуйста! Опции

[Eichhorn]

Язык СИ, пишу на dev cpp.
Задача:
Реализовать программу, сохраняющую числа из входного файла в двоичном дереве. Имя файла приходит как аргумент командной строки. Числа необходимо хранить в сбалансированом дереве двоичного поиска. После построения дерева вывести его содержимое на экран в порядке возрастания.

Пример:
input.txt
48 1 0 29

Вывод:
0 1 29 48

Код

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    struct tree *pred;
};

struct tree * create(int data) {

    struct tree *p = (struct tree*)calloc(1,sizeof(struct tree));
    p->data=data;    
    p->left=NULL;
    p->right=NULL;
    return p;        
}

struct tree *add_tree(struct tree * head,int data) {
    struct tree *a = head;

    if(head==NULL){
        head=create(data);
        return head;
    }

    while(1) {
        if(a->data < data) {
            if(!a->right) {
                a->right = create(data);
                break;
            }
            a = a->right;
        } else {
            if(!a->left) {
                a->left = create(data);
                break;
            }
            a = a->left;
        }
    }


    return head;
}

int depth_tree(struct tree *head) {
if(head) {
  return 1 + depth_tree(head->left) + depth_tree(head->right);
}
return 0;
}

void print_tree(struct tree *tree) {
    if(tree==NULL){
        return;
    }

    print_tree(tree->left);
    printf("%i\n",tree->data);
    print_tree(tree->right);

}

void balance_tree(){
    
}

int main() {
    int n=0;
    int g=0;
    struct tree* head = NULL;    

    FILE * f=fopen("file.txt","r");

    
        if(f==0){
            printf("%s","Fail ne otkrit\n");
            return -1;
        }
    while(!feof(f)){
        g=fscanf(f,"%d",&n);
        head = add_tree(head,n);
        if(g!=1){
            printf("%s","fail pust\n");
        
            return -1;
        }        
    }
    
    print_tree(head);
    printf("depth is %i\n",depth_tree(head));
    getch();
    return 0;
}

Здесь просто вывод дерева. А как сделать балансировку?

Сообщение отредактировано: Eichhorn - 25.11.2011 19:51

[IUnknown]

А как сделать балансировку?

Вот так: Идеально сбалансированное бинарное дерево

[Eichhorn]

Что-то никак не могу понять как это делается... Половину из того, что там написано в тексте программы не знаю...

[IUnknown]

Так. Давай уточним: тебе надо это дело просто сбалансировать один раз после того, как дерево было заполнено, или надо постоянно поддерживать его в сбалансированном виде (то есть, чтобы в любой момент высота левой/правой ветки не отличались больше, чем на 1)?

Просто тот алгоритм, ссылку на который я привел, подразумевает, что ему передаются уже упорядоченные данные. Если тебе надо однократно перебалансировать дерево, уже после создания обычного бинарного дерева поиска - то это возможно (тебе уже известно количество элементов, и сами элементы очень просто получить в упорядоченном виде). Если же надо при добавлении каждого элемента заниматься перестроениями - это уже не бинарное, а, скорее, AVL-дерево (информация есть здесь: http://volvo71.narod.ru/faq_folder/avl.htm , если надо - помогу написать его на чистом С)

[Гость]

Нам нужно бинарное дерево, чтобы в любой момент высота не отличалась более, чем на 1.

[IUnknown]

Значит, надо будет после каждого добавления элемента полностью перестраивать дерево, другого варианта просто не существует. Очень неэффективный метод, надо сказать: дерево из 10 элементов будет создаваться 11 раз (один раз - то самое, несбалансированное, которое есть у тебя, и еще 10 раз будет создаваться/удаляться новое дерево, в котором высоты почти равны). Чуть позже покажу, как это сделать...

[Eichhorn]

У меня сейчас есть такой код:

Код

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

struct tree {
    int data;
    struct tree *left;
    struct tree *right;
    int balance; //-1, 0, 1
};

struct tree * create(int data) {

    struct tree *p = (struct tree*)calloc(1,sizeof(struct tree));
    p->data=data;    
    p->left=NULL;
    p->right=NULL;

    return p;        
}

struct tree * small_RR(struct tree *a){
    struct tree *b = a->right;
    struct tree *c = b->right;
    a->right = b ->left;
    b->left=a;
    a->balance = 0;
    b->balance = 0;
    return b;    
}

struct tree * big_RR(struct tree *a){
    struct tree *b = a -> right;
    struct tree *c = b -> left;
    b -> left = c->right;
    c -> right = b;
    a -> right = c;
    a=small_RR(a);

    return a;
}

struct tree * small_LR(struct tree *a){
    struct tree *b = a->left;
    struct tree *c = b->left;
    a->left = b ->right;
    b->right=a;
    a->balance = 0;
    b->balance = 0;
    return b;    
}

struct tree * big_LR(struct tree *a){
    struct tree *b = a -> left;
    struct tree *c = b -> right;
    b -> right = c->left;
    c -> left = b;
    a -> left = c;
    a=small_RR(a);

    return a;
}

int add_tree(struct tree ** head,int data) {
    struct tree *a = *head;
    if(a==NULL){
        *head = create(data);
        return 1;
    }
    if(a->data < data) {
        int changed = add_tree(&(a->right),data);

        if(!changed)
        return 0;

        if(a -> balance == -1){
            a -> balance ++;
            return 0;
        }    

        if(a -> balance == 0){
            a -> balance ++;
            return 1;
        }

        if(a -> balance == 1){
            struct tree *b;
            a -> balance ++;
             b = a -> right;
            if(b -> balance == 1){
                *head = small_RR(a);
            }
            if(b -> balance == -1)
                *head = big_RR(a);
        }
    
    }

    else {
        int changed = add_tree(&(a->left),data);

        if(!changed)
        return 0;

        if(a -> balance == 1){
            a -> balance --;
            return 0;
        }

        if(a -> balance == 0){
            a -> balance --;
            return 1;
        }

        if(a -> balance == -1){
            struct tree *b;
            a -> balance --;

            b = a -> left;

            if(b -> balance == -1){
                *head = small_LR(a);
            }

            if(b -> balance == 1)
                *head = big_LR(a);
            
        }

    }

}


int depth_tree(struct tree *head) {
    if(head) {
        return 1 + maxx(depth_tree(head->left), depth_tree(head->right));

    }
    return 0;
}

int maxx(int a, int b){
    if(a>b)
    return a;
    return b;
}

void print_tree(struct tree *tree) {
    if(tree==NULL){
        return;
    }

    print_tree(tree->left);
    printf("%i\n",tree->data);
    print_tree(tree->right);
}

void dump_tree(struct tree * t) {
    if(t->left) {
        printf("(");
        dump_tree(t->left);
        printf(")");
    }
    printf("%d", t->data);
    if(t->right) {
        printf("(");
        dump_tree(t->right);
        printf(")");
    }
}

void balance_tree(){

}

int main() {
    int n=0;
    int g=0;
    struct tree* head = NULL;    

    FILE * f=fopen("input.txt","r");


    if(f==0){
        printf("%s","Fail ne otkrit\n");
        return -1;
    }
    while(!feof(f)){
        g=fscanf(f,"%d",&n);
        add_tree(&head,n);
        if(g!=1){
            printf("%s","fail pust\n");

            return -1;
        }        
    }

    dump_tree(head);
    printf("depth is %i\n",depth_tree(head));

    getch();
    return 0;
}

Но нам сказали, что эта программа не совсем корректно работает. Балансировку не правильно считает.

[IUnknown]

Но это уже не совсем бинарные деревья. У тебя изменена struct tree (добавлено новое поле balance). Если надо именно с бинарными - то:

Много кода (Показать/Скрыть)

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <string.h>

struct tree
{
    int data;
    struct tree *left;
    struct tree *right;
};

struct tree *create(int data)
{
    struct tree *p = (struct tree*)calloc(1, sizeof(struct tree));
    p->data = data;
    p->left = NULL;
    p->right = NULL;
    return p;
}

/*
   Это добавляет новый элемент к бинарному дереву,
   не изменял, то что было то и осталось, только
   переформатировалось (у меня AStyle настроен на другой
   стиль)
*/
struct tree *add_tree(struct tree * head, int data)
{
    struct tree *a = head;

    if(!head)
    {
        head = create(data);
        return head;
    }

    while(1)
    {
        if(a->data < data)
        {
            if(!a->right)
            {
                a->right = create(data);
                break;
            }
            a = a->right;
        }
        else
        {
            if(!a->left)
            {
                a->left = create(data);
                break;
            }
            a = a->left;
        }
    }

    return head;
}

/* Чуть-чуть поправил функцию вычисления глубины дерева */
int depth_tree(struct tree *head) {
    /*
    if(head)
    {
        return 1 + depth_tree(head->left) + depth_tree(head->right);
    }
    return 0;
    */

    if(head)
    {
        int l_d = depth_tree(head->left);
        int r_d = depth_tree(head->right);
        return 1 + (l_d > r_d ? l_d : r_d);
    }
    return 0;
}

/*
   Здесь я сделал 2 разных функции для вывода деревьев по одной
   простой причине: чтобы вывести в отсортированном порядке узлы
   обычного бинарного дерева - надо обходить его в *симметричном*
   порядке:
   (Левое поддерево - Корень - Правое поддерево).

   Для того же, чтобы вывести упорядоченные узлы сбалансированного
   дерева, надо его обойти в *прямом* порядке:
   (Корень - Левое поддерево - Правое поддерево).
*/
void print_tree(struct tree *root)
{
    if(!root) return;

    print_tree(root->left);
    printf("%i\n", root->data);
    print_tree(root->right);
}

void print_balanced_tree(struct tree *root)
{
    if(!root) return;

    printf("%i\n", root->data);
    print_balanced_tree(root->left);
    print_balanced_tree(root->right);
}

/* Это будет удалять любое дерево */
void delete_tree(struct tree *root)
{
    if(!root) return;

    delete_tree(root->left);
    delete_tree(root->right);
}

/* Здесь я записываю всё содержимое бинарного дерева,
   упорядоченное по возрастанию, в буфер, чтобы потом
   оттуда заполнять дерево сбалансированное. Обход -
   симметричный.
*/
void buff_tree(struct tree *root, int *items, int *curr)
{
    if(!root) return;

    buff_tree(root->left, items, curr);

    items[*curr] = root->data;
    (*curr) += 1;

    buff_tree(root->right, items, curr);
}

/* Да, я знаю, что глобальные переменные - зло, но так будет проще */
int curr_item;

/*
   Собственно, эта функция и создает сбалансированное дерево, получая
   количество элементов и сами элементы.
*/
void create_balanced_tree(int n_items, int *items, struct tree **root)
{
    struct tree *new_node;
    int x, n_left, n_right;

    new_node = *root;
    if(!n_items)
        *root = NULL;
    else
    {
        n_left = n_items / 2;
        n_right = n_items - n_left - 1;
        x = items[curr_item++];
        new_node = create(x);
        create_balanced_tree(n_left, items, &((*new_node).left));
        create_balanced_tree(n_right, items, &((*new_node).right));
        *root = new_node;
    }
};

/*
   А это - подготовительная функция. Как только у нас есть дерево,
   которое надо сбалансировать - мы
   1) удаляем старое сбалансированное дерево
   2) заполняем динамически выделенный буфер упорядоченными
   значениями узлов бинарного дерева
   3) вызываем функцию построения сбалансированного дерева
*/
struct tree *create_balanced(struct tree *prev_balanced,
                             struct tree *unbalanced, int length)
{
    int curr = 0;
    struct tree *bt = NULL;

    if(prev_balanced)
    {
        delete_tree(prev_balanced);
    }

    int *buff = (int*)malloc(length * sizeof(int));
    buff_tree(unbalanced, buff, &curr);

    curr_item = 0;
    create_balanced_tree(length, buff, &bt);

    return bt;
}


int main()
{
    int n = 0;
    int g = 0;
    int n_count = 0;
    /* Это - указатель на обычное дерево */
    struct tree* head = NULL;
    /* Это - указатель на сбалансированное дерево */
    struct tree* b_tree = NULL;

    FILE *f = fopen("file.txt", "r");
    if(!f)
    {
        printf("%s\n","Fail ne otkrit");
        return -1;
    }

    while(!feof(f))
    {
        g = fscanf(f, "%d", &n);
        head = add_tree(head,n);
        n_count += 1;

        if(g != 1)
        {
            printf("%s\n","fail pust");
            return -1;
        }
        b_tree = create_balanced(b_tree, head, n_count);
    }

    printf("\nUnbalanced:\n");
    print_tree(head);

    printf("\nBalanced:\n");
    print_balanced_tree(b_tree);

    printf("unbalanced depth is %i\n",depth_tree(head));
    printf("balanced depth is %i\n",depth_tree(b_tree));

    /* Не забудь удалить деревья, чтоб не было утечек */
    getch();

    return 0;
}

file.txt

48 1 0 29 2 6 4 9 5

Вывод:

Unbalanced:
0
1
2
4
5
6
9
29
48

Balanced:
0
1
2
4
5
6
9
29
48
unbalanced depth is 7
balanced depth is 4

Сообщение отредактировано: IUnknown - 26.11.2011 21:37

[Eichhorn]

Спасибо за ещё один вариант решения. Но, возвращаясь к моей проге... Нам преподаватель сказал заменить строку

Код

printf("%d",tree->data);

на

Код

printf("%d",tree->balance);

в функции dump_tree.
При этом баланс неправильно выводится. Например при числах 5 1 8 7 6 9 10 балансировку делает правильно, но в некоторых местах пишет, что баланс равен 2, хотя он по определению либо 1, либо -1, либо 0.

Сообщение отредактировано: Eichhorn - 28.11.2011 21:32

[IUnknown]

хотя он по определению либо 1, либо -1, либо 0.

По определению - это конечно, хорошо, но... Смотри на момент отладки:


Как думаешь что произойдет? При выходе из функции чему будет равен a->balance, учитывая, что b->balance равен 0? Чуть ниже есть такой же момент с a->balance, но в другую сторону, в (-2), то есть, теоретически, при некотором стечении обстоятельств, баланс может быть и (+2) и (-2).

Надо добавить еще одну ветку, что делать, если b->balance == 0

[Eichhorn]

Что-то я никак не могу придумать... В голову пришло только

Код

if(b -> balance == 0){
    a -> balance --;
}

и

Код

if(b -> balance == 0){
    a -> balance ++;
}

[IUnknown]

А если сделать вот так:

        if(a -> balance == 1){
            struct tree *b;
            /* a -> balance ++; */
            b = a -> right;
            if(b -> balance == 1){
                *head = small_RR(a);
            }
            if(b -> balance == -1)
                *head = big_RR(a);
        }

// ...

        if(a -> balance == -1){
            struct tree *b;
            /* a -> balance --; */

            b = a -> left;
            if(b -> balance == -1){
            *head = small_LR(a);
            }

            if(b -> balance == 1)
                *head = big_LR(a);
        }

(понимаешь идею да? Всё равно баланс отрицательный или положительный, зачем еще усиливать), то произойдет чудо, и вывод из вот такого

((1(0))-1(0))1((0)2((0)1((0)0((0)0(0)))))depth is 6

станет таким:

((1(0))-1(0))0(((0)0(0))0((0)0((0)0(0))))depth is 5

(тестировалось на данных "5 1 8 7 6 9 10 17 3 12 22 25 14 31")

Почему это?

[Eichhorn]

Спасибо!

Сообщение отредактировано: Eichhorn - 3.12.2011 11:17