# Tree
## Binary Search Tree Insert

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

typedef struct node{
	int key;
	struct node *left,*right;
}NODE;
NODE *newNode(int item){
	NODE *node=(NODE*)malloc(sizeof(NODE));
	node->key=item;
	node->left=NULL;
	node->right=NULL;
	return node;
}

NODE *insert(NODE *node,int key){//parent,key
	if(node==NULL)//當這個node空，就插入
		return newNode(key);
	
	if(key<node->key){
		node->left=insert(node->left,key);
	}else if(key>node->key){
		node->right=insert(node->right,key);
	}
	return node;//回傳走過的node
}
NODE *minValueNode(NODE *node){
	NODE *current=node;
	while(current&&current->left!=NULL){//所在的node不為空，且左邊也不為空
		current=current->left;//一直往左走，找到右子樹的最小值
	}
	return current;
	
}

NODE *deleteNode(NODE *node,int key){

	if(node==NULL){
		return node;
	}
	if(key<node->key){
		node->left=deleteNode(node->left,key);
	}else if(key>node->key){
		node->right=deleteNode(node->right,key);
	}
	else{
		//沒有child node或是1個child node，回傳剩下的
		if(node->left==NULL){
			NODE *temp=node->right;
			free(node);
			return temp;
		}
		if(node->right==NULL){
			NODE *temp=node->left;
			free(node);
			return temp;
		}
		//有兩個child
		NODE *temp=minValueNode(node->right);//找出右子樹中的最小值
		
		node->key=temp->key;//用右子樹中的最小值取代原本的node裡面的值，
		//因為會用前面的判斷return值所以可以用call by value。
		node->right=deleteNode(node->right,temp->key);//找出被取代的node，用前面的判斷來free掉
		//具有兩個child的node的Successor或是Predecessor一定是leaf node或是只有一個child，所以一定可以free掉
		
	}
	
	
	return node;//回傳走過的node
	
}

void inorder(NODE *node){
	if(node!=NULL){//如果不等於才要做
		inorder(node->left);
		printf("%d \n",node->key);
		inorder(node->right);
	}
	
}

int main() 
{ 
	/* Let us create following BST 
    	50 
	/	 \ 
	30	 70 
	/ \ / \ 
	20 40 60 80 */
	NODE *root = NULL; 
	root = insert(root, 50); 
	insert(root, 30); 
	insert(root, 20); 
	insert(root, 40); 
	insert(root, 70); 
	insert(root, 60); 
	insert(root, 80); 

	// print inorder traversal of the BST 
	printf("print inorder traversal\n");
	inorder(root); 
	
	printf("\nDelete 20\n"); 
    root = deleteNode(root, 70); 
    printf("Inorder traversal of the modified tree \n"); 
    inorder(root); 
	return 0; 
} 

## AVL Tree

#include<stdio.h> 
#include<stdlib.h> 
typedef struct node{
	int data;
	struct node *left;
	struct node *right;
	int height;
}NODE;
int max(int a,int b){
	
	return (a>b)?a:b;
}
int height(NODE *N){
	if(N==NULL){
		return 0;
	}
	return N->height;
}
NODE *newNode(int key){
	NODE *node=(NODE*)malloc(sizeof(NODE));
	node->left=NULL;
	node->right=NULL;
	node->data=key;
	node->height=1;//height of leaf is 1
	return (node);
}
NODE *rightrotate(NODE *y){
	NODE *x=y->left;
	NODE *T2=x->right;
	
	//perform rotate
	x->right=y;
	y->left=T2;
	
	//update height(AVL tree)
	x->height=max(height(x->left),height(x->right))+1;
	y->height=max(height(y->left),height(y->right))+1;
	//new root
	return x;
}
NODE *leftrotate(NODE *x){
	NODE *y=x->right;
	NODE *T2=y->left;
	//perform rotate
	y->left=x;
	x->right=T2;
	
	//update height
	x->height=max(height(x->left),height(x->right))+1;
	y->height=max(height(y->left),height(y->right))+1;
	//new root
	return y;
}

