§ Linked List

1. Intro

// Linked List node
typedef struct _node
{
    int data;
    struct _node *next;
} NODE;

// global variable. 전체 Linked List의 head 
NODE *head; // node pointer

// insert front function
void insert_data(int data)
{
    NODE *temp;
    temp = (NODE*)malloc(sizeof(NODE));
    temp->data = data;
    temp->next = head;
    head = temp;
}

2. Display function

void display(void)
{
    NODE *temp;
    system("clear");
    printf("head");
    // until temp is NULL
    for (temp=head;temp;temp=temp->next)
        printf("->[%d]", temp->data);
    printf("\n");
    getchar();
}

3. Generalized insert function

- Drawback
    1) front insert 만 가능 혹은 맨 앞 삽입과 그렇지 않을 때 코드가 달라짐 
    2) process 에 1개만 존재할 수 있음
       insert function 에서 head가 hard coding 되어있음. 

- Solution
    1) NODE *head 를 NODE head 로 변경하기
       NODE pointer 에서 NODE 로 변경하여 중간에 node를 삽입할 경우를 대비하여 code 일반화
    2) insert function 인자에 NODE pointer 추가
       여러 head가 존재할 수 있도록 지역 변수로 설정할 때에는 반드시 `초기화` 해주어야 함
       ex) NODE head = {0, };

4. Memory dependency

- Drawback
    1) insert_data 에서 malloc을 사용하면 heap 에 잡으라고 강요하는 code

- Solution
    1) memory 할당/해지를 user에게 위임. NODE로 배열 선언하여 stack에 할당해둔다.
       (`memory pooling`: 미리 memory를 잡아둠으로써 속도 개선, 단 memory size가 정해짐.
        하지만 현실 세계에서는 메모리 limit이 존재하기 때문에 그에 맞게 memory를 pooling 해두면 됨.)

※ Stack vs. Heap Memory 영역 (code/data/stack/heap)

code: code, function, control statement

data: global variable, static

heap: dynamic (malloc, new) 속도가 매우 느림!

stack: (temp) local variable, parameter (매개변수), return

Link: Memory_Segment

  1 #include <stdio.h> 
  2 #include <stdlib.h>
  3  
  4 typedef struct _node
  5 {
  6     int data;
  7     struct _node *next;
  8 } NODE;
  9  
 10 void insert_data(NODE *temp, NODE *head)
 11 {
 12     temp->next = head->next;
 13     head->next = temp;
 14 }
 15  
 16 void display(NODE *head)
 17 {
 18     NODE *temp;
 19     printf("[HEAD]");
 20     for(temp=head->next;temp;temp=temp->next)
 21         printf("->[%d]", temp->data);
 22     printf("\n");
 23 }
 24  
 25 int main()
 26 {
 27     int i;
 28     NODE head = {0, };
 29     NODE temps[7];
 30  
 31     for(i=0;i<7;i++)
 32     {
 33         temps[i].data = i+1;
 34         display(&head);
 35         insert_data(temps+i, &head);
 36         getchar();
 37     }
 38     return 0;
 39 }

5. Tail node

- Drawback
    1) display function 혹은 loop 에서 temp로 인해 NULL을 역참조하게 될 경우 
       temp->data // ((*temp).data) 와 동일
       process가 바로 죽게 된다. (매우 위험한 code!) 

- Solution
    1) NULL 참조의 위험성을 배제하기 위해 dummy tail node를 도입하자 ! 
       맨 처음에 head와 tail을 만들고, tail 자체가 자기 자신을 가리키도록 초기화 한다.

  1 #include <stdio.h> 
  2 #include <stdlib.h>
  3  
  4 typedef struct _node
  5 {
  6     int data;
  7     struct _node *next;
  8 } NODE;
  9  
 10 void insert_data(NODE *temp, NODE *head)
 11 {
 12     temp->next = head->next;
 13     head->next = temp;
 14 }
 15  
 16 void display(NODE *head, NODE *tail)
 17 {
 18     NODE *temp;
 19     printf("[HEAD]");
 20     for(temp=head->next;temp!=tail;temp=temp->next) // check temp NODE 
 21         printf("->[%d]", temp->data);
 22     printf("->[TAIL]\n");
 23     getchar();
 24 }
 25  
 26 int main()
 27 {
 28     int i;
 29     NODE tail = {0, &tail};  // tail NODE 
 30     NODE head = {0, &tail};  
 31     NODE temps[7];
 32  
 33     for(i=0;i<7;i++)
 34     {
 35         temps[i].data = i+1;
 36         display(&head, &tail);
 37         insert_data(temps+i, &head);
 38     }
 39     return 0;
 40 }

6. Circular Linked List

- Drawback
    1) 과연 tail이 필요한가? NODE의 크기가 커지면 tail 때문에 memory 낭비 발생하게 된다. 
       tail이 없어도 tail과 동일한 역할을 하도록 head에게 tail 역할 부여 (tail을 없애기 위해 circular 도입) 

- Solution
    1) 맨 처음에 head을 만들고, head 자체가 자기 자신을 가리키도록 초기화 한다.

 16 void display(NODE *head)
 17 {
 18     NODE *temp;
 19     printf("[HEAD]");
 20     for(temp=head->next;temp!=head;temp=temp->next)
 21         printf("->[%d]", temp->data);
 22     printf("->[HEAD]\n");
 23     getchar();
 24 }
 25  

 26 int main()
 27 {
 28     int i;
 29     NODE head = {0, &head};
 30     NODE temps[7];
 31  
 32     for(i=0;i<7;i++)
 33     {
 34         temps[i].data = i+1;
 35         display(&head);
 36         insert_data(temps+i, &head);
 37     }
 38     return 0;
 39 }

7. reserve function

- Drawback
    1) singular linked list 의 한계점 (reverse 방향)   

- Solution
    1) linked list를 reverse 하는 function 을 만들자 !

##### 다시 해보기 !! 
 26 void reverse(NODE *head)
 27 {
 28     NODE *prev = head;
 29     NODE *curr = prev->next;
 30     NODE *next;
 31    
 32     while(curr != head)
 33     {
 34         next = curr->next;
 35         curr->next = prev;
 36  
 37         prev = curr;
 38         curr = next;
 39     }
 40     curr->next = prev;
 41 }

8. Double Linked List

  1 #include <stdio.h>                                                                                                                                                                                            
  2  
  3 typedef struct _node
  4 {
  5     int data;
  6     struct _node *prev;
  7     struct _node *next;
  8 } NODE;
  9  
 10 NODE node;
 11  
 12 void __insert_data(NODE *prev, NODE *temp, NODE *next)
 13 {
 14     temp->next = next;
 15     next->prev = temp;
 16     temp->prev = prev;
 17     prev->next = temp;
 18 }
 19  
 20 void insert_front(NODE *temp, NODE *head)
 21 {
 22     __insert_data(head, temp, head->next);
 23 }
 24  
 25 void insert_back(NODE *temp, NODE *head)
 26 {
 27     __insert_data(head->prev, temp, head);
 28 }

9. Type dependency (void pointer)

  3 typedef struct _node
  4 {
  5     void *data;
  6     struct _node *prev;
  7     struct _node *next;
  8 } NODE;
  9  
 10 NODE node;
 11  
 12 typedef struct
 13 {
 14     char name[20];
 15 } EMPLOYEE;

// loose coupling 의 문제점
// node가 먼저 없어지거나 (dangling pointer) data가 가리키는 정보가 먼저 없어지게 (null 참조) 될 경우
// 문제가 발생할 수 있으므로 node와 data의 할당과 해지 시점을 항상 일치 시켜야 한다.

※ loose coupling : Loose coupling is an approach to interconnecting the components in a system or network so that those components, also called elements, depend on each other to the least extent practicable. Coupling refers to the degree of direct knowledge that one element has of another.

Pros: The benefit is that it's much easier to swap other pieces of code/modules/objects/components when the pieces aren't dependent on one another.

Cons: Dangling pointers arise during object destruction, when an object that has an incoming reference is deleted or deallocated, without modifying the value of the pointer, so that the pointer still points to the memory location of the deallocated memory.

10. Type dependency (sizeof)

node에 data를 넣지 말고, data에 node를 넣어라 ! 
그리하면 type dependency 도 없애고 memory 동기화 문제도 해결할 수 있을 것이다 ~ 

