6. 자료구조 2

6) 연결 리스트: 트리

• 트리 : 연결리스트를 기반으로 한 새로운 데이터 구조

• 트리에서의 노드들의 연결은 2차원적으로 구성 (연결리스트는 1차원)

• 각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가짐

• 이진 검색을 수행하는데 유리하면서 유동성 유지.

• 가장 높은 층에서 트리가 시작되는 노드 : ‘루트’
• 루트 노드는 다음 층의 노드들을 가리킴 : ‘자식 노드’

[이진 검색 트리 노드 구조체와 재귀적 이진 검색 함수]

//이진 검색 트리의 노드 구조체
typedef struct node
{
    // 노드의 값
    int number;

    // 왼쪽 자식 노드
    struct node *left;
 
   // 오른쪽 자식 노드
    struct node *right;
} node;

// 이진 검색 함수 (*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{
    // 트리가 비어있는 경우 ‘false’를 반환하고 함수 종료
    if (tree == NULL)
    {
        return false;
    }
    // 현재 노드의 값이 50보다 크면 왼쪽 노드 검색
    else if (50 < tree->number)
    {
        return search(tree->left);
    }
    // 현재 노드의 값이 50보다 작으면 오른쪽 노드 검색
    else if (50 > tree->number)
    {
        return search(tree->right);
    }
    // 위 모든 조건이 만족하지 않으면 노드의 값이 50이므로 ‘true’ 반환
    else {
        return true;
    }
}

검색 실행 시간과 노드 삽입 시간은 모두 O(log n)

7) 해시 테이블

해시 테이블 : ‘연결 리스트의 배열’

• 해시 함수를 통해서 바구니에 값을 나눠 담음. 각 바구니 안에 값들는 연결리스트로 이어짐.

• 이상적 해시 테이블의 검색시간 : O(1)
  why? 각 바구니에 하나의 값들만 담겼을 때.
• 현실적으로 최악의 상황에 모든 값들이 한 바구니에 담기면 : O(n)

--> 일반적으로 최대한 많은 바구니를 만드는 해시 함수를 사용하기 때문에 실행시간은 O(1)에 가까움.

8) 트라이

트라이 : 노드가 배열로 이루어져 있는 트리형태의 자료구조

• 이론적으로 검색시간 : O(n)
  트라이에서 값을 검색하는데 걸리는 시간은 ‘문자열의 길이’에 의해 한정
• O(1)이나 마찬가지

9) 스택, 큐, 딕셔너리

큐

• 값이 아래로 쌓이는 구조
• 선입 선출 | FIFO
  가장 먼저 들어온 값이 가장 먼저 나감(은행)
• 배열이나 연결 리스트를 통해 구현 가능

스택

• 값이 위로 쌓이는 구조
• 후입 선출 | LIFO
  가장 나중에 들어온 값이 가장 먼저 나감(뷔페 접시)
• 배열이나 연결 리스트를 통해 구현 가능

딕셔너리

• key : value
• ‘해시 테이블’과 동일한 개념