비선형 구조(1) - 트리

💡 트리(Tree)의 개념

• 트리는 데이터들을 계층화시킨 자료 구조이다.
• 그래프의 특수한 형태로 노드(Node)와 선분(Branch)으로 되어 있고, 정점 사이에 사이클(Cycle)이 형성되어 있지 않으며, 자료 사이의 관계성이 계층 형식으로 나타나는 비선형 구조이다.
• 인덱스를 조작하는 방법으로 가장 많이 사용하는 구조이다.
• 트리는 노드(Node)와 노드를 연결하는 링크(Link)로 구성된다.
• 배열과 달리 노드들이 포인터로 연결되어 노드의 상한선이 없다.

트리의 개념 한 눈에 보기!!

 

📍 트리(Tree) 용어

용어	설명
루트 노드(Root Node)	∙ 트리에서 부모가 없는 최상위 노드, 트리의 시작점 ∙ {A}
단말 노드(Leaf Node)	∙ 자식이 없는 노드, 트리의 가장 말단에 위치 ∙ {F, G, H, E, C}
레벨(Level)	∙ 루트 노드를 기준으로 특정 노드까지의 경로 길이 ∙ E의 레벨 = 3
조상 노드(Ancestor Node)	∙ 특정 노드에서 루트에 이르는 경로상 모든 노드 ∙ D의 조상 노드 = {B, A}
자식 노드(Child Node)	∙ 특정 노드에 연결된 다음 레벨의 노드 ∙ B의 자식 노드 = {D, E}
부모 노드(Parent Node)	∙ 특정 노드에 연결된 이전 레벨의 노드 ∙ F의 부모 노드 = {D}
형제 노드(Sibling)	∙ 같은 부모를 가진 노드 ∙ F의 형제 노드 = {G, H}
깊이(Depth)	∙ 루프 노드에서 특정 노드에 도달하기 위한 간선의 수 ∙ 트리의 깊이 = 3
차수(Degree)	∙ 특정 노드에 연결된 자식 노드의 수 ∙ D의 차수는 3

 

📍 트리 순회 방법

➡️ 트리 순회방법은 크게 전위, 중위, 후위로 구분된다. (아래 자료가 설명이 잘되어 있어 참고했다.)

https://www.jiwon.me/binary-tree-traversal/

이진 트리 순회: 전위, 중위, 후위, 레벨

 

📎 전위 순회 (Pre-Order Traversal)

➡️ 'Root - Left - Right' 순으로 방문

C - L - R 순으로 조회

 

📎 중위 순회 (In-Order Traversal)

➡️ 'Left - Root - Right' 순으로 방문

L-C-R 순으로 조회

 

📎 후위 순회 (Post-Order Traversal)

➡️ 'Left - Right - Root' 순으로 방문

L-R-C 순으로 조회

 

📍 트리 종류

📌 이진 탐색 트리(Binary Search Tree)

• 이진 탐색 트리는 차수가 2 이하인 노드로 구성되어 자식이 둘 이하로 구성된 트리이다.
• 이진 ㅌ탐색 트리는 부모 노드보다 작은 값은 왼쪽으로 부모 노드보다 큰 값은 오른쪽 노드에 생성된다.

📎  균형 잡힌 이진 탐색 트리

균형 잡힌 이진 트리

 

📎 균형 잡히지 않은 이진 탐색 트리

균형 잡히지 않은 이진 탐색 트리

 

📌 AVL 트리(Adelson-Velsky and Landis Tree)

• AVL 트리는 두 자식 서브 트리의 높이는 항상 최대 1만큼만 차이가 나도록 스스로 균형을 잡는 이진 탐색 트리이다.

📌 2-3 트리(2-3 Tree)

• 2-3 트리는 차수가 2 또는 3인 내부 노드를 갖는 탐색 트리이다.
• AVL 트리의 단점인 삽입과 삭제 시의 전체 트리를 재구성하는 부분을 줄인 트리이다.

📌 레드-블랙 트리(Red-Black Tree)

• 레드-블랙 트리의 각 노드는 빨강 또는 검정의 색상을 가지고 있으며, 색깔에 따른 규칙을 통해 스스로 균형을 잡는 이진 탐색 트리이다.