say2

//
//  main.cpp
//  kruskal_algo
//
//  Created by 김세희 on 2017. 5. 28..
//  Copyright © 2017년 김세희. All rights reserved.
//

#include 
#include 
#include
#include
using namespace std;

#define max 99999
int G[7][7]={{max,8,9,max,max,max,max},{8,max,max,2,11,max,max},{9,max,max,4,max,max,max},{max,2,4,max,max,7
    ,max},{max,11,max,max,max,3,10},{max,max,max,7,3,max,4},{max,max,max,max,10,4,max}};

int represent[7];
int check[7],path[7];
struct Edge{
    int v1,v2;
    int weight;
};
struct comp{
    bool operator()(struct Edge edge1,struct Edge edge2){
        return edge1.weight>edge2.weight;
    }
};
int rep_check(int v){
    if(represent[v]==-1)
        return -1;
    else if(represent[v]==v)
        return v;
    else
        return rep_check(represent[v]);
}
int main(int argc, const char * argv[]) {
    priority_queue,comp> q;
    int i,j,c,p,w,v1,v2,d=0;
    memset(represent,-1,7*sizeof(int));
    struct Edge E;
    for(i=0;i<7;i++){
        for(j=i+1;j<7;j++){
            if(G[i][j]!=max){
                E.v1=j;
                E.v2=i;
                E.weight=G[i][j];
                q.push(E);
            }
        }
    }
    while(!q.empty()){
        v1=q.top().v1;
        v2=q.top().v2;
        w=q.top().weight;
        q.pop();
        if(represent[v1]==-1&&represent[v2]==-1){
            represent[v1]=v1;represent[v2]=v1;
        }
        else if(rep_check(v1)==rep_check(v2))
            continue;
        else{
            if(represent[v1]==-1)
                represent[v1]=rep_check(v2);
            else if(represent[v2]==-1)
                represent[v2]=rep_check(v1);
            else
                represent[rep_check(v2)]=v1;
        }
        d+=w;
        printf("%c - %c diatance : %d total : %d\n",'A'+v1,'A'+v2,w,d);
    }
}

+inverse

//
//  main.cpp
//  kruskal_inverse_algo
//
//  Created by 김세희 on 2017. 5. 28..
//  Copyright © 2017년 김세희. All rights reserved.
//

#include 
#include 
#include
#include
using namespace std;

#define max 99999
int G[7][7]={{max,8,9,max,max,max,max},{8,max,max,2,11,max,max},{9,max,max,4,max,max,max},{max,2,4,max,max,7
    ,max},{max,11,max,max,max,3,10},{max,max,max,7,3,max,4},{max,max,max,max,10,4,max}};
int ch;
int represent[7];
int check[7],path[7];
struct Edge{
    int v1,v2;
    int weight;
};
struct comp{
    bool operator()(struct Edge edge1,struct Edge edge2){
        return edge1.weight,comp> q;
    int i,j,w,v1,v2,d=0,temp;
    memset(represent,0,7*sizeof(int));
    struct Edge E;
    for(i=0;i<7;i++){
        for(j=i+1;j<7;j++){
            if(G[i][j]!=max){
                E.v1=j;
                E.v2=i;
                E.weight=G[i][j];
                q.push(E);
                d+=G[i][j];
            }
        }
    }
    while(!q.empty()){
        v1=q.top().v1;
        v2=q.top().v2;
        w=q.top().weight;
        q.pop();
        temp=G[v1][v2];
        G[v1][v2]=max;G[v2][v1]=max;
        memset(check,0,7*sizeof(int));
        ch=0;
        cir(v1,v2);
        if(!ch){
            G[v1][v2]=temp;
            G[v2][v1]=temp;
            continue;
        }
        d-=w;
        printf("%c - %c diatance : %d total : %d\n",'A'+v1,'A'+v2,w,d);
    }
}

class 선언

@interface myclass : (부모 클래스 : 주로 NSObject씀)

{

@public

int a;

@private

int b;

}

-(void) func_name : (int)A anddata : (int)B;

-(void)func_name2 : (int)A : (int)B;

@end

@implementation myclass

-(void) func_name : (int)A anddata : (int)B

{

a=A;

b=B;

}

-(void)func_name2 : (int)A : (int)B;

{

a=A;

b=B;

}

@end

<사용>

myclass *C;

C=[[myclass alloc]init];

//C=[myclass alloc]

//C=[C init]

[C func_name:1234 anddata:5678];

[C func_name2:1234 :5678];

[C release];

** object C에서는 직접접근 X 포인터로 접근해야함

@property ----

<프로토콜>

메서드정의 -> 클래스에서 메서드 구성(프로토콜에서 정의된 메서드는 전부 구성해야함-@required@optional으로 컨트롤 가능)

xcode : 모르는 단어 help -> command+option+control+?

xcode : header나 정의 파일로 이동 -> command+클릭 / 전반적 설명 -> option+클릭

<멤버메소드와 클래스 메소드>

멤버 메소드

