#include #include typedef enum {RED, BLACK} node_color; typedef struct node{ int value; node_color color; struct node *left, *right, *parent; }node; void allocation_check(void* ptr) { if (!ptr) { printf("Greska pri alokaciji!\n"); exit(1); } } node* create_node(int val) { node *new_node = malloc(sizeof(node)); allocation_check(new_node); new_node->value = val; new_node->color = RED; new_node->parent = NULL; new_node->left = NULL; new_node->right = NULL; return new_node; } /* ~~~ TELEVISA PRESENTA ~~~ */ void l_rotation(node *father) { node *son = father->right; node *grandpa = father->parent; // Levo podstablo od sina prelazi kod oca father->right = son->left; if (son->left != NULL) son->left->parent = father; // Sin ide iznad oca son->left = father; son->parent = grandpa; father->parent = son; // Deda pokazuje na sina (ako deda postoji) if (grandpa != NULL) { if (grandpa->left == father) grandpa->left = son; else grandpa->right = son; } } void r_rotation(node *father) { node *son = father->left; node *grandpa = father->parent; father->left = son->right; if (son->right != NULL) son->right->parent = father; son->right = father; son->parent = grandpa; father->parent = son; if (grandpa != NULL) { if (grandpa->left == father) grandpa->left = son; else grandpa->right = son; } } void rebalance_tree(node **root, node** temp) { // Proveravamo da li vaze pravila RB stabla i korigujemo ako ne vaze node *son = *temp; node *father = son->parent; while(1) { // 1. Root mora da je crn if (father == NULL) { son->color = BLACK; break; } // 2. Ako je dete crveno, roditelj ne sme da bude crven if (father->color == BLACK) { break; } // Otac i sin su crveni - Nadjimo ujaka node *grandpa = father->parent; // Ako je otac crven, znaci da nije root, odnosno i deda postoji node *uncle = (grandpa->left == father) ? grandpa->right : grandpa->left; // ujak moze biti i NULL if (uncle != NULL && uncle->color == RED) { // Ujak crven - promeni ujaku, ocu i dedi boje grandpa->color = RED; uncle->color = father->color = BLACK; // Proveravamo da li pravila nisu narusena i za dedu - ostajemo u while-u son = grandpa; father = son->parent; continue; } else { // Ujak crn ili NULL - trougao koji dovodimo do linije if(grandpa->right == father && father->left == son) { r_rotation(father); node *tmp = son; son = father; father = tmp; } else if(grandpa->left == father && father->right == son) { l_rotation(father); node *tmp = son; son = father; father = tmp; } // Ujak crn ili NULL - linija na levo if (grandpa->left == father && father->left == son) { father->color = BLACK; grandpa->color = RED; r_rotation(grandpa); } // Ujak crn ili NULL - linija na desno else if(grandpa->right == father && father->right == son) { father->color = BLACK; grandpa->color = RED; l_rotation(grandpa); } break; } } // Ispravi root ako se promenio while ((*root)->parent != NULL) *root = (*root)->parent; } void add_node(node **root, int value) { // Krecemo se kroz stablo i nalazimo mesto za novi cvor node **temp = root; node *father = NULL; while (*temp != NULL) { father = *temp; if (value < (*temp)->value) temp = &((*temp)->left); else if (value > (*temp)->value) temp = &((*temp)->right); else return; } *temp = create_node(value); (*temp)->parent = father; rebalance_tree(root, temp); } void create_tree(node **root,int* init_values, int n) { for(int i=0; ileft); free_tree(&(*root)->right); free(*root); *root = NULL; } void visualize_tree(node* tree, int level) { if (tree == NULL) return; visualize_tree(tree->right, level + 1); for(int i = 0; i < level; i++) printf(" "); //printf("%3d,(%c)\n", tree->value, tree->color == RED ? 'R' : 'B'); // Radi lepseg prikaza, nije neophodno if (tree->color == RED) printf("\033[91m%3d,(R)\033[0m\n", tree->value); else printf("\033[97m%3d,(B)\033[0m\n", tree->value); visualize_tree(tree->left, level + 1); } int main() { node *root = NULL; int init_values [] = {10,20,30,40,50}; // Napravi stablo create_tree(&root, init_values, sizeof(init_values)/sizeof(int)); // Ispisi stablo visualize_tree(root, 1); printf("----------------------\n"); // Dodaj nove elemente int val; while(scanf("%d",&val) == 1) { add_node(&root,val); visualize_tree(root, 1); printf("----------------------\n"); } // Obrisi stablo free_tree(&root); return 0; }