AVL stablo

Napisati funkciju koja proverava da li dato binarno pretraživačko stablo zadovoljava AVL svojstvo. AVL stablo je binarno pretraživačko stablo u kome je za svaki čvor razlika visina njegovih levog i desnog podstabla najviše 1.

int stablo_avl(Cvor* koren);

Ulaz

Sa standardnog ulaza se, sve do kraja ulaza (EOF), unosi niz celih brojeva koji se ubacuju u binarno pretraživačko stablo.

Izlaz

Na standardni izlaz ispisati DA ako stablo zadovoljava AVL svojstvo, ili NE ako ne zadovoljava.

Primer

stdin

10 5 15 3 7 12 18

stdout

DA

Primer

stdin

10 5 15 3 7 12 18 1

stdout

DA

Primer

stdin

10 5 15 3 7 12 18 20 25

stdout

NE

Primer

stdin

stdout

DA

Rešenje

stablo.h

#ifndef STABLO_H
#define STABLO_H

#include <stddef.h>

typedef struct Cvor {
    int vrednost;
    struct Cvor* levo;
    struct Cvor* desno;
} Cvor;

/* Ubacivanje */
int stablo_ubaci(Cvor** koren, int x);

/* Uništavanje */
void stablo_unisti(Cvor* koren);

/* Obilasci */
void stablo_infiksno(Cvor* koren, void (*visit)(int));
void stablo_prefiksno(Cvor* koren, void (*visit)(int));
void stablo_postfiksno(Cvor* koren, void (*visit)(int));

/* Pretraga */
Cvor* stablo_pretrazi(Cvor* koren, int x);

/* Brisanje */
void stablo_obrisi(Cvor** koren, int x);

/* Analiza */
size_t stablo_velicina(Cvor* koren);
size_t stablo_visina(Cvor* koren);

#endif

main.c

#include <stdio.h>
#include <stdlib.h>
#include "stablo.h"

int stablo_avl_stara(Cvor* koren)
{
	if (!koren) return 1; // Prazno stablo je AVL

	int visina_levo = stablo_visina(koren->levo);
	int visina_desno = stablo_visina(koren->desno);

	// Provera AVL svojstva za trenutni čvor
	if (abs(visina_levo - visina_desno) > 1)
		return 0;

	// Rekurzivna provera za levo i desno podstablo
	return stablo_avl_stara(koren->levo) && stablo_avl_stara(koren->desno);
}

int stablo_avl_pomocna(Cvor* koren, int* visina)
{
	if (!koren) {
		*visina = 0;
		return 1; // Prazno stablo je AVL
	}

	int visina_levo = 0, visina_desno = 0;

	// Rekurzivna provera za levo i desno podstablo
	int avl_levo = stablo_avl_pomocna(koren->levo, &visina_levo);
	int avl_desno = stablo_avl_pomocna(koren->desno, &visina_desno);

	// Postavljanje visine trenutnog čvora
	*visina = 1 + (visina_levo > visina_desno ? visina_levo : visina_desno);

	// Ako bilo koje podstablo nije AVL, onda ni trenutno stablo nije AVL
	if (!avl_levo || !avl_desno) 
		return 0;

	// Provera AVL svojstva za trenutni čvor
	if (abs(visina_levo - visina_desno) > 1)
		return 0;

	return 1;
}

int stablo_avl(Cvor* koren)
{
	int visina = 0;
	return stablo_avl_pomocna(koren, &visina);
}

int stablo_avl(Cvor *koren) 
{
	if (!koren) {
		return 1;
	}

	int visina_levo = stablo_visina(koren->levo);
	int visina_desno = stablo_visina(koren->desno);

	if (abs(visina_levo - visina_desno) > 1) {
		return 0;
	}

	return stablo_avl(koren->levo) && 
		   stablo_avl(koren->desno);
}

