Untitled
unknown
plain_text
2 months ago
2.5 kB
1
Indexable
Never
#include <stdio.h> #include <stdlib.h> //1=black //0=red struct node { int data; struct node *parent; struct node *left; struct node *right; int color; }; // Function to perform right rotation void rightrotate(struct node* x) { struct node* y = x->left; x->left = y->right; if (y->right != NULL) { y->right->parent = x; } y->parent = x->parent; if (x->parent == NULL) { // If x was the root, update the root to y root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->right = x; x->parent = y; } // Function to perform left rotation void leftrotate(struct node* x) { struct node* y = x->right; x->right = y->left; if (y->left != NULL) { y->left->parent = x; } y->parent = x->parent; if (x->parent == NULL) { // If x was the root, update the root to y root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; x->parent = y; } insert(struct node* k) { struct node* u; while (k->parent->color == 1) { if (k->parent == k->parent->parent->right) u = k->parent->parent->left; if(u->color == 1) { u->color=0; k->parent->color=0; k->parent->parent->color=1; k=k->parent->parent; } else{ if (k == k->parent->left) { k=k->parent; rightrotate(k); } k->parent->color = 0; k->parent->parent->color =1; leftrotate(k->parent->parent) } }else{ u = k->parent->right; if(u->color == 1) { u->color = 0; k->parent->color=0; k->parent->parent->color=1; k = k->parent->parent; } else{ if(k== k->parent->right) { k=k->parent; leftrotate(k); } k->parent->color=0; k->parent->parent->color=1; rightrotate(k->parent->parent); } } if(k==root) { break; } } root->color=0 int main () { insert(58); insert(66); insert(13); insert(33); insert(44); insert(51); return 0 ; }