Ağaçlar (AVL Ağacı)
//6.Bölüm-Ağaçlar (AVL Ağacı)
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
struct node
{
int key;
struct node *left;
struct node *right;
int height; //Derinlik.
};
int max(int a,int b)
{
return a>b ? a:b; //Doğru ise a, yanlış ise b döndürülür.
}
struct node *newNode(int key)
{
struct node *node=(struct node *)malloc( sizeof(struct node) );
node->key=key;
node->left=node->right=NULL;
node->height=1;
return node;
}
int height(struct node *node)
{
if(node==NULL)
return 0;
return node->height;
}
struct node *rightRotate(struct node *y) //Sol-Sol Durumu.
{
struct node *x=y->left, *T=x->right;
x->right=y;
y->left=T;
y->height=max( height(y->left),height(y->right) )+1;
x->height=max( height(x->left),height(x->right) )+1;
return x;
}
struct node *leftRotate(struct node *x) //Sağ-Sağ Durumu.
{
struct node *y=x->right, *T=y->left;
y->left=x;
x->right=T;
x->height=max( height(x->left),height(x->right) )+1;
y->height=max( height(y->left),height(y->right) )+1;
return y;
}
int getBalance(struct node *node)
{
if(node==NULL) //Ağaç NULL ise.
return 0;
return height(node->left) - height(node->right);
}
struct node *insert(struct node *node,int key)
{
int balance;
if(node==NULL)
return newNode(key);
if(key < node->key)
node->left=insert(node->left,key);
else
node->right=insert(node->right,key);
node->height=max( height(node->left),height(node->right) )+1;
balance=getBalance(node);
if(balance>1 && key < node->left->key) //Sol-Sol Durumu.
return rightRotate(node);
if(balance<-1 && key > node->right->key) //Sağ-Sağ Durumu.
return leftRotate(node);
if(balance>1 && key > node->left->key) //Sol-Sağ Durumu.
{
node->left=leftRotate(node->left);
return rightRotate(node);
}
if(balance<-1 && key < node->right->key) //Sağ-Sol Durumu
{
node->right=rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void preorder_yardimci(struct node *node)
{
if(node!=NULL)
{
printf("%d (%d) ",node->key,node->height);
preorder_yardimci(node->left);
preorder_yardimci(node->right);
}
}
void preorder(struct node *node)
{
preorder_yardimci(node);
printf("\n");
}
struct node *minValueNode(struct node *root)
{
struct node *current=root;
if(current==NULL)
return NULL;
while(current->left)
current=current->left;
return current;
}
struct node *deleteNode(struct node *root,int key)
{
if(root==NULL)
return root;
if(key < root->key) //Sol taraftan gidilir.
root->left=deleteNode(root->left,key);
else if(key > root->key) //Sağ taraftan gidilir.
root->right=deleteNode(root->right,key);
else //Silinen düğüme göre kontroller yapılır.
{
if(root->left==NULL || root->right==NULL) //Düğüm yaprak ise...
{
struct node *temp=root->left ? root->left:root->right; //if true:if false
if(temp==NULL)
{
temp=root;
root=NULL;
}
else
*root=*temp; //İcerikler kopyalanıyor.
/*root->key=temp->key;
root->right=temp->right;
root->left=temp->left*/
free(temp);
}
else
{
struct node *temp=minValueNode(root->right);
root->key=temp->key;
root->right=deleteNode(root->right,temp->key);
}
}
if(root==NULL)
return root;
root->height=max( height(root->left),height(root->right) )+1;
int balance=getBalance(root);
if( balance>1 && getBalance(root->left)>=0 )
return rightRotate(root);
if( balance>1 && getBalance(root->left)<0 )
{
root->left=leftRotate(root->left);
return rightRotate(root);
}
if(balance<-1 && getBalance(root->right)<=0)
return leftRotate(root);
if(balance<-1 && getBalance(root->right)>0)
{ root->right=rightRotate(root->right);
return leftRotate(root);
}
return root;
}
int main(int argc, char** argv)
{
struct node *root=NULL;
root=insert(root,90);
root=insert(root,150);
root=insert(root,173);
root=insert(root,73);
root=insert(root,40);
root=insert(root,80);
root=insert(root,160);
root=insert(root,180);
preorder(root); //90(4) 73(2) 40(1) 80(1) 160(3) 150(1) 173(2) 180(1)
/*
root=deleteNode(root,90);
root=deleteNode(root,160);
root=deleteNode(root,73);
root=deleteNode(root,80);
root=deleteNode(root,40);
root=deleteNode(root,173);
root=deleteNode(root,180);
root=deleteNode(root,150);
*/
getch();
return 0;
}
No comments:
Post a Comment