 : 앞에. (-)  , 기능수행, alloc이후 사용가능

클래스 메소드

: 앞에 (+), 안에 alloc이 있음. 메모리 관리 시스템이 사용

<NSstring method>

stringwithstring:nsstring

initwithstring:nsstring

initwithformat

length

isequaltostring

doubleValue

floatvalue

intvalue

integervalue

UTF8string

initwithUTF8String

** NSstring printformat : %@ 

<NSarray method>

initwitharray

initwithobjects

isequaltoarray

objectatindex

count

ex)

NSArray* arr=[[NSArray alloc] initwithobjects:@"A",@"B",nil];

NSLog(@"%@", [arr objectatindex:0]);

<NSMutableArray>

오브젝트를 추가 삭제가능

ex)

NSMutableArray *arr=[[NSMutableArray array];

[arr addobject:@"asdf];

[arr removeobjectatindex:0];

<NSDictionary>

<NSEnumerate>

<NSSet>

allobject

count

equaltoset

objectenumerate

** visual studio 2013 컴파일

string 객체 할당

std::basic_string<char,std::char_traits<char>,std::allocator<char>>::basic_string<char,std::char_traits<char>,std::allocator<char>>(&mystring,'123')

string 객체 해제

std::basic_string<char,std::char_traits<char>,std::allocator<char>>::~basic_string<char,std::char_traits<char>,std::allocator<char>>(&mystring3);

operator new : c++에서만 쓸수 있는 객체지향적이면서 heap에 메모리를 할당하는 malloc과 비슷한 함수(linux기준 new함수 내부에서 malloc을 호출한다고 한다.)

<펌>http://drunkenpsycho.tistory.com/13

3. malloc / new 차이점

  C++에서는 기본적으로 malloc과 new 모두 사용이 가능하다. 그렇다면 차이점은 어떤 것이 있고, 어떠한 경우에 malloc이나 new를 선택하느냐를 알아보자.

  1) malloc은 기본적으로 라이브러리 제공 함수로, 함수 콜을 요청하게 된다. 하지만, new는 C++ 언어에서 제공하는 기본 키워드로, 별도의 라이브러리 추가없이 바로 사용이 가능하다.

  2) malloc은 기본적으로 사이즈를 매개변수로 받고, 리턴타입이 void *형이므로 sizeof 와 캐스트 연산자의 도움을 받아야 쉬운 코딩이 가능하다. 하지만 new는 할당할 타입을 지정하면, 알아서 할당할 타입의 포인터로 넘어오기 때문에, 할당할 타입과 같은 타입의 포인터 변수로 받아오기만 하면 끝이다.

  3) malloc은 메모리를 동적으로 할당하는 것만이 목적이므로 초기값을 지정해 줄 수 없지만, new의 경우는 할당과 동시에 초기화가 가능하다. 

  4) new 키워드는 생성자를 자동으로 호출하게 된다. 생성자는 객체를 자동으로 초기화 해주는 함수로, malloc과 new의 가장 큰 차이점이다. 

  차이점만 본다면, malloc은 없어도 new만 가지고도 쉽게 쉽게 코딩이 가능하다. 하지만 malloc이 필요한 경우 또한 분명히 존재한다. malloc의 경우에는 realloc이라는 함수로 재할당이 가능하지만, new에는 realloc에 대응하는 것이 없기 때문에, 새로 할당 -> 복사 -> 해제 하는 과정을 해야만 가능하다. 하지만, 할당 대상이 어디까지나 객체가 아니라는 전제하에서다. 객체는 반드시 new / delete 를 사용해야된다. 하지만 객체가 아니고, 재할당이 빈번하게 일어나야된다면, malloc과 free가 오히려 더 좋은 선택이 될 수도 있다.

  C에서는 동적 할당이 malloc 밖에 없지만, C++에서는 두가지 중 선택할 수 있으므로, 사용자의 입맛에 따라 어느 것을 사용해도 무방하다. 단, 할당 해제는 반드시 짝을 맞춰서 써야한다. new로 할당 했다면 delete로 해제하고, malloc으로 할당했다면 free로 해제해야만 한다.