data의 node (prev pointer, next pointer) 들은 서로의 node들을 가리킨다. 
즉, node가 data를 가리킨 게 아니라 node 자체를 가리키기 때문에 data 의존성도 없어지고 
data를 없앨 때 data를 없앨 때, node도 같이 없어지기 때문에 memory 동기화도 없어진다.

  4 typedef struct _node
  5 {
  6     struct _node *prev;
  7     struct _node *next;
  8 } NODE;
  9  
 10 NODE node;
 11  
 12 typedef struct 
 13 {
 14     char name[20]; // padding -> maybe 8 byte * x
 15     NODE list;
 16 } EMPLOYEE;
 17  

 37 void display(NODE *head)
 38 {
 39     EMPLOYEE *emp;
 40     NODE *temp;
 41  
 42     printf ("[HEAD]");
 43     for (temp=head->next; temp != head; temp=temp->next) 
 44     {
 45         emp = (EMPLOYEE*)((char*)temp - (sizeof(EMPLOYEE) - sizeof(NODE)));
 46         printf ("<->[%s]", emp);
 47     }
 48     printf("<->[HEAD]\n");
 49 }
 50  
 51 int main()
 52 {
 53     NODE head = {&head, &head}; // dummy head 
 54     EMPLOYEE emp[M] = { {"TEST1"}, {"TEST2"}, {"TEST3"} };
 55  
 56     int i;
 57  
 58     for (i=0;i<M;i++)
 59     {
 60         insert_back( &emp[i].list, &head );
 61         display(&head);
 62     }
 63  
 64     return 0;
 65 }

11. Type dependency (container_of)

sizeof 를 사용하면 1개의 node에 1개의 list만 가질 수 있다. 
※ pointer 를 숫자로 변경하고 싶으면 int 가 아닌 unsigned long 을 사용 해야 한다 ! (32bit 64bit 에서도 호환 가능)

 12 typedef struct
 13 {    
 14     char name[20];
 15     NODE list1;
 16     NODE list2;
 17      
 18 } EMPLOYEE;

 39 void display(NODE *head)
 40 {    
 41     EMPLOYEE *emp;
 42     NODE *temp;
 43      
 44     printf ("[HEAD]");
 45     for (temp=head->next; temp != head; temp=temp->next) 
 46     {
 47         emp = (EMPLOYEE*)((char*)temp - (unsigned long)(&((EMPLOYEE*)0)->list2)); 
 48         printf ("<->[%s]", emp);
 49     }
 50     printf("<->[HEAD]\n");
 51 }

// container of - 일반화를 하기 위해 macro를 지원하자 ! 
  1 #include <stdio.h>
  2 #define container_of(ptr, type, member) \
  3     (type*)((char*)ptr - (unsigned long)&((type*)0)->member)                                                                                                                                                  
  4      
  5 typedef struct
  6 {    
  7     int a;
  8     int b;
  9     int c;
 10 } AA;
 11      
 12 int main()
 13 {    
 14     AA aa = {1, 2, 3};
 15     int *temp = &aa.c;
 16      
 17     AA *p = container_of(temp, AA, c);
 18     // AA *p = (AA*)((char*)temp - (unsigned long)(&((AA*)0)->c));
 19      
 20     printf ("[TEST] a, b, c : %d %d %d\n", p->a, p->b, p->c);
 21     return 0;
 22 }    

※ gcc -E 를 통해 전처리 확인할 수 있음

12. open source example

macro는 const 를 사용할 수 없음. 
macro에 사용되는 인자는 type을 지정할 수 없고 symbol만 지정할 수 있음

→ const를 흉내내기 위해서 내장 macro를 사용하자 !

  1 #include <stdio.h>                                                                                                                                                                                            
  2  
  3 #define __FOO(x)                    \
  4     printf("data = %d\n", *(x))
  5  
  6 #define FOO(x)                      \
  7     const typeof(*(x)) *__x = x;    \ 
  8     __FOO(__x)
  9

2줄 이상의 macro에서는 do while 문을 사용해야 하지만, 이를 macro에 사용할 경우 do while 문은 제어문이기 때문에 return 값을 받아올 수 없다. 

