자료 구조 | 연결리스트(3) 트리

연결 리스트에서는 각 요소가 다른 요소를 하나씩만 가리키고 있었다. 만약 가리키는 요소가 여러 개가 된다면 어떻게 될까.

 

학습 목표

트리의 구조를 설명하고 활용하는 코드를 작성할 수 있다.

 

연결 리스트와 트리

• 트리는 연결 리스트를 기반으로 한 데이터 구조다.
• 연결 리스트에서 각 노드들의 연결이 1차원적이었다면, 트리에서는 2차원적으로 구성되어 있다.
• 각 노드는 일정한 층에 속하고 다음 층의 노드를 가리키는 포인터를 가진다.

 

이진 검색 트리(사진 출처 cs50)

 

• 트리가 시작되는 노드를 루트라고 한다.
• 루트는 다음 층의 노드를 가리키며 이를 자식 노드라고 한다.
• 이진 검색 트리에서 하나의 노드는 두 개의 자식 노드를 가진다.
• 왼쪽 자식 노드는 자신의 값보다 작고, 오른쪽 자식 노드는 크다.

 

이러한 트리 구조는 이진 검색을 수행하는데 유리하다. 이진 검색 트리의 노드 구조체와 숫자 50을 재귀적으로 검색하는 이진 검색 함수를 구현해보자.

 

#include <stdbool.h>

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)이다.

 

생각해보기

값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점은 무엇일까?

• 노드를 추가하거나 검색할 때 기본 연결 리스트에 비해 시간 효율성이 좋다.
• 노드 하나 당 두 개의 노드를 가리켜야 하기 때문에 메모리 사용량이 더 많다.

 

---

이 글은 네이버 부스트 코스 David J. Malan(데이비드 J. 말란) 교수님의 모두를 위한 컴퓨터 과학(CS50 2019) 강의를 수강하고 작성한 글입니다. 본 강좌 내 실습에서는 CS50 Sandbox를 사용합니다.

 

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