** MST(Minimum Spanning Tree)

l  Spanning Tree: acyclic connected subgraph containing all nodes

Ex)

l  MST: a spanning tree with weight less than or equal to the weight of every other spanning tree

l  Kruskal’s algorithm : G(V,E):O(|E|*log|E|)    * Prim’s algorithm

1.     Create a new graph T with the same vertices as G, but no edges (yet)

{1} {2}  {3} {4}  {5}

{1,2}   {3,4}    {5}

{1,2} {3,5} {4}

{1,2,3,5} {4}

{1,2,3,4,5}

1.     Make a list of all the edges in G.

2.     Sort the edges by weight, from lowest to highest

3.     Iterate through the edges in sorted order

For each edge(u,w): If u and w are not connected by a path in T, add (u,w) to T

O(log|E|) using disjointed sets

** Graph Traversal

l  DFS(Depth-First Search)

Void dfs(vertex u){

      u.visit();

      u.visited=true;

      for(each vertex v such that (u,v) ∈ E){

                 if(!v.visited)

                           dfs(v);

      }

}

l  BFS(Breadth-First Search)

void BFS(vertex u){

      u.visit();

      u.visited=true;

      q=new Queue();

      q.enqueue(u);

      while(q is not empty){

                 v=q.dequeue();

                 for (each vertex w s.t (v,w)∈E){

                           if(!w.visited){

                                      w.visit();

                                      w.visited=true;

                                      q.enqueue(w);

                           } //end of if

                 }

      }

** Quick-Union with an array for disjoint sets

{0} {1} {2} {3} {4} {5} {6} {7} {8} {9}

0  1  2  3  4  5  6  7  8  9

l  Union-by-size

l  Find

Ex)

Int find(int x){

      If(array[x] < 0){ return x;}

      Else{

                 Array[x]=find(array[x]);

                 Return array[x];

      }

}

find(7)

array[7]=find(4)

array[4]=find(1)

array[1]=find(0)

void union ( int root1, int root2){

      if(array[root2]<array[root1]){

                 array[root2]+=array[root];

                 array[root1]=root2;

      }else{

                 Array[root1]+=array[root2];

                 Array[root2]=root1;

      }

}

** If we use union-by-size, a single find operation can take O(log u) worst-case time, where u is the number of union operations that took place prior to the find.

-      find the k-th smallest key in a list

** quickselect(index j)

http://m.blog.naver.com/babobigi/220527978173

-      modification of quicksort

-      θ(n) average-case time complexity

1.     start with an unsorted list I of n input items

2.     choose a pivot item v from I

3.     Partition I into unsorted lists I1, I2 and Iv like quicksort

4.     If (j<=|I1|){

Recursively find the item with index j in I1;

Return it;

}else if(j<=|I1|+|Iv|){

      Return the pivot v;

}else{

      Recursively find the item with index j-|I1|-|Iv| in I2;

      Return it;    

}        

