6) 연결 리스트: 트리
트리란
트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다.
연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다.
각 노드는 일정한 층에 속하고, 다음 층의 노드들을 가리키는 포인터를 가지게 됩니다.
트리 예시
예시를 보면 이해가 쉽습니다.
가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 합니다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 합니다.
위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’ 입니다.
- 먼저 하나의 노드는 두 개의 자식 노드를 가집니다.
- 또 왼쪽 자식 노드는 자신의 값 보다 작고,
- 오른쪽 자식 노드는 자신의 값보다 큽니다.
따라서 이런 트리 구조는 이진 검색을 수행하는데 유리합니다.
구현
이진 검색 트리의 노드 구조체와 “50”을 재귀적으로 검색하는 이진 검색 함수를 구현
//이진 검색 트리의 노드 구조체
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) 입니다.
검색 실행 시간과 노드 삽입 시간이 같은 이유는 검색을 마치고 삽입하기 때문이며, 시간은 이진 탐색과 같다.
생각해보기
값을 검색할 때 이진 검색 트리가 기본 연결 리스트에 비해 가지는 장점과 단점은 무엇이 있을까요?
장점은 속도가 빠르다.(
O(n)->O(log n))단점으로는 각 노드마다 포인터를 2개씩 가져야 하므로 메모리를 조금 더 사용하게 된다는 점이 있다.
note
written by CaesiumY