int getBalance(NODE *root){//T(left)-T(right)
	if(root==NULL)
		return 0;
		
	return height(root->left)-height(root->right);
}
NODE *insert(NODE *node ,int key){
	
	//1.perform normal BST
	if(node==NULL){//arrive the target position
		return (newNode(key));
	}
	if(key<node->data){
		node->left=insert(node->left,key);
	}else if(key>node->data){
		node->right=insert(node->right,key);
	}else{//equal key not allow
		return node;//NOT unchanged node 
	}
	
	//2.update height because insert new node
	node->height=max(height(node->left),height(node->right))+1;
	
	//3.after update height，you need calculate balance
	int balance=getBalance(node);
	//test which rotate case
	//position of node is height=2
	//LL case
	if(balance>1&&key<node->left->data){
		return rightrotate(node);
	}
	//RR case
	if(balance<-1&&key>node->right->data){
		return leftrotate(node);
	}
	//LR case
	if(balance>1&&key>node->left->data){
		node->left=leftrotate(node->left);//lower rotate need update pointer
		return rightrotate(node);
	}
	//RL case
	if(balance<-1&&key<node->right->data){
		node->right=rightrotate(node->right);
		return leftrotate(node);
	}
	 /* return the (unchanged) node pointer */
    return node; //important
}


NODE *minValueNode(NODE *node){
	NODE *current=node;
	while(current&&current->left!=NULL){//所在的node不為空，且左邊也不為空
		current=current->left;//一直往左走，找到右子樹的最小值
	}
	return current;
	
}

NODE *deleteNode(NODE *node,int key){
	//BST delet
	if(node==NULL){
		return node;
	}
	if(key<node->data){
		node->left=deleteNode(node->left,key);
	}else if(key>node->data){
		node->right=deleteNode(node->right,key);
	}
	else{
		//沒有child node或是1個child node，回傳剩下的
		if(node->left==NULL){
			NODE *temp=node->right;
			free(node);
			return temp;
		}
		if(node->right==NULL){
			NODE *temp=node->left;
			free(node);
			return temp;
		}
		//有兩個child
		NODE *temp=minValueNode(node->right);//找出右子樹中的最小值
		
		node->data=temp->data;//用右子樹中的最小值取代原本的node裡面的值，
		//因為會用前面的判斷return值所以可以用call by value。
		node->right=deleteNode(node->right,temp->data);//找出被取代的node，用前面的判斷來free掉
		//具有兩個child的node的Successor或是Predecessor一定是leaf node或是只有一個child，所以一定可以free掉
		// node with only one child or no child 
       
	}
	//2.update height because insert new node
	node->height=max(height(node->left),height(node->right))+1;
	
	//3.after update height，you need calculate balance
	int balance=getBalance(node);
	//test which rotate case
	//position of node is height=2
	//LL case
	if(balance>1&&key<node->left->data){
		return rightrotate(node);
	}
	//RR case
	if(balance<-1&&key>node->right->data){
		return leftrotate(node);
	}
	//LR case
	if(balance>1&&key>node->left->data){
		node->left=leftrotate(node->left);//lower rotate need update pointer
		return rightrotate(node);
	}
	//RL case
	if(balance<-1&&key<node->right->data){
		node->right=rightrotate(node->right);
		return leftrotate(node);
	}
	 /* return the (unchanged) node pointer */
    return node; //important
	
}

void inorder(NODE *node){
	if(node!=NULL){//如果不等於才要做
		inorder(node->left);
		printf("%d ",node->data);
		inorder(node->right);
	}
}


