6: 자료구조-5(연결 리스트: 트리)

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

 

이진 탐색 트리

- 연결 리스트에서의 요소들의 연결은 1차원적으로 구성되어 있고, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있음

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

- 가장 높은 층에서 트리가 시작되는 노드 ‘루트’

- 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 함

- 트리의 노드들은 최대 두 개의 자식 노드를 가짐. 이진법의 이진을 따와서 최대 2라는 것을 표현

 

- 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 자신의 값보다 큼 이런 트리 구조는 이진 검색을 수행하는 데 유리함

- 트리를 탐색하려면 트리의 가장 위에 있는 루트라는 노드만 알려주면 트리의 모든 곳으로 갈 수 있음

- 트리에서 7개의 요소가 있다면 어떤 값을 찾는 데에는 3단계밖에 걸리지 않음 -> 필요한 단계의 수는 O(log n)

- 이진 검색 트리를 활용했을 때 검색 실행 시간과 노드 삽입 시간은 모두 O(log n)

---

이진 검색 트리의 노드 구조체

 

typedef struct node
{ 
    // 노드의 값
    int number;
    
    // 왼쪽 자식 노드
    struct node *left;
    
    // 오른쪽 자식 노드
    struct node *right;
}
node;

---

50을 재귀적으로 검색하는 이진 검색 함수를 구현함(50이 트리에 있으면 true 아니면 false를 받는 코드 작성)

 

// 트리의 루트의 주소를 입력 받음
// 이진 검색 함수(*tree는 이진 검색 트리를 가리키는 포인터)
bool search(node *tree)
{    
    // 트리가 비어있는 경우 “false”를 반환하고 함수 종료
    if (tree == NULLL)
    {
        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 // (50 == tree->number)
    {
        return true; 
    }
}

 

트리는 2차원적이고 재귀적으로 정의되어 있는데 이 의미는 어떤 노드에서도 왼쪽이 더 작고 오른쪽이 더 크다는 것

 

 

https://www.boostcourse.org/cs112/joinLectures/41307

모두를 위한 컴퓨터 과학 (CS50 2019)