→ return 값을 갖는 macro를 쓰자 ! do while 문 대신 소괄호를 사용하자 ({ ... }) 이용하기 
그러면 최종 expression 값이 return 값이 된다. ! 

최종 코드에는, 
- macro 에서 안되는 const 에 대한 고려가 포함되어 있음
- macro 에서 안되는 return 값이 안되는 소괄호 문법이 들어가 있음

 13 #define container_of(ptr, type, member) ({                  \ 
 14     const typeof( ((type*)0)->member ) *__mptr = (ptr);     \
 15     (type*)( (char*)__mptr - offsetof(type, member) );})    \

§ Hash

1. Intro

- linked list의 문제점
    1) 최악의 경우 Big O(N), N번 순회해야 한다. 
- hash
    1) bucket pointer로 나눈다. 
    2) 각 node를 insert할 때 hash 값을 계산하여 해당되는 데에 넣는다. 
    3) memory 를 더 사용함으로써 분산 배치를 이용하여 효율을 높인다. 
    4) hash function 이 알고리즘의 성능을 좌지우지한다.

2. Generic hash의 타입 설계 및 구현

- hash heads 
  + 1중 포인터 *first (기본적으로 NULL) 

- hash
  + 1중 포인터 *next 
  + 2중 포인터 **pprev  → why? pointer와 node를 같이 가리키기 위해서

  1 #include <stdio.h>     
  2 #include <stdlib.h>
  3 #define MAX 8
  4         
  5 #define container_of(ptr, type, member)     \
  6     (type*)((char*)ptr - (unsigned long)&((type*)0)->member)
  7         
  8 struct hlist_head {
  9     struct hlist_node *first;
 10 };      
 11         
 12 struct hlist_node {
 13     struct hlist_node *next, **pprev;
 14 };      
 15         
 16 typedef struct {
 17     int no;
 18     struct hlist_node hash;
 19 } data; 
 20         
 21         
 22 void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
 23 {       
 24     struct hlist_node *first = h->first; 
 25         
 26     n->next = first;
 27     if (first)
 28         first->pprev = &n->next;
 29     h->first = n;
 30     n->pprev = &h->first;
 31         
 32 }       
 33         
 34 void display(struct hlist_head *h)
 35 {       
 36     int i;
 37     struct hlist_node *temp;
 38     data *d;
 39     system("clear");
 40         
 41     for (i=0; i<MAX; i++)
 42     {   
 43         printf ("[%d]", i);
 44         for(temp=h[i].first; temp; temp=temp->next)
 45         {
 46             d = container_of(temp, data, hash); 
 47             printf("<->[%d]", d->no);
 48         }
 49         printf ("\n");
 50     }
 51     getchar();
 52 }
 53  
 54 int hash_function(int n)
 55 {
 56     return n % MAX;
 57 }
 58  
 59 int main(void)
 60 {
 61     struct hlist_head heads[MAX] = {0,};
 62     data d[30] = {0,};
 63     int i, sno;
 64  
 65     for (i=0; i<30; i++) {
 66         sno = 1000 + i;
 67         d[i].no = sno;
 68         hlist_add_head( &d[i].hash, &heads[hash_function(sno)]);
 69         display(heads);
 70     }
 71  
 72  
 73     return 0;
 74 }

// hash function
  2 #define GOLDEN_RATIO_PRIME_32 0x9e370001UL 
 ...
 32 unsigned int hash_32(unsigned int val, unsigned int bits)
 33 {    
 34     unsigned int hash = val * GOLDEN_RATIO_PRIME_32;
 35     return hash >> (32 - bits);
 36 }

§ Binary Search Tree

1. Intro

- Terms 
  + root : level = 0
  + level 
  + leaf : level = depth of tree
  + degree : 최대 가지 수 
