[자료구조] 트리 구조 (Tree) / 이진 트리 (Binary Tree)

Tree구조

 

Tree의 정의

그래프의 일종으로 비선형 계층적 자료 구조(Hierachical Data Structure)이다. 하나의 루트(root) 노드와 이를 기준으로 한 개 또는 여러 개의 서브트리(subtree)로 구성되어 있다. → 부모 노드와 자식 노드로 구분된다.

✅ 비선형 자료구조란? 한 노드가 여러 개의 노드와 연결되어 있는 형태를 가지는 자료 구조로 각 노드가 선형적인 순서가 아닌 여러 경로를 통해 연결될 수 있음을 의미한다. 대표적으로 트리(Tree), 그래프(Graph), 힙(Heap), 해시테이블(Hash table) 등이 있다.

한 노드에서 시작하여 다른 노드들을 순회하고 자기 자신에게 돌아오는 연결 그래프이다. 아래로 뻗어나가는 구조이기 때문에 사이클이 없다. 

트리는 그래프의 부분집합으로 순환 구조를 가지지 않아야 한다. 즉, 한 노드에서 시작하여 다른 노드로 돌아오지 않아야 하는 것이다. 

부모-자식 관계로 구성된 계층적 데이터를 표현하기에 유용하다.

Tree 구조와 용어

- 루트(Root)
트리 구조에서 가장 상위에 위치한 노드
루트 노드는 다른 모든 노드들의 조상(ancestor)이며 트리 구조에서 유일함
- 자식(Child) 노드
어떤 노드의 바로 아래에 위치한 노드들
- 부모(Parent) 노드
어떤 노드보다 한 단계 위에 위치한 노드
- 형제(Sibling) 노드
부모 노드가 같은 노드들
같은 레벨에 나란히 있는 노드
- 잎 노드(Leaf)
자식 노드가 없는 노드 (= 단말 노드)
- 서브트리(Subtree)
트리에서  어떤 노드와 그 노드의 모든 자손들로 이루어진 트리
- 엣지(Edge)
노드 간의 연결을 나타내는 선으로 방향성을 가지지 않음 (단방향)
트리 구조에서 각 노드는 하나 이상의 edge로 연결
- 깊이(Depth)
루트 노드에서 어떤 노드까지 이르는 경로의 길이를 해당 노드의 깊이라고 함
루트 노드에서 특정 노드까지 이르는 엣지(Edge)의 개수
- 레벨(level)
해당 노드의 깊이(depth)에 1을 더한 값으로 같은 깊이를 가지고 있는 노드를 묶어서 레벨이라고 한다.

Tree 구조의 장점

- 계층 구조 표현에 적합
상위와 하위 관계가 있는 데이터를 표현하는데 유용
- 빠른 검색
이진 탐색 트리(Binary Search Tree) 라는 형태로 구성될 때 효과적
- 메모리 공간 효율
중복된 값을 허용하지 않기 때문에 공간을 효율적으로 사용할 수 있다.
- 데이터 정렬에 용이
이진 탐색 트리(Binary Search Tree)는 데이터를 정렬된 상태로 유지할 수 있다.
- 알고리즘에서 활용 가능
트리 순회(Tree Traversal) 알고리즘, 힙(Heap) 알고리즘, 분할 정복(Divide and Conquer) 알고리즘 등에서 트리 구조 사용
- 삽입, 삭제가 쉬움
삽입 및 삭제 시 해당 노드의 부모 노드와 자식 노드만 수정하면 된다.

---

 

이진트리(Binary Tree)란?

각각의 노드가 최대 두 개의 자식 노드를 가지는 자료구조로 왼쪽 자식 노드, 오른쪽 자식 노드로 나눈다.

정 이진트리, 완전 이진트리, 균형 이진트리, 포화 이진트리, 무한 이진트리 등이 있다.

- 특징
    - 각 노드는 최대 두 개의 자식 노드를 가진다.
    - 왼쪽 서브 트리와 오른쪽 서브 트리는 각각 이진 트리
    - 레벨 i에서 노드의 최대 개수는 2^(i-1)이다.

트리순회란?

트리의 각 노드를 체계적인 방법으로 방문하는 과정을 의미하며 전위순회(preorder), 중위 순회(inorder), 후위 순회(postorder)로 나뉜다.

🔽 이진 탐색 트리 의 구조 알아보기

Binary Search Tree Visualization

- 전위 순회(pre-order)
루트 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순서로 순회
- 중위 순회(in-order)
왼쪽 자식 노드 → 루트 → 오른쪽  자식 노드 순서로 순회
- 후위 순회(post-order)
왼쪽 자식 노드 → 오른쪽 자식 노드 → 루트 순서로 순회

이진트리 표현 방법

- 1차원 배열 : 이진트리의 n번째 노드를 배열의 n번째 요소에 저장하는 방법으로 노드의 위치를 색인에 의하여 쉽게 접근 할 수 있다.
- 연결 리스트 표현 : 왼쪽 자식을 가리키는 포인터 필드와 오른쪽 자식을 가리키는 포인터 필드를 포함하는 노드로 표현하는 방법으로 기억 장소를 절약하며 노드의 삽입 및 삭제에 있어 효율적이다.

이진 탐색 트리(Binary Search Tree), 힙(Heap), 트라이(Trie), 레드 블랙 트리(Red-Black Tree)는 모두 이진 트리(Binary Tree)의 일종이다.

---

이진트리와 이진 탐색 트리 그리고 메모리 영역의 힙과 여기 나오는 힙의 개념이 뭐가 어떻게 다른건지 어렵고 헷갈리기 시작했다.

다음 게시물에서
1. 정 이진트리, 완전 이진트리, 균형 이진트리, 포화 이진트리, 무한 이진트리
2. 이진 탐색 트리(Binary Search Tree), 힙(Heap), 트라이(Trie), 레드 블랙 트리(Red-Black Tree)
3. 이진 탐색 트리와 이진트리의 차이점 / 자료구조 힙(Heap)과 메모리 영역의 힙(Heap) 에 대해 알아봐야겠다.

하나를 공부하면 항상 10개 정도는 궁금증이 생긴다. 그래서 재미있기도 하고 시간가는 줄 모르겠다ㅎㅅㅎ 오늘도 화이팅 해야지!