Anasayfa » Algoritmalar

Kırmızı – Siyah Ağaç Yapıları ( Red – Black Trees) C Kodu

16 Aralık 2011 2.914 kez okundu Yorum yok
1 Star2 Stars3 Stars4 Stars5 Stars (1 oy,5 üzerinden : 5,00 )
Loading...

Merhaba arkadaşlar, bu yazımda daha önceden bahsettiğim red black tree lerin c kaynak kodlarını paylaşacağım.  Eğer red black tree ler ve algoritması hakkında bilgi sahibi olmak istiyorsanız önceki yazımı buradan okuyabilirsiniz.

Red black tree lerin c kaynak kodu şu şekildedir. Kodumuzda binary insert, binary fix up, left rotate, right rotate, inorder print gibi fonksiyonlar bulunmaktadır.

Kodumuzu çalıştırdığımızda iki seçenek sunmaktadır. İster belirlediğimiz sayıları kendimiz girebiliriz, istersek belli bir sayıyı otomatik yerleştirmesini söyleyebiliriz.

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <time.h>
struct node
{
	struct node *parent;
	struct node *left;
	struct node *right;
	int value;
	bool isRed;
};
void yazdir (int * A, int length)
{
		int i;
        for(i=1;i<=length;i++)
                printf("%4d",A[i]);  
		printf("\n\n");
}
void inorder_yazdir(struct node * tree)
{
  if(tree == NULL)
	  return;
  inorder_yazdir(tree->left);
  printf("%4d",tree->value);
  inorder_yazdir(tree->right);
}
void tum_bilgi_yazdir(struct node * tree)
{
  if(tree == NULL)
	  return;
  printf("Node:%4d\nAddress:%d\nParent:%d\nLeft:%d\nRight:%d\nColor:%c\n\n",tree->value,tree,tree->parent,tree->left,tree->right,(tree->isRed==true?'R':'B'));
  tum_bilgi_yazdir(tree->left);
  tum_bilgi_yazdir(tree->right);
}
void right_rotate(struct node *& tree,struct node * new_node)
{
	struct node * y = new_node->left;
	new_node->left = y->right;
	if(y->right!=NULL)
	{
		y->right->parent = new_node;
	}
	y->parent = new_node->parent;
	if(new_node->parent == NULL)
		tree = y;
	else if(new_node == new_node->parent->right)
		new_node->parent->right = y;
	else
		new_node->parent->left = y;
	y->right = new_node;
	new_node ->parent = y;
}
void left_rotate(struct node *& tree,struct node * new_node)
{
	struct node * y = new_node->right;
	struct node * temp;
	new_node->right = y->left;
	if(y->left!=NULL)
	{
		y->left->parent = new_node;
	}
	temp = new_node->parent;
	y->parent = temp;
	if(new_node->parent == NULL)
		tree = y;
	else if(new_node == new_node->parent->left)
		new_node->parent->left = y;
	else
		new_node->parent->right = y;
	y->left = new_node;
	new_node ->parent = y;
}
void rb_insert_fixup(struct node *& tree,struct node *& new_node)
{
	struct node * y;
	while(new_node!= tree && new_node->parent->isRed==true)
	{
		if(new_node->parent==new_node->parent->parent->left)
		{
			y = new_node->parent->parent->right;
			if(y!=NULL && y->isRed==true)
			{
				//case1
				new_node->parent->isRed=false;
				y->isRed=false;
				new_node->parent->parent->isRed= true;
				new_node = new_node->parent->parent;
			}
			else 
			{
				if(new_node == new_node->parent->right)
				{
				//case2
				new_node = new_node->parent;
				left_rotate(tree,new_node);
				}
				//case3
				new_node->parent->isRed = false;
				new_node->parent->parent->isRed = true;
				right_rotate(tree,new_node->parent->parent);
			}
 
		}
		else
		{
			y = new_node->parent->parent->left;
			if(y!=NULL && y->isRed==true)
			{
				//case1
				new_node->parent->isRed=false;
				y->isRed=false;
				new_node->parent->parent->isRed= true;
				new_node = new_node->parent->parent;
			}
			else 
			{
				if(new_node == new_node->parent->left)
				{
				//case2
				new_node = new_node->parent;
				right_rotate(tree,new_node);
				}
				//case3
				new_node->parent->isRed = false;
				new_node->parent->parent->isRed = true;
				left_rotate(tree,new_node->parent->parent);
			}
 
		}
	}
	tree->isRed = false;
}
void rb_insert(struct node *& tree, struct node *& new_node)
{
	struct node * y = NULL;
	struct node * x = tree;
	while(x!=NULL)
	{
		y=x;
		if(new_node->value<x->value)
			x=x->left;
		else
			x=x->right;
	}
	new_node->parent = y;
	if(y==NULL)
		tree = new_node;
	else if(new_node->value<y->value)
		y->left=new_node;
	else
		y->right=new_node;
 
	new_node->left=NULL;
	new_node->right=NULL;
	new_node->isRed=true;
	rb_insert_fixup(tree,new_node);
}
void main()
{
		int *A;
        struct node * tree = NULL;
		struct node * new_node;
		int n;//eleman sayısı
		int i,j,k;		
		int secim;
		srand(time(NULL));
		printf("Rastgele sayilar icin - 1 \n Kendiniz girmek icin - 2 ");
        scanf("%d",&secim);
		if(secim == 1)
		{
			printf("Eklenecek eleman sayisi : ");
			scanf("%d",&n);
			A = (int *)malloc(sizeof(int)*n+1);
			for(i=1;i<=n;i++)
			{
				new_node = (struct node*)malloc(sizeof(struct node));
				new_node->isRed=true;
				new_node->left=NULL;
				new_node->parent=NULL;
				new_node->right=NULL;
				A[i]=rand()%100;
				new_node->value = A[i];
				rb_insert(tree,new_node) ;
			}
		}
		else
		{
			printf("Eklenecek eleman sayisi : ");
			scanf("%d",&n);
			A = (int *)malloc(sizeof(int)*n+1);
			for(i=1;i<=n;i++){
 
				new_node = (struct node*)malloc(sizeof(struct node));
				new_node->isRed=true;
				new_node->left=NULL;
				new_node->parent=NULL;
				new_node->right=NULL;
				printf("Eleman : ");
				scanf("%d",&A[i]);
				new_node->value = A[i];
				rb_insert(tree,new_node);
			}
		}
		printf("Eklenmesi gereken sayilar :");
		yazdir(A,n);
		printf("Tum Bilgiler:\n");
		tum_bilgi_yazdir(tree);
		printf("\n\n");
		//heap_sort(A,n);		
		printf("Inorder Gezinti Sonrasi:");
        inorder_yazdir(tree);	
		printf("\n\n");
 
}

En kısa sürede red black tree lerin java kodlarını da paylaşacağım

<<< Önceki:

Sonraki: >>>


Facebookta Paylaş

Yorum Bırakın!

Yorum yaz, yada kendi sitende trackback (Geri besleme) olarak ekle. Ayrıca RSS ile bu konuya üye olabilirsin. .

Nazik olun. Temiz tutun. Konu dışına çıkmayın. Spam yaratmayın.

Bu tagları kullanabilirsiniz:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>

Bloğumuz gavatarı desteklemektedir. Kendi gavatarınızı edinmek için lütfen Gravatar a üye olun.