1. Insertion sorting (O(n^2))

zzzzzzzzzz

2. Selection sort(O(n^2))

http://luckyyowu.tistory.com/127

배열의 0번쨰 요소부터 끝까지

0 1~N 까지 요소와 비교하면서 최솟값을 넣느다

i i+1~N까지랑 비교하면서 최솟(댓)값으로 하나씩 채워나감

3. Heap Sort

http://proneer.tistory.com/entry/Sort-%ED%9E%99-%EC%A0%95%EB%A0%ACHeap-Sort

<연습문제>

Your program reads its inputs from the input file “heapsort.in”, and outputs its output to the output file “heapsort.out”. In heapsort.in, the first line includes a list containing the elements to be sorted. In heapsort.out, you have to print out the structure of the binary heap used in the heapsort using inorder(I) traversal and preorder(P) traversal whenever the binary heap is changed. Finally, the last line outputs a sorted list of elements. Note that you have to use letter I, P, and O to denote inorder traversal, preorder traversal, and output, respectively.

===========================================================

heapsort.in.

4 7 5 8

=========================================================

heapsort.out

#include
char _arr[1000],temp,cnt;
void inorder(int *arr, int x);
void preorder(int *arr, int x);
void insert(int *arr, int x);
void _sort(int *arr);
int main(){
	int temp,n,in[10000],len=1,sort[10000],loc=0;
	freopen("heapsort.in", "rb", stdin);
	freopen("heapsort.out", "w", stdout);
	while (1){
		temp = scanf("%d", &n);
		if (temp == -1)
			break;
		else{
			in[len++] = n;
			insert(in, len-1);
		}
		cnt = 0;
		inorder(in,1);
		printf("I ");
		for (int j = 0; j < len-1; j++)
			printf("%d ", _arr[j]);
		printf("\n");
		cnt = 0;
		preorder(in,1);
		printf("P ");
		for (int j = 0; j < len-1; j++)
			printf("%d ", _arr[j]);
		printf("\n");
	}
	for (int j = len - 1; j > 0; j--){
		sort[loc++] = in[1];
		in[1] = in[j];
		in[j] = -1;
		if (j == 1)break;
		_sort(in);
		printf("I ");
		cnt = 0;
		inorder(in,1);
		for (int l = 0; l < cnt; l++)
			printf("%d ", _arr[l]);
		printf("\nP ");
		cnt = 0;
		preorder(in,1);
		for (int l = 0; l < cnt; l++)
			printf("%d ", _arr[l]);
		printf("\n");
	}
	printf("O ");
	for (int j = 0; j < len - 1; j++)
		printf("%d ", sort[j]);
}
void _sort(int *arr)
{
	int temp, i = 1, j;
	while (1)
	{
		if (arr[i * 2] < 0 )break;
		if (arr[i * 2 + 1] < 0)
			j = i * 2;
		else if (arr[i * 2] < arr[i * 2 + 1]){
			j = i * 2;
		}
		else
			j = i * 2+1;
		if (arr[i]>arr[j])
		{
			temp = arr[i];
			arr[i] = arr[j];
			arr[j] = temp;
			i = j;
		}
		else
			break;
	}
}
void insert(int *arr, int x){
	while (x != 1){
		if (arr[x / 2] > arr[x]){
			temp = arr[x];
			arr[x] = arr[x / 2];
			arr[x / 2] = temp;
		}
		else
			break;
	}
}
void inorder(int *arr,int x){
	if (arr[x]>0){
		inorder(arr,2*x);
		_arr[cnt++] = arr[x];
		inorder(arr,2*x+1);
	}
}
void preorder(int *arr, int x){
	if (arr[x] > 0){
		_arr[cnt++] = arr[x];
		preorder(arr, 2 * x);
		preorder(arr, 2 * x + 1);
	}
}

4.merge sort(O(nlogn))