int main() 
{ 
	NODE *root = NULL; 
  
  /* Constructing tree given in the above figure */
  root = insert(root, 10); 
  root = insert(root, 20); 
  root = insert(root, 30); 
  root = insert(root, 40); 
  root = insert(root, 50); 
  root = insert(root, 25); 
  
  /* The constructed AVL Tree would be 
            30 
           /  \ 
         20   40 
        /  \     \ 
       10  25    50 
  */
  
  printf("inorder traversal of the constructed AVL"
         " tree is \n"); 
  inorder(root); 
  root = deleteNode(root, 20); 
  
  printf("\ninorder traversal of the constructed AVL"
         " tree is \n"); 
  inorder(root); 
	return 0; 
} 

## LLRB Tree

#include<stdio.h> 
#include<stdlib.h> 
#include<stdbool.h> 
typedef struct node{
	int data;
	struct node *left;
	struct node *right;
	bool color;
}NODE;
// node is red in color or not. 
int isRed(NODE *node){
	if(node==NULL)//第一個node
		return 0;
	return (node->color==true);//red return 1
}
void swapcolor(NODE *a,NODE *b){//因為沒有修到pointer本身存的address，所以不需要用pointer to pointer
	bool temp=a->color;
	a->color=b->color;
	b->color=temp;
	
}
NODE *newNode(int key){
	NODE *node=(NODE*)malloc(sizeof(NODE));
	node->left=NULL;
	node->right=NULL;
	node->data=key;
	//red is true,black is false 
	node->color=true;//newnode always be red
	return (node);
}
NODE *rightrotate(NODE *y){
	printf("right rotation\n"); 
	
	NODE *x=y->left;
	NODE *T2=x->right;
	
	//perform rotate
	x->right=y;
	y->left=T2;
	//new root
	return x;
}
NODE *leftrotate(NODE *x){
	printf("left rotation!!\n"); 
	NODE *y=x->right;
	NODE *T2=y->left;
	//perform rotate
	y->left=x;
	x->right=T2;
	//new root
	return y;
}


NODE *insert(NODE *node ,int key){
	
	//1.perform normal BST
	if(node==NULL){//arrive the target position，at the leaf
		return (newNode(key));
	}
	if(key<node->data){
		node->left=insert(node->left,key);
	}else if(key>node->data){
		node->right=insert(node->right,key);
	}else{//equal key not allow
		return node;//NOT unchanged node 
	}
	
	//case 1
	if(isRed(node->right) && !isRed(node->left)){
		node=leftrotate(node);
		swapcolor(node,node->left);//不需要return，void
	}
	//case 2
	if(isRed(node->left)&&isRed(node->left->left)){
		node=rightrotate(node);
		swapcolor(node,node->right);
	}
	//case 3
	if(isRed(node->left)&&isRed(node->right)){
		
		node->color= !node->color;//相反的顏色
		//change the color of child
		node->left->color=false;
		node->right->color=false;
	}
	return node;
	
}


void inorder(NODE *node){
	if(node!=NULL){//如果不等於才要做
		inorder(node->left);
		printf("%d ",node->data);
		inorder(node->right);
	}
}


int main() 
{ 
	NODE *root = NULL; 
    /* LLRB tree made after all insertions are made. 
              
    1. Nodes which have double INCOMING edge means 
       that they are RED in color. 
    2. Nodes which have single INCOMING edge means 
       that they are BLACK in color. 
      
        root 
         | 
         40 
       //  \ 
      20    50 
     /  \ 
   10    30 
        // 
       25    */
  
    root = insert(root, 10); 
    // to make sure that root remains 
    // black is color 
    root -> color = false; 
      
    root = insert(root, 20); 
    root -> color = false; 
      
    root = insert(root, 30); 
    root -> color = false; 
     
    root = insert(root, 40); 
    root -> color = false; 
      
    root = insert(root, 50); 
    root -> color = false;  
      
    root = insert(root, 25); 
    root -> color = false;  
  
    // display the tree through inorder traversal. 
    inorder(root); 
      
    return 0; 
}