- 하나의 node에서 다른 node로 가는 방법이 1개만 존재하면 tree, 2개 이상 존재할 경우에는 graph 라고 한다. 폐곡선 (circle) 이 1개라도 존재하면 graph 이다.

  1 #include <stdio.h>
  2 #include <stdlib.h>
  3      
  4 typedef enum { LEFT, RIGHT } FLAG;
  5      
  6 typedef struct _node
  7 {    
  8     int data;
  9     struct _node *left;
 10     struct _node *right;
 11 } NODE;
 12      
 13 NODE *root;
 14      
 15 void insert_data(int data, NODE *ref, FLAG flag)
 16 {    
 17     NODE *temp;
 18     temp=malloc(sizeof(NODE));
 19     temp->data = data;
 20     temp->left = 0;
 21     temp->right = 0;
 22      
 23     if(root == 0)
 24     {
 25         root = temp;
 26         return;
 27     }
 28     if (flag == LEFT) ref->left = temp;
 29     else if (flag == RIGHT) ref->right = temp;                                                                                                                                                                
 30 }    
 31      
 32 int main(void)
 33 {    
 34     insert_data(1, root, LEFT);
 35     insert_data(2, root, LEFT);
 36     insert_data(3, root, RIGHT);
 37      
 38     insert_data(4, root->left, LEFT);
 39     insert_data(5, root->left, RIGHT);
 40      
 41     insert_data(6, root->right, LEFT);
 42     insert_data(7, root->right, RIGHT);
 43      
 44     return 0;
 45 }

2. Tree order traverse

tree는 비선형 자료 구조이므로 전체 순회하기가 어렵다. 
- pre order: root - left - right 
  + 1 2 4 5 3 6 7 

- in order: left - root - right 
  + 4 2 5 1 6 3 7 

- post order: left - right - root
  + 4 5 2 6 7 3 1

  32 // pre order 
 33 void pre_order(NODE *temp)
 34 {    
 35     if (temp == 0) return;
 36      
 37     printf ("%d\n", temp->data);
 38     pre_order(temp->left);
 39     pre_order(temp->right);
 40 }    
 41      
 42 // in order
 43 void in_order(NODE *temp)
 44 {    
 45     if (temp == 0) return;
 46      
 47     in_order(temp->left);
 48     printf("%d\n", temp->data);
 49     in_order(temp->right);
 50 }    
 51      
 52 // post order 
 53 void post_order(NODE *temp)
 54 {    
 55     if (temp == 0) return;
 56      
 57     post_order(temp->left);
 58     post_order(temp->right);
 59     printf("%d\n", temp->data);
 60 }

3. Tree display function

- in_order 순회를 하지만, display 가 거울에 뒤집힌 것처럼 되기 때문에 반대로 순회를 한다 ! 
※ static : 함수 scope 제한적이지만, 전역 변수이기 때문에 함수에서 값을 계속 유지하게 됨.
하지만 이 함수를 여러번 호출하게 되면 static 값이 계속 유지된다. 

- 위 방법은, tree가 세로로 출력되므로 가로로 출력하려면 array 에 넣어주면 된다.
이 때, display 함수와 __display 함수를 쓰게 되는데, 
__display 는 배열에 값을 넣어주는 역할을 하며, return 값으로 2차원 배열을 넘겨준다. 
이 때 int(* __function(type *var))[size] 이런 식으로 하면 2차원 배열을 return 값으로 설정 가능
(고급 C문법 참조)

- 하지만 마찬가지로 배열도 함수를 호출할때마다 초기화 되어야 하므로 static이 아닌 다른 걸 사용해보자 ! 
call by address 로 넘겨주자

 63 // display  
 64 int (*__display(NODE *temp))[MAX]
 65 {    
 66     int i;
 67     static int row = -1;
 68     static int col = 0;
 69     static int tree[MAX][MAX] = {0,};
 70      
 71     if (temp == 0) return tree;
 72      
 73     ++row;
 74     __display(temp->left);
 75     tree[row][col++] = temp->data;
 76     __display(temp->right);
 77     --row; 
 78     return tree;
 79 }    
 80      
 81 void display(NODE *temp)
 82 {    
 83     int (*tree)[MAX];
 84     int i, j; 
 85     tree = __display(temp);
 86      
 87     system("clear");
 88     for(i=0; i<MAX; i++)
 89     {     
 90         for (j=0; j<MAX; j++)
 91         { 
 92             if (tree[i][j]) 
 93                 printf("%3d", tree[i][j]);
 94             else
 95                 printf("%3c", ' ');
 96         } 
 97         printf("\n");
 98     }     
 99     getchar();
100 }

 63 // display final   
 64 void __display(NODE *temp, int (*tree)[MAX], int *row, int *col)
 65 {                 
 66     if (temp == 0) return;
 67                   
 68     ++*row;       
 69     __display(temp->left, tree, row, col);
 70     tree[*row][++*col] = temp->data;
 71     __display(temp->right, tree, row, col);
 72     --*row;       
 73 }                 
 74                   
 75 void display(NODE *temp)
 76 {                 
 77     int row = -1; 
 78     int col = 0;  
 79     int tree[MAX][MAX] = {0,};
 80     __display(temp, tree, &row, &col);
 81                   
 82     system("clear");
 83     int i, j;     
 84                   
 85     for(i=0; i<MAX; i++)
 86     {             
 87         for (j=0; j<MAX; j++)
 88         {         
 89             if (tree[i][j]) 
 90                 printf("%3d", tree[i][j]);
 91             else  
 92                 printf("%3c", ' ');
 93         }         
 94         printf("\n");
 95     }             
 96     getchar();    
 97 }

4. Binary search tree insert

 16 void insert_data(int data)                                                                                                                                                                                    
 17 {    
 18     NODE *temp, *p=root, *prev;
 19     temp = (NODE*)malloc(sizeof(NODE));
 20      
 21     temp->data = data;
 22     temp->right = 0;
 23     temp->left = 0;
 24      
 25     if (root == 0)
 26     {
 27         root = temp;
 28         return;
 29     }
 30      
 31     while(p)
 32     {
 33         prev = p;
 34         if (p->data > data)
 35             p = p->left;
 36         else if (p->data < data)
 37             p = p->right;
 38         else
 39             return;
 40     }
 41      
 42     if (prev->data > data)
 43         prev->left = temp;
 44     else 
 45         prev->right = temp;
 46 }

- 새로 들어오는 값이 root node 값보다 작으면 왼쪽, 크면 오른쪽에
   + 이 경우 O(log2N)  
   + 또한 중복을 허용하지 않으므로 같은 값이 들어오면 바로 return;
 
- insert function
   + curr (pointer)을 root (pointer)부터 (*curr = root) 출발 
   + 하지만 curr을 1중 포인터로 하게 되면 code redundancy 
   + 결론 : curr을 2중 포인터로 한다 ! __**(**curr = &root)**__
   + 이렇게 하면 root == 0 일 때의 비교 할 필요 없음
   + 또한, while(curr) 대신 while(*curr) 을 사용하게 되면 NULL 일때 자동으로 빠져나옴
   + while 문을 수행하는 중에 적절한 자리를 만나면, curr는 NULL 을 가리키는게 아니라 curr 가 가리키는 포인터의 left를 가리키게 됨.
   + left는 NULL 이지만 left의 번지를 가리키기 때문에 curr는 NULL은 아님
   + while 문을 빠져나오면 *curr = temp; 라고만 넣으면 됨. 
   + 즉, curr은 root 라는 pointer를 가리키는 pointer 가 된다.

 48 void insert_data_final(int data)
 49 {    
 50     NODE *temp;
 51     NODE **curr = &root;
 52      
 53     temp = (NODE*)malloc(sizeof(NODE));
 54     temp->data = data;
 55     temp->right = 0;
 56     temp->left = 0;
 57      
 58     while(*curr)
 59     {
 60         if ( (*curr)->data > data ) 
 61             curr = &(*curr)->left;
 62         else if ( (*curr)->data < data )
 63             curr = &(*curr)->right;
 64         else
 65             return;
 66     }
 67     *curr = temp;
 68 }

5. Binary search tree balance

- balance가 맞지 않는 tree는 최악의 경우 O(N) 이며 이는 linked list와 동일하다.
- 따라서 값이 어떻게 들어오더라도, balance를 맞춰주는 게 필요하다.
   + 1차원 sorted 배열로 만들어 주는 __fill 이라는 함수를 구현한다 
   + user interface 겸 bal 함수 : 인자를 채우는 역할
   + __bal 함수는 bal 에서 mid를 찾아서 연결시켜주는 역할을 하는 함수 
   + __bal 함수는 return 값이 NODE* 가 되어야 한다. 
   + 이 때 __bal 함수를 재귀적으로 호출하는데 array 의 size인 n > 0 일때는 temp를 return 하고 그 외에는 0을 return 