http://yujuwon.tistory.com/entry/%EB%B3%91%ED%95%A9%EC%A0%95%EB%A0%ACMerge-Sort

1. start with the unsorted list I of n input items

2. Break Z into two halves Z1 and Z2, having [n/2] and items

3. Sort I1 recursively, yielding the sorted list s1

4. sort I2 recursively, yielding the sorted list s2

5. Merge s1 and s2 into a sorted list S=>O(n)

W(n)=2*w(n/2)+n

W(1)=0

Merge algorithm

1.Let q1 and q2 be two sorted queues.

2.while (neither q1 nor q2 is empty){

item1=q1.front();

item2=q2.front();

move the smaller of item1 and item2 from its present queue to the end of q

}

3. concatenate the remaining non-empty queue(q1 or q2) to the end of q

Complexity of Mergesort

Recurrence relation

W(n)=2W(n/2)+n

W(1)=0

n=2^k

W(2^k)=2W(2^(k-1))+2^k

           =2(2W(2^(k-2)+2^(k-1))+2^k

           =4(W(2^(k-2))+2*2^k

           =2^k(W(2^(k-k))+k*2^k

           =k*2^k

W(n)=nlogn

5. quick sort

http://proneer.tistory.com/entry/Sort-%ED%80%B5-%EC%A0%95%EB%A0%ACQuick-Sort

** Quicksort on arrays

-the fastest known

Comparison-based sort for arrays

-(O(n^2) worst-case running time

-- O(nlogn) average-case running time

Ex)

6. Bucker sort(linear time sort)

simulation

https://www.cs.usfca.edu/~galles/visualization/BucketSort.html

-the number of items : n

-the range of keys : [0, q-1]

-time complexity : θ(q+n)

           * if q∈O(n), θ(q+n)= θ(n)

Ex) q=8, n=8

           Input : (6:a),(7:b),(3:c),(0:d),(3:e)--key,(1:f),(5:g),(0:h)

Queue:

** we need a pointer to find the end of a list in O(1)

Output : (0:d)(0:h)(1:f)(3:c)(3:e)(5:g)(6:a)(7:b)

O(q+n)

*Bucket sort is said to be “stable”.

-- A sort is stable, if items with equal keys come out in the same order in the output as they appeared in the input

7. comparison based sort

https://ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%ED%9E%99

-- merge : merge two binomial trees of the same order

l  To mearge two binomial heaps is analogous to the binary addition of the sizes of the two heaps

l  Insert

1.     Create a new heap containing only this element

2.     Merge the new heap with the original heap

l  Find –min

-      Use a pointer : O(1)

l  Delete – min

1.     Find the root containing min

2.     Remove the root from its binomial tree, and obtain a list of its subtrees

3.     Transform this list of subtrees into a separate binomial heap

4.     Merge the new heap with the original heap except the removed binomial tree

l  Decrese –key

 The same as the binary heap

splay tree simulation

https://www.cs.usfca.edu/~galles/visualization/SplayTree.html

-      Run in O(logn) time on average

시간 복잡도는 평균 log n

-      Any single operation can take theta(n)  time in the worst case

어떠한 연산도 theta(n)시간 안에 처리

-      Any sequence of k splay tree operations, with the tree initially empty and never exceeding n items, takes O(klogn) worst-case time

어떠한 연속된 k splay 트리 연산도 klogn안에 연산

-      Simpler, faster, easier to program

간단하고 빠르고 쉽다 프로그램한테

-      Fast access to entries that have been accessed recently

최근에 접근했던 entry들에 빠르게 접근

-      The most widely used basic data structure invented in the last 30 years

가장 범융적으로 쓰이는 자료구조 30년전에 만든,

-      Used in windows NT(in the virtual memory networking), the gcc compiler, GNU c++ library, unix malloc

windows NT, gcc컴파일러, GNU c++ 라이브러리 , unix malloc에 사용

Find(k)

1.     We walk down the tree until w e  find the entry with the key k, or reach a dead end.

2.     Let x be the node where the search ended, whether it contains the key k or not.

3.     We splay X up the tree through a sequence of rotations, so that X becomes the root of the tree.

-recently accessed entries are near the root of the tree

-improve the balance along the branch of the tree

3 case for splaying

Insert(k)

1.     Insert k just like in an ordinary binary search tree

2.     Splay the new node to the root

Remote(k)

1.     Remove k just like in an ordinary binary search tree

2.     Let x be the node removed from the tree

3.     Splay x’s parent to the root

trianing

Your program reads its inputs from the input file “splay.in”, and outputs its output to the output file “splay.out”. In splay.in, there are two operations; insert(I) and find(F). For instance, “I 0” means, you have to insert “0”into the splay tree. Then, you have to print out the modified splay tree using inorder(I) traversal and preorder(P) traversal. In the below example, there are six insert operations and one find operation. You have to print out the modified splay tree after each operation using two traversal algorithms.

===========================================================

splay.in.

I 0

I 1

I 2

I 3

I 4

I 5

F 1

=========================================================

splay.out

#include
typedef struct tree_node{
	int data;
	struct tree_node *left_child, *right_child,*parent;
}*tree_pointer;					//트리 구조체 선언 
tree_pointer tree;
tree_pointer x;
tree_pointer p, pp;
int arr[1000],cnt=0;
void inorder(tree_pointer ptr);
void preorder(tree_pointer ptr);
tree_pointer insert(tree_pointer tr, int n);
tree_pointer left_rotation(tree_pointer tr);
tree_pointer right_rotation(tree_pointer tr);
tree_pointer splay(tree_pointer object);
tree_pointer find(int n,tree_pointer tr);
int main(){
	FILE *fin = fopen("splay.in", "rb");
	FILE *fout = fopen("splay.out", "w");
	char instruct;
	int n,temp;
	int i = 0;
	tree_pointer k;
	tree = (tree_pointer)malloc(sizeof(struct tree_node));
	while (1){
		temp = fscanf(fin, "%c %d\r", &instruct, &n);
		if (temp == -1)
			break;
		if (instruct == 'I'){
			i++;
			if (i == 1){
				tree->data = n;
				tree->left_child = NULL; tree->right_child = NULL; tree->parent = NULL;
			}
			else{
				k = insert(tree, n);		//insert해준후
				tree = splay(k);			//splay를 해주는데 splay를 하면 루트노드가 바뀌기 떄문에 루트노드를 return값으로 주었다.
			}
		}
		else if (instruct == 'F'){
			k = find(n,tree);				//마찬가지로 find하고
			tree = splay(k);				//splay해준다 
		}
		else{
			fprintf(fout,"WRONG INPUT");
			break;
		}
		cnt = 0;
		inorder(tree);						//inorder preorder 으로 프린트하는 코드이다. 
		fprintf(fout,"I ");
		for (int j = 0; j < i; j++)
			fprintf(fout, "%d ", arr[j]);
		fprintf(fout, "\n");
		cnt = 0;
		preorder(tree);
		fprintf(fout,"P ");
		for (int j = 0; j < i; j++)
			fprintf(fout, "%d ", arr[j]);
		fprintf(fout, "\n\n");
	}
}

void inorder(tree_pointer ptr){				//그동안 많이 했던 inorder알고릐즘!
	if (ptr){
		inorder(ptr->left_child);
		if (ptr->data != -1) arr[cnt++] = ptr->data;
		inorder(ptr->right_child);
	}
}
void preorder(tree_pointer ptr){			//preorder알고리즘!!
	if (ptr){
		if (ptr->data != -1) arr[cnt++] = ptr->data;
		preorder(ptr->left_child);
		preorder(ptr->right_child);
	}
}

tree_pointer insert(tree_pointer tr, char n){  //insert해주는 코드 AVL트리짤때랑 똑같이 짰다
	if (tr == NULL)
	{
		x->data = n;
		x->left_child = NULL;
		x->right_child = NULL;
		tr = x;
		return x;
	}
	else
	{
		if (n < tr->data)
		{
			if (tr->left_child == NULL){
				x = (tree_pointer)malloc(sizeof(struct tree_node));
				x->parent = tr;
			}
			tr->left_child = insert(tr->left_child, n);
		}
		else
		{
			if (tr->right_child == NULL){
				x = (tree_pointer)malloc(sizeof(struct tree_node));
				x->parent = tr;											//parent를 넣어주기 위해 여기에 malloc 코드를 짰다. 
			}
			tr->right_child = insert(tr->right_child, n);
		}
	}
}
tree_pointer splay(tree_pointer object){
	if (object->parent == NULL){
		return object;
	}
	else{		
		if (object->parent->parent == NULL){			//move to root rotation
			if (object->parent->right_child == object){
				object = right_rotation(object);
			}
			else
				object = left_rotation(object);
		}
		else{
			p = object->parent;
			pp = p->parent;
			if (pp->right_child == p&&p->right_child == object){	//zigzig	object->parent부터 로테이션을 돌리고 object를 rotation 돌린다. 
				p = right_rotation(p);
				object = right_rotation(object);
			}
			else if (pp->left_child == p &&p->left_child == object){	//zigzig
				p = left_rotation(p);
				object = left_rotation(object);
			}
			else{														//zigzag	object로테이션을 두번해준다!
				if (object->parent->right_child == object){
					object = right_rotation(object);
					object = left_rotation(object);
				}
				else{
					object = left_rotation(object);
					object = right_rotation(object);
				}
			}
		}
		object = splay(object);
	}
	return object;
}

tree_pointer left_rotation(tree_pointer tr){		//left rotation 코드이다 tr과 tr->parent의 성분을 적절하게 바꾸어 줬다. 
	x = tr->right_child;
	tr->right_child = tr->parent;
	tr->right_child->left_child = x;
	tr->parent = tr->right_child->parent;
	tr->right_child->parent = tr;
	if (tr->parent == NULL)
		return tr;
	else if (tr->parent->right_child == tr->right_child)
		tr->parent->right_child = tr;
	else
		tr->parent->left_child = tr;
	return tr;
}
tree_pointer right_rotation(tree_pointer tr){		//마찬가지로 left rotation과 비슷한 right rotation 코드
	x = tr->left_child;
	tr->left_child = tr->parent;
	tr->left_child->right_child = x;
	tr->parent = tr->left_child->parent;
	tr->left_child->parent = tr;
	if (tr->parent == NULL)
		return tr;
	else if (tr->parent->right_child == tr->left_child)
		tr->parent->right_child = tr;
	else
		tr->parent->left_child = tr;
	return tr;
}
tree_pointer find(int n,tree_pointer tr){			//루트붜 내려가면서 data가 n 인 노드를 찾는다. 
	if (tr->data == n){
		return tr;
	}
	else if (tr->data > n){
		find(n, tr->left_child);
	}
	else if (tr->data < n){
		find(n, tr->right_child);
	}
}

represent 2-3-4 trees as BST with red&black nodes

Red&Black node로 BST(binary search tree)같은 2-3-4트리를 구현할 수 있다.

root always black

루트는 항상 black

-never two red nodes in a row

한열에 두개의 red node가 있을 수 없다

-For each node, all simple paths from the node to descendent leaves contain the same number of black nodes

각 노드에 대하여 노드에서 자식 leave까지의 simple path에는 동일 한 수의 black node가 포함된다

2-3-4 tree    ->    red black tre

동그라미 두번친게 red node

black height

1. Insertion : insert as a red node

Case 1) z=red, z.p=red, y=red

Case 2) z=red, z.p=red y=black

Case3) z=red, z.p=red, y=black

Case4) z=red zp=black z=root

정리 더 잘된 블로그 ㅠ

http://ddmix.blogspot.kr/2015/02/cppalgo-19-red-black-tree.html

http://egloos.zum.com/sweeper/v/900135