[ MPesic @ 25.01.2013. 22:45 ] @
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?
[ reiser @ 26.01.2013. 15:17 ] @
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
[ Nedeljko @ 26.01.2013. 16:58 ] @
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);
}
[ MPesic @ 26.01.2013. 18:59 ] @
Citat:
reiser: Aj posto ti niko nije odgovorio.
How to add node in binary tree

Code:

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

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?
[ Nedeljko @ 26.01.2013. 19:13 ] @
Slično, samo kod min heap-a je roditelj manji ili jednak od potomaka.