Doskonale zrównoważone drzewo

Otóż mam taki problem: Chcę stworzyć doskonale zrównoważone drzewo (to to, że różnica rozmiarów lewego i prawego poddrzewa to max 1). Algorytm z tego co wiem wygląda mniej więcej tak:

1. Tworzymy tablicę z elementami.
2. Sortujemy ją.
3. Wybieramy środkowy element i ustawiamy go jako korzeń.
4. Bierzemy elementy środkowe z tablic będących efektem podziału tablicy pierwotnej względem środka.
5. Umieszczamy je w drzewie: odpowiednio z lewej i prawej.
   ... No i tak rekurencyjnie do końca. System dzielenia tablic trochę jak w MergeSort.

No i napisałem implementacje tego algorytmu. Tablicę tworzy raczej bezbłędnie, wrzucanie do drzewa też zgodnie z tym co udało mi się metodami wypisywania elementów działa bez zarzutu. Jednak kiedy próbuję wypisać elementy drzewa, to wypisuje mi tylko kilka - nigdy wszystkie. Tablica jeszcze nie jest posortowana - zostawiłem to na potem. Na razie chciałem sprawdzić, czy drzewo się tworzy.

Oto kod:

 #include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
#include <fstream>
#include <algorithm>
using namespace std;

struct wezel
    {
        char nazwisko[13];
        char imie[13];
        int indeks;
        wezel *rodzic;  //wskaznik na rodzica
        wezel *lewy;   //wskaznik na lewe dziecko
        wezel *prawy;   //wskaznik na prawe dziecko

        wezel()
            {
                rodzic=NULL;
                lewy=NULL;
                prawy=NULL;
            }
    };

wezel *BBSTRoot = NULL;

void makeBBST (wezel *tab, int first, int last, wezel *rodzic) {

    if(first <= last) {
        int middle = (first+last)/2;

        wezel *actual = new wezel;
        *actual = tab[middle];
        actual->rodzic = rodzic;
        actual->lewy = NULL;
        actual->prawy = NULL;
        cout << actual->imie << endl;
        if(!rodzic){
            BBSTRoot = actual;}
            //cout << actual->imie << endl;}
        else {
            if(actual->indeks < rodzic->indeks){
                rodzic->lewy = actual;}
                //cout << actual->imie << endl;}
            else{
                rodzic->prawy = actual;}
                //cout << actual->imie << endl;}
        }
        //cout << actual->imie << endl;

        makeBBST(tab, first, middle - 1, actual);
        makeBBST(tab, middle + 1, last, actual);
    }
}


void BSTprintInOrder (wezel *k) {

    if(k->lewy) BSTprintInOrder(k->lewy);
    cout << k->indeks << " ";
    if(k->prawy) BSTprintInOrder(k->prawy);
}

void BSTprintPreOrder(wezel *k) {
    cout << k->indeks << " ";
    if(k->lewy) BSTprintPreOrder(k->lewy);
    if(k->prawy) BSTprintPreOrder(k->prawy);
}

void BSTprintPostOrder(wezel *k) {
    if(k->lewy) BSTprintPostOrder(k->lewy);
    if(k->prawy) BSTprintPostOrder(k->prawy);
    cout << k->indeks << " ";
}

int main()
    {
        fstream dane;
        dane.open("listy.txt", fstream::in);

        wezel *tab = new wezel [10];
            for(int i = 0; i < 9; i++)
                {
                    dane >> tab[i].indeks;
                    dane >> tab[i].nazwisko;
                    dane >> tab[i].imie;
                    cout << tab[i].indeks << endl;
                }
        makeBBST(tab, 0, 9, NULL);
        cout << endl << "Wypisywanie:" << endl;
        BSTprintInOrder(BBSTRoot);
        cout << endl << "Nastepne wypisywanie:" << endl;
        BSTprintPostOrder(BBSTRoot);
        cout << endl << "Nastepne wypisywanie:" << endl;
        BSTprintPreOrder(BBSTRoot);

        return 0;
    }

wczytujesz do tablicy 9 elementów, a wykorzystujesz 10
poza tym wygląda ok, ale udostępniłbyś plik listy.txt żeby można było uruchomić kod u siebie

Tu w kodzie wczytuję 9, bo akurat taką wersję skopiowałem. Próbowałem różnych opcji. Mniej elementów, tyle samo, a nawet próbowałem przekroczyć zakres. Zawsze źle. W załączniku plik "listy.txt". Imiona i nazwiska może mało realne, ale nie o to przecież chodzi^^

problemem jest właśnie to że pominąłeś część algorytmu

            if(actual->indeks < rodzic->indeks){
                rodzic->lewy = actual;}
                //cout << actual->imie << endl;}
            else{
                rodzic->prawy = actual;}
                //cout << actual->imie << endl;}
        }

w tym fragmencie kluczowym jest to żeby tablica była posortowana bo inaczej sobie nadpisujesz elementy drzewka

jeżeli chcesz tylko sprawdzić działanie na tym etapie to zamień warunek na:

            if(rodzic->lewy == NULL){
                rodzic->lewy = actual;}
                //cout << actual->imie << endl;}
            else{
                rodzic->prawy = actual;}
                //cout << actual->imie << endl;}
        }

zresztą taki warunek możesz nawet zostawić też potem bo jest bardziej uniwersalny, bardziej logiczny i dopuszcza identyczne indeksy

Faktycznie! Dzięki bardzo:D Wystarczyło rzeczywiście posortować i zmienić te warunki. Bardzo Ci dziękuję:)

Problem rozwiązany:)