비선형 자료구조 - 트리(Tree)란 무엇이고 왜 이진 트리를 알아야 하는가?

시작하며.

자료구조를 공부하면서 선형 자료구조는 어떻게 어떻게 이해하겠는데
비선형 자료구조는 정말 멘탈 바사삭이다.
그래서 트리부터 천천히 정리하며 기록하려 한다.

 

트리(Tree)란 무엇인가?

노드와 링크로 구성된 자료구조, 그래프의 일종, Cycle 없음
계층적 구조를 나타낼 때 사용(폴더 구조, 조직도, 가계도 등)
데이터가 순차적으로 저장되지 않기 때문에 비선형 자료구조
트리의 요소가 여러 수준으로 배열되는 계층 구조

트리는 나무.
나무에는 잎, 가지, 뿌리 및 줄기가 있다
잎을 따라가면 줄기가 있고 이 줄기는 결국 뿌리로 향한다.
트리 구조는 이런 나무의 모습을 그대로 구조화한 모델이다.

뿌리에 해당하는 제일 상위의 노드는 루트 노드라고 하며
줄기에 해당 하는 에지(링크, 브랜치)는 노드 간의 연결선으로 간선이라고도 한다.
아래 그림을 통해 각 명칭과 구조와 의미를 확인해보자.

노드(Node) - 트리 구조의 자료 값을 담고 있는 단위
에지(Edge) - 노드 간의 연결선 (간선)

루트(Root) 노드 - 부모가 없는 가장 상위 노드
잎새(Leaf) 노드 - 자식이 없는 노드 (단말 노드) 
내부(internal) 노드 - 잎새 노드를 제외한 모든 노드 

부모(Parent) - 연결된 두 노드 중 상위 노드
자식(Child) - 연결된 두 노드 중 하위의 노드
형제(Sibling) - 같은 부모를 가지는 노드

깊이(Depth) - 루트에서 특정 노드까지의 간선의 수
레벨(Level) - 트리의 특정 깊이를 가지는 노드 집합
높이(Height) - 트리에서 가장 큰 레벨 값
크기(Size) - 자신을 포함한 자식 노드의 개수
차수(Degree) - 각 노드가 지닌 가지의 수
트리의 차수 : 트리의 최대 차수

 

트리의 특징.

하나의 노드에서 다른 노드로 이동하는 경로는 유일
노드가 N개인 트리의 간선 수는 N-1개
Acyclic(Cycle이 존재하지 않음)
모든 노드는 서로 연결되어 있음 -> 순회할 수 있음
하나의 Edge(간선)을 끊으면 2개의 Sub-tree로 분리됨
부모 노드 밑에 여러 자식 노드가 연결되고, 자식 노드 각각에 다시 자식 노드가 연결되는 재귀적 형태

트리의 종류.

• 노드의 간선, 자식 노드의 수에 따른 분류

Binary Tree : 각 노드가 최대 두 개의 자식 노드를 가지는 트리. 모든 노드의 간선 개수가 최대 2개인 트리
Ternay Tree : 각 노드가 최대 세 개의 자식 노드를 가지는 트리. 모든 노드의 간선 개수가 최대 3개인 트리
Quaternary Tree : 각 노드가 최대 네개의 자식 노드를 가지는 트리. 모든 노드의 간선 개수가 최대 4개인 트리
...
N-ary Tree : 각 노드가 최대 정수 N개의 자식 노드를 가지는 트리. 모든 노드의 간선 개수가 최대 N개인 트리

각 노드가 가질 수 있는 최대 자식 노드에 따라 이진트리, 터너리트리, 쿼너리 트리 그 이상이면 N(엔)어리 트리라고 부른다.
그럼 왜 우리는 이 중에서도 이진 트리에 대해서 알아야 하며 제일 먼저 배우는 걸까?라고 GTP에게 물어보았다.

• 이진 트리는 다른 트리 구조의 기반이 되며 많은 고급 트리 구조 및 알고리즘은 이진 트리를 기반으로 만들어진다.
  이진 트리를 이해하는 것은 다른 트리 구조를 이해하는 데 큰 도움이 된다.
• 이진 트리는 널리 사용되는 자료구조로 데이터의 효율적인 저장 및 검색을 위해 많이 사용된다.
  이어 배우게 되는 이진 탐색 트리(Binary Search Tree)는 데이터를 정렬된 상태로 유지하면서 빠른 검색을 제공하며,
  힙(Heap)은 우선순위 큐와 같은 중요한 응용 프로그램에서 사용된다.
  그렇기 때문에 이진트리의 이해가 기반이 되어야 이후 학습할 내용도 정확하게 이해할 수 있다.
