연결 리스트: 트리

들어가기 전에

연결 리스트를 활용해서 보다 더 다양한 데이터 구조를 만들 수 있습니다. 연결 리스트에서는 각 요소가 다른 요소를 하나씩만 가리키고 있었습니다. 만약 가리키는 요소가 여러개가 된다면 어떤 장점과 단점이 있을까요? 이번 강의에서는 ‘트리’라는 연결 리스트 기반의 자료 구조를 알아보겠습니다.

 

학습 목표

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

 

핵심 단어

• 트리
• 루트

트리는 연결리스트를 기반으로 한 새로운 데이터 구조입니다.

연결리스트에서의 각 노드 (연결 리스트 내의 한 요소를 지칭)들의 연결이 1차원적으로 구성되어 있다면, 트리에서의 노드들의 연결은 2차원적으로 구성되어 있다고 볼 수 있습니다.

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

 

아래 그림은 트리의 한 예입니다. 나무가 거꾸로 뒤집혀 있는 형태를 생각하면 됩니다.

가장 높은 층에서 트리가 시작되는 노드를 ‘루트’라고 합니다. 루트 노드는 다음 층의 노드들을 가리키고 있고, 이를 ‘자식 노드’라고 합니다. 

 

 

위 그림에 묘사된 트리는 구체적으로 ‘이진 검색 트리’ 입니다.

각 노드가 구성되어 있는 구조를 살펴보면 일정한 규칙을 알 수 있습니다.

먼저 하나의 노드는 두 개의 자식 노드를 가집니다.

또 왼쪽 자식 노드는 자신의 값 보다 작고, 오른쪽 자식 노드는 자신의 값보다 큽니다.

따라서 이런 트리 구조는 이진 검색을 수행하는데 유리합니다.

 

아래 코드에서는 이진 검색 트리의 노드 구조체와 “50”을 재귀적으로 검색하는 이진 검색 함수를 구현하였습니다.

 

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

 

 

생각해보기

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

 

나의 생각 : 이진 검색 트리가 검색이 빠르지만 포인터를 더 많이 사용해서 메모리를 많이 먹는다.

 

출처 : https://www.boostcourse.org/cs112/lecture/119041?isDesc=false 네이버커넥트재단