[데이터베이션] 자료구조 이진 트리 및 이진 탐색 트리

이번 포스팅에서는 이진 트리에 대해 다루어 보려고 합니다.

 

트리의 기본 개념에 대해 확인하고 싶으시면 아래의 링크를 참고 부탁드립니다.

2022.10.23 - [Intelligence Technology] - [데이터베이스] 자료구조 - 트리(Tree)의 개념(비선형 구조)

[데이터베이스] 자료구조 - 트리(Tree)의 개념(비선형 구조)

 

이진트리(Binary Tree)란

차수(Degree)가 2 이하인 노드들로 구성된 트리입니다. 즉, 자식 노드가 둘 이하인 노드들로 구성된 트리입니다.

 

<2진 트리 구조>

이진트리의 특징

이진트리의 레벨이 n의 최대 노드의 수는 2의 (n-1) 제곱만큼 가집니다. 위 트리와 같이 레벨이 n=3인 경우 최대 노드의 수는 2의 (3-1) 제곱을 해서 4개가 됩니다. 또한, 이진트리에서 단말 노드의 수가 x 개고 차수가 2인 노드의 수가 y개면 x=y+1이 성립합니다. 위 트리를 통해서 확인해 보면 단말 노드의 수 x는 D, E, F, G, 4개가 되고 차수가 2인 노드들은 A, B, C, 3개가 됩니다. 따라서 4 = 3+1로 성립이 됨을 확인 가능합니다.

 

이진트리는 종류가 여러 가지 있습니다.

1. 정이진 트리(Full Binary Tree)

2. 전이진 트리(Complete Binary Tree)

3. 사향 이진트리(Skewed Binary Tree)

 

우선 정이진 트리는 깊이가 k인 경우 전체 노드의 수는 2의 (k-1) 제곱이 되며 각 레벨 i마다 2의 (i-1) 제곱씩 꽉 찬 트리를 얘기합니다. 위에 예시로 들어둔 표가 정이진 트리의 모형입니다. 빈 노드가 없는 트리입니다.

 

전이진 트리의 경우는 모든 노드가 0개 또는 2개의 노드를 갖고 있는 트리를 의미합니다. 

<전이진 트리>	<전이진 트리가 아닌 경우>

 

사향 이진트리는 근원 노드로부터 한쪽으로만 기울어져 있는 트리를 의미합니다. 좌사향 이진트리의 경우는 오른쪽 자식이 없으며 우사향 이진트리의 경우는 왼쪽의 자식 노드들이 없습니다.

<좌사향 이진 트리>	<우사향 이진 트리>

 

그러면 트리에서는 값을 어떤 순서로 읽는지 알아보도록 하겠습니다.

트리의 운행법(Traversal)이라고 하며 3가지가 있습니다.

1. Preorder: 근원 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순

2. Inorder: 왼쪽 자식 노드 → 근원 노드 → 오른쪽 자식 노드 순

3. Postorder: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 근원 노드

---

예시를 들 때 그룹으로 치환을 하셔서 보시면 쉽습니다.

<2진 트리 운행법>

1. Preorder: 근원 노드 → 왼쪽 자식 노드 → 오른쪽 자식 노드 순

☞A1번3번 → AB2번E3번 → ABDHIECFG

방문 순서는 ABDHIECFG 순으로 접근합니다.

 

2. Inorder: 왼쪽 자식 노드 → 근원 노드 → 오른쪽 자식 노드 순

☞1번A3번 → 2번BEA3번 → HDIBEAFCG

방문 순서는 HDIBEAFCG 순으로 접근합니다.

 

3. Postorder: 왼쪽 자식 노드 → 오른쪽 자식 노드 → 근원 노드

☞1번3번A → 2번EBFGCA → HIDEBFGCA 순으로 방문을 합니다.

---

위와 같은 방식은 수식의 표현에도 적용이 가능합니다.

<2진 운행 수식 표현>

전위 표기법(PreFix): 연산자 → 왼쪽 자식 노드 → 오른쪽 자식 노드

☞+AB

중위 표기법(InFix): 왼쪽 자식 노드 → 연산자 → 오른쪽 자식 노드

☞A+B

후위 표기법(PostFix): 왼쪽 자식 노드 → 오른쪽 자식 노드 → 연산자

☞AB+

 

그러면 조금 더 복잡한 예시로 확인해보겠습니다.

PreFix

X = A / B * (C + D) + E

* 연산 우선순위 따라 괄호로 묶은 후 연산자를 해당 괄호 앞으로 이동시킵니다. 그 후, 괄호를 제거하면 됩니다.

☞ (X =  (A / B * (C + D) + E)) → (X =  ((A / B) * (C + D) + E)) → (=X+*(/(A  B) + (C  D)  E)) → =X+*/AB+CDE

 

PostFix

X = A / B * (C + D) + E

*연산 우선순위 따라 괄호로 묶은 후 연산자를 해당 괄호 뒤로 이동시킵니다. 그 후, 괄호를 제거하면 됩니다.

☞ (X =  (A / B * (C + D) + E)) → (X =  ((A / B) * (C + D) + E)) → XAB/CD+*E+=

---

PreFix와 PostFix를 InFix로 변환하는 경우는 각각 했던 방향을 역순으로 진행하시면 됩니다.

 

이상으로 2진 트리 및 방문 순서와 수식 적용방법에 대한 포스팅을 마치겠습니다.

 

오늘도 똑구의 꿀팁 블로그를 방문해 주셔서 감사합니다.