• 이진 트리는 재귀적인 구조를 가지고 있어 이러한 특성은 많은 알고리즘에서 재귀적인 접근을 사용하는 데 중요하다.
• 이진 트리는 데이터 구조의 기본 개념을 이해하는 데 도움이 된다.
  이진 트리를 학습하면 트리 구조의 기본 개념과 특성을 이해할 수 있고
  트리는 데이터의 계층적인 구조를 표현하며, 많은 문제를 효과적으로 해결하는 데 사용된다.
  
  아래는 그 사용에 대한 예시라고 볼 수 있는데, 나는 아직 이해 안됨 말하는 감자는 웁니다.

이진 탐색 트리(Binary Search Tree): 
이진 탐색 트리는 이진 트리의 한 종류로, 데이터를 정렬된 상태로 유지하면서 효율적인 검색을 제공합니다. 
이를 활용하여 특정 데이터를 빠르게 검색하거나, 데이터의 삽입과 삭제를 효율적으로 처리할 수 있습니다. 
예를 들어, 전화번호부나 사전과 같은 대용량의 정렬된 데이터를 검색해야 할 때 이진 탐색 트리는 매우 유용합니다.

힙(Heap): 
힙은 이진 트리의 한 종류로, 우선순위 큐와 같은 응용 프로그램에서 사용됩니다. 
힙은 최댓값이나 최솟값을 빠르게 찾아내는 데 효율적인 구조입니다. 
예를 들어, 작업 스케줄링이나 이벤트 처리 등에서 가장 우선순위가 높은 작업을 처리하는 데 힙을 사용할 수 있습니다.

이진 트리 검색 알고리즘: 
이진 트리는 데이터를 검색하는 다양한 알고리즘에서 사용됩니다. 
이진 트리를 활용한 검색 알고리즘은 효율적인 탐색을 제공합니다. 
대표적으로 이진 탐색(Binary Search) 알고리즘이 있는데, 
렬된 배열에서 특정 값을 찾는 데 사용됩니다. 이진 탐색은 이진 트리의 구조와 재귀적인 특성을 기반으로 작동합니다.

이진 트리 기반의 암호화 알고리즘: 
이진 트리는 암호화 알고리즘에서도 사용될 수 있습니다. 
예를 들어, 허프만 코딩(Huffman Coding)은 이진 트리를 활용하여 데이터의 압축과 해제를 수행하는 알고리즘입니다.

조직 구조: 
회사나 조직의 구조를 이진 트리로 모델링할 수 있습니다. 
각 노드는 조직의 구성원을 나타내며, 부모-자식 관계로 구성됩니다. 
이를 통해 조직 내에서 구성원의 관계, 계층 구조, 조직도 등을 표현할 수 있습니다.

주소록: 
전화번호부나 주소록은 이진 트리 구조로 구성될 수 있습니다. 
각 노드는 개인의 정보를 나타내며, 이름을 기준으로 정렬된 상태를 유지합니다. 
이를 통해 이름을 기반으로 개인을 검색하거나, 정렬된 순서로 목록을 조회할 수 있습니다.

계좌 관리: 
은행이나 금융 기관의 계좌 관리 시스템에서 이진 트리가 활용될 수 있습니다. 
각 노드는 계좌 정보를 나타내며, 계좌 번호를 기준으로 정렬된 상태로 유지됩니다. 
이를 통해 계좌를 검색하거나, 정렬된 순서로 계좌 목록을 관리할 수 있습니다.

파일 탐색기: 
컴퓨터의 파일 탐색기는 폴더 및 파일을 이진 트리 구조로 표현할 수 있습니다. 
각 노드는 폴더 또는 파일을 나타내며, 부모-자식 관계로 구성됩니다. 
이를 통해 파일 및 폴더의 계층 구조를 표현하고, 탐색 및 관리를 할 수 있습니다.

인터넷 라우팅: 
인터넷의 라우팅 시스템은 이진 트리 구조를 사용하여 경로 선택을 수행합니다. 
각 노드는 라우터를 나타내며, 네트워크 주소 및 경로 정보를 포함합니다. 
이를 통해 패킷의 전송 경로를 결정하고 효율적인 데이터 전송을 지원합니다.

정리하면 트리가 무엇인지 개념을 먼저 이해하고
기본이 되는 이진 트리를 알아야 그 이후에 접하게 되는 다양한 자료구조에 대해서도 정확한 이해를 동반할 수 있는 것 같다.
그래서 내일은 이진 트리의 종류와 구현 방법, 순회하는 방법 등과 친해지려 노력하며 이어 정리하려 한다.
하다보면 이해되겠죠 ? 트리ㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣㅣ