1. 연결리스트

먼저 배열은 임의접근을 할 수있어서 이진탐색을 쓸수있습니다.
그러나 연결리스트는 역동성을 가지며 임의접근이 불가합니다. 즉, 이진탐색이 불가합니다.

기존의 연결리스트는 하나의 포인터를 갖고있던 반면 두개의 포인터를 가지게 하여 이진탐색을 할 수 있도록 만들 수 있습니다.
이것을 트리라고 하며 이진탐색 트리입니다.

모든 노드의 왼쪽 자식이 더 작으며, 모든 노드의 오른쪽 자식이 더 크다는 특징을 가집니다.

<노드에 포인터가 2개>

typedef struct node
{
	int number;
    struct node *left;
    struct node *right;
}
node;

이진탐색이 가능하며 포인터를 이용하였기에 역동성도 가집니다.

트리를 탐색하려면, 트리의 가장 위에 있는 루트라는 노드만 알려주면 됩니다.
재귀를 이용하여 특정 숫자를 찾는 코드입니다.

bool search(node *tree) 
{
	if(tree==NULL){
    	return false;
    }
    else if (50 < tree ->number){ 
    	return search(tree->left);
    }
    else if (50 > tree ->number){ 
    	return search(tree->right);
    }
    else {
    	return true;
    }
}

이진 탐색 트리의 탐색 시간의 상한은 O(log n) 입니다.
추가 또한 O(logn)이다.

2. 해시 테이블

해시 테이블은 배열과 연결리스트의 조합입니다.

해리포터에 나오는 이름들을 해시테이블에 넣어보면
harry, hermiony, hagrid가 동일한 bucket인 h 에 들어간다.

동일한 이름은 연결리스트를 통해서 계속 늘릴 수 있다.

해시함수는 인덱싱을 하는데 사용하는 배열로 이름을 넣어주면 어느 바구니로 가야하는 지 알려주는 함수를 의미한다. 입력값을 받아 출력값을 만든다.

만약 모든 이름이 h로 시작한다면 이런 이름의 첫글자로 indexing하는 것은 꽤나 바보 같은 일이다.

이때 첫 두글자를 이용한다면?

바구니가 26*26개가 필요하고 그래도 충돌할 수 있다.

그러면 첫 세단어로???
이렇게 생각해도 똑같은 이름만 많이 들어온다면 O(n)이다.

시간과 공간의 trade를 통해 균형이 잡히는 것이 중요한다.

---

이상적인 해시함수는 이름표들이 각기 다른 결과를 만들어 충돌을 방지하는 것이다.
이상적인 해시는 O(1)으로 일정한 실행시간을 가질 수 있다.

그러나 그렇지 않은 경우, 모든 이름이 단 하나의 바구니에 담긴다면 O(n)이 된다.

3. 트라이

트라이는 어떤 자원을 위해 다른 자원을 소비하는 패턴을 가진다.
많은 메모리가 필요하지만 검색하는데 일정한 실행 시간을 가진다.

각각의 노드가 배열로 이루어진 트리로 여기에 이름을 하나 저장하고 싶다면 이름의 모든 글자를 봐야합니다.

harry, hagrid, hermione를 넣으면 최소 하나의 노드를 나누어 가집니다.

소요시간은 이름의 길이만큼입니다.
즉 search와 insert에 o(1)이라는 상수시간이 필요합니다.

이에대한 대가는 메모리입니다.

4. 큐, 스택, 딕셔너리

1) 큐

큐는 (FIFO) first in first out으로 먼저 들어간 것이 먼저 나온다.
ex) 놀이공원에서 놀이기구 타기

선입선출의 특징을 가진 자료구조이다.
큐에 들어가는 것을 enqueue : 줄에 들어선다. dequeue : 줄을 빠져나온다.

2) 스택

스택은 (LIFO) last in first out으로 나중에 들어온 것이 첫번째로 나온다.
ex) gmail의 최근 받은 메일함

후입선출의 특징을 가진 자료구조이다.

push : 스택에 넣는다. pop : 스택에서 뺀다.

3) 딕셔너리

key - value 쌍

이쪽 부분은 설명이 별로 없다.

5. 퀴즈 -!

1) int 2개의 배열을 5개를 담을 배열로 확장하고 싶다.올바른ralloc 코드는?

int tmp = reallc(list, 5sizeof(int));

2) 배열과 리스트가 있을 때 첫번째 값이 아닌 위치에 접근하려고 할 때 무엇이 더빠른가?

배열이 더 빠릅니다.

3) (*n).number와 동일한 의미의 코드는?

n->number

4) 연결리스트에서 값을 검색하는데 걸리는 시간은?

O(n)

5) 트리의 최상위 노드를 뭐라고 하는가?

루트 노드

6) 해시 테이블에 사용되는 함수의 이름은?

해시 함수

7) 길이가 10인 문자열이 있을때 트라이에 저장하는 경우 몇개의 노드를 이어줘야 할까?

10개

8) 선입선출의 자료구조는?

큐

9) node를 구조체로 정의할 때 next포인터를 어떻게 정의하나요?

struct node * next;

10) 프로그램에 이름과 전화번호를 저장하는 자료구조를 구현할 때 고려해야할 점이 아닌 것은 ?

메모리 주소 표기법