int main(void)
{
	Cvor *koren = NULL;

	int x;
	while (scanf("%d", &x) != EOF) {
		stablo_ubaci(&koren, x);
	}

	if (stablo_avl(koren))
		printf("DA\n");
	else
		printf("NE\n");

	stablo_unisti(koren);

	return 0;
}

stablo.c

#include "stablo.h"
#include <stdlib.h>

/* ---------- pomoćne ---------- */

static Cvor* cvor_novi(int x) {
    Cvor* n = (Cvor*)malloc(sizeof(Cvor));
    if (!n) return NULL;
    n->vrednost = x;
    n->levo = NULL;
    n->desno = NULL;
    return n;
}

/* ---------- uništavanje ---------- */

void stablo_unisti(Cvor* koren) {
    if (!koren) return;
    stablo_unisti(koren->levo);
    stablo_unisti(koren->desno);
    free(koren);
}

/* ---------- ubacivanje: BST ---------- */
/* Dogovor: x < vrednost ide levo, inače desno */

int stablo_ubaci(Cvor** koren, int x) {
    if (!koren) return 0;

    while (*koren) {
        if (x < (*koren)->vrednost)
            koren = &(*koren)->levo;
        else
            koren = &(*koren)->desno;
    }

    *koren = cvor_novi(x);
    return (*koren != NULL);
}

/* ---------- obilasci ---------- */

void stablo_infiksno(Cvor* koren, void (*visit)(int)) {
    if (!koren) return;
    stablo_infiksno(koren->levo, visit);
    visit(koren->vrednost);
    stablo_infiksno(koren->desno, visit);
}

void stablo_prefiksno(Cvor* koren, void (*visit)(int)) {
    if (!koren) return;
    visit(koren->vrednost);
    stablo_prefiksno(koren->levo, visit);
    stablo_prefiksno(koren->desno, visit);
}

void stablo_postfiksno(Cvor* koren, void (*visit)(int)) {
    if (!koren) return;
    stablo_postfiksno(koren->levo, visit);
    stablo_postfiksno(koren->desno, visit);
    visit(koren->vrednost);
}

Cvor *stablo_pretrazi(Cvor *koren, int x)
{
    if (!koren) return NULL;

    if (koren->vrednost == x)
        return koren;
    else if (x < koren->vrednost)
        return stablo_pretrazi(koren->levo, x);
    else
        return stablo_pretrazi(koren->desno, x);
}

void stablo_obrisi(Cvor **koren, int x)
{
    if (!koren || !*koren) return;

    if (x < (*koren)->vrednost) {
        stablo_obrisi(&(*koren)->levo, x);
        return;
    } 
    
    if (x > (*koren)->vrednost) {
        stablo_obrisi(&(*koren)->desno, x);
        return;
    }

    // Čvor za brisanje pronađen
    if (!(*koren)->levo) {
        Cvor *temp = (*koren)->desno;
        free(*koren);
        *koren = temp;
        return;
    }
    
    if (!(*koren)->desno) {
        Cvor *temp = (*koren)->levo;
        free(*koren);
        *koren = temp;
        return;
    }

    // Čvor sa dva deteta: nađi najmanji u desnom podstablu
    Cvor *parent = *koren;
    Cvor *successor = (*koren)->desno;
    while (successor->levo) {
        parent = successor;
        successor = successor->levo;
    }

    // Kopiraj vrednost naslednika
    (*koren)->vrednost = successor->vrednost;

    // Obriši naslednika
    if (parent->levo == successor)
        parent->levo = successor->desno;
    else
        parent->desno = successor->desno;
    free(successor);
}

/* ---------- size / height ---------- */

size_t stablo_velicina(Cvor* koren) {
    if (!koren) return 0;
    return 1
         + stablo_velicina(koren->levo)
         + stablo_velicina(koren->desno);
}

size_t stablo_visina(Cvor* koren) {
    if (!koren) return 0;
    size_t hl = stablo_visina(koren->levo);
    size_t hr = stablo_visina(koren->desno);
    return 1 + (hl > hr ? hl : hr);
}