- 기존에 들어온 tree를 파괴하여 1차 배열로 정렬 후 다시 balance tree 만들어도 되는데, 이렇게 되면 실시간 balance가 아니다. 주기적으로 balance 함수를 호출할텐데, 호출 전까지는 balance가 맞지 않는다. 
- 또 node가 10만개 되는 code에서는 tree를 다시 파괴하고 다시 만들기에는 overhead가 있다. 
- 새로운 tree들이 연구되기 시작 ! 바로 RB tree

§ Red Black Tree

1. Intro

AVL tree : 가중치를 둬서 balance를 맞추는 tree
2-3 tree /2-3-4 tree
B tree / B+ tree / B* tree
Read Black Tree!!

2. RB Tree insert rule ※ node 의 parent를 parent 라고 하고 그의 parent를 gparent, 그리고 gparent의 또다른 자식을 uncle 이라고 한다.

ground rule !
root 노드로부터 모든 단말 노드로 가는 경로의 검정노드의 수가 같으면 !! balance가 맞는 것으로 간주한다.
첫째, 새로운 노드는 RED 이다. → root 노드 등장으로 둘째 룰로 밀려남.
첫째, root 노드는 언제나 BLACK 이다.
셋째, 부모가 RED 이면 회전한다. → 네번째
- color flip parent color => BLACK gparent color => RED
- 경사를 본다. R-R 경사 => rotate_left(gparent) (rotate 시 이미 자식 node가 있으면 입양을 하고 내려온다.)
- 셋째 룰은, uncle이 있을 경우 해결되지 않으므로 네번째 룰로 밀려난다.
셋째, parent도 RED, uncle도 RED이면 color flip 만 한다.
- color filp parent, uncle => BLACK gparent => RED

정리하면,

유사 밸런스 조건: 단말 노드까지 경로 중 BLACK 노드 수가 같으면 balance가 맞는 것으로 간주한다.
root 노드는 언제나 BLACK 이다.
새로운 노드는 RED 이다.
부모가 RED, 삼촌도 RED 이면 color flip 만 한다.
부모가 RED 이면 color flip 과 rotate 한다.

4. RB Tree insert code

§ Augment Tree

1. Intro

질문 : 알파벳 순서상 5번째 사람은 ?
문제점 : 총 N개 중 N에 가까운 사람을 찾을때에는 시간이 더 오래 걸린다 (최악의 경우 O(N))
해결책 : 증강값을 추가한다 ! (augment) : size 라고 부른다.
- leaf node 에는 augment = 1 로 setting
- parent node 에는 child node 들의 augment의 합 + 1 을 넣는다.
찾고자 하는 index i, i와 비교하는 기준점 k (초기값은 왼쪽 sub-tree의 augment + 1)
기준점 k 보다 i가 작을 때에는 왼쪽으로 이동
- 왼쪽으로 이동할 때에는 i는 그대로 있고, k는 다시 왼쪽 sub tree의 augment + 1 로 다시 setting
기준점 k 보다 i가 클 때에는 오른쪽으로 이동
- 오른쪽으로 이동할 때에는 i := i - k, k 는 왼쪽 sub tree의 augment + 1 로 setting (null 이면 0으로 봄)
기준점 k 와 i가 같을 때 바로 찾고자 하는 곳 !!
이렇게 만들어진 tree를 동적 통계 tree 라고 한다.
이런 알고리즘을 select 알고리즘 이라고 한다.

§ Flexible Array

1. Intro

flexible array 를 pointer로 잡아서, 동적으로 memory 할당

https://github.com/imguru-mooc/opensource-datastructure-algorithm

Data Structure - jjin-choi/study_note GitHub Wiki

§ Linked List

§ Hash

§ Binary Search Tree

§ Red Black Tree

§ Augment Tree

§ Flexible Array

⚠️ GitHub.com Fallback ⚠️

Data Structure - jjin-choi/study_note GitHub Wiki

§ Linked List

§ Hash

§ Binary Search Tree

§ Red Black Tree

§ Augment Tree

§ Flexible Array

⚠️ **GitHub.com Fallback** ⚠️

⚠️ GitHub.com Fallback ⚠️