[es] - Par pitanja u vezi binarnih stabala

MPesic
Beograd

Član broj: 164946
Poruke: 124
*.dynamic.isp.telekom.rs.

+25 Profil

^{25.01.2013. u 22:45 - pre 136 meseci}

Od niza brojeva sam napravio uredjeno binarno stablo, koje izgleda ovako:

Code:

                                      15
                                     /   \
                                    /     \
                                   /       \
                                  /         \
                                 /           \
                               14           18
                              /                 \
                             /                   \
                           10                   29
                          /   \                 /  \
                         /     \               /    \
                        5      12             21    31
                          \                     \
                           7                     26
                                                /   \
                                              25    27

Kako bih izvrsio dodavanje jos jednog lista recimo broja 13. Da li ga odmah stavljam u desnom podstablu elementa 12 ili se to izvodi na neki drugi nacin?

Drugo pitanje je imam niz brojeva 15, 19, 10, 7, 17, 16. Kreiram stablo koriscenjem algoritma heap sort koje izgleda ovako.

Code:

                             19
                            /   \
                           /     \
                          /       \
                         /         \
                        /           \
                      17           16
                     /   \        /
                   7      15     10

A kako se kreira stablo primenom algoritma MIN heap i MAX heap?

Odgovor na temu

reiser

Član broj: 7895
Poruke: 2314

+102 Profil

Re: Par pitanja u vezi binarnih stabala

^{26.01.2013. u 15:17 - pre 136 meseci}

Aj posto ti niko nije odgovorio.

How to add node in binary tree

Code:
You traverse the binary tree from the root:
if your new element is less or equal than the current node, you go to the left subtree, otherwise to the right subtree and continue traversing

if you arrived at a node, where you can not go any deeper, because there is no subtree, this is the place to insert your new element
               (5)Root
      (3)-------^--------(7)
(2)---^----(5)           ^-----(8)
        (5)--^

You start at (5), then go left (since 5 <= 5) to (3), then go right (since 5 > 3) to (5), then you want to go to the left subtree (since 5 <= 5), but you see that there is no subtree, so this is the place to insert your new element (5).

Sto se tice heapa, ne mogu da se setim, ali je trivijalno. Odgledaj ovo: http://www.youtube.com/watch?v=8xJU2TZksWw

Odgovor na temu

Nedeljko
Nedeljko Stefanović

Član broj: 314
Poruke: 8632
*.3gnet.mts.telekom.rs.

+2790 Profil

Re: Par pitanja u vezi binarnih stabala

^{26.01.2013. u 16:58 - pre 136 meseci}

Da, tako se dodaje 13, desno od 12.

Što se tiče hipa, nov element prvo ubaciš na slobodno mesto. To je u ovom primeru desno od 16, tj. pored 10. Onda granu koja povezuje taj list i koren sortiraš, tj. zamenjuješ mesta tom elementu i roditelju sve dok je roditelj manji od deteta penjući se na gore. Recimo, da je bio dodat element 30, najpre bi 30 i 16 zamenili mesta, a potom 30 i 19. Da je umesto 30 dodat 18, zamenili bi mesta samo 18 i 16. Da je kojim slučajem dodat broj 12 u stablo na slici, ne bi bilo zamena.

Evo koda:

Code (c):

#include <stdio.h>

#include <stdlib.h>

typedef struct Node

{

    int element;

    struct Node *left;

    struct Node *right;

} *Tree;

void initializeTree(Tree *tree)

{

    *tree = NULL;

}

void insertInTree(Tree *tree, int element)

{

    if (*tree == NULL) {

        *tree = (Tree) malloc(sizeof(struct Node));

        (*tree)->element = element;

        (*tree)->left = NULL;

        (*tree)->right = NULL;

        return;

    }

    if (element < (*tree)->element) {

        insertInTree(&((*tree)->left), element);

    } else {

        insertInTree(&((*tree)->right), element);

    }

}

void eraseTree(Tree *tree)

{

    if (*tree != NULL) {

        eraseTree(&((*tree)->left));

        eraseTree(&((*tree)->right));

        free(*tree);

        *tree = NULL;

    }

}

typedef struct

{

    int *buffer;

    int capacity;

    int size;

} Heap;

void initializeHeap(Heap *heap)

{

    heap->buffer = NULL;

    heap->capacity = 0;

    heap->size = 0;

}

void setHeapSize(Heap *heap, int size)

{

    heap->buffer = realloc(heap->buffer, sizeof(int)*size);

    heap->capacity = size;

}

int insertInHeap(Heap *heap, int element)

{

    int child, parent;

    if (heap->size == heap->capacity) {

        return 0;

    }

    child = heap->size;

    while (element > heap->buffer[parent = (child - 1) >> 1]) {

        heap->buffer[child] = heap->buffer[parent];

        child = parent;

    }

    heap->buffer[child] = element;

    return 1;

}

void eraseHeap(Heap *heap)

{

    setHeapSize(heap, 0);

}

Nije bitno koji su zaključci izvučeni, već kako se do njih došlo.

Odgovor na temu

MPesic
Beograd

Član broj: 164946
Poruke: 124
*.dynamic.isp.telekom.rs.

+25 Profil

Re: Par pitanja u vezi binarnih stabala

^{26.01.2013. u 18:59 - pre 136 meseci}

Citat:

reiser: Aj posto ti niko nije odgovorio.
How to add node in binary tree

Da proverim da li sam razumeo celu proceduru:
Ako zelim ubaciti 13 proveravam da li je root veci ili manji od 13, ako je veci ide na desnu stranu, ako je manji ide na levu. Posto je manji dalje ga proveravam sa 14 i ponovo ide na levu stranu. Dalje ga uporedjujem sa 10 i saljem ga u jos nizi nivo, i dolazimo do 12 gde ga uporedjujemo i smestamo ga kao desni list cvora 12?

@Nedeljko
Kod hipa ja samo ne razumem koja je razlika izmedju heapsort, maxheap i minheap.
Heap je zapravo nesortiran "skoro potpuno binarno stablo" gde su svi nivoi popunjeni, osim poslednjeg koji je delimicno popunjen sa leva na desno?
Max heap je isto sto i heap samo sortirano stablo?
A min heap?

Odgovor na temu