트리, 이진트리, 이진탐색트리

트리(Tree)

---

계층적인 자료를 표현하는 자료구조다.

• 나무를 거꾸로 한 모습이다.
• 사이클이 존재하지 않고, 모든 노드가 연결되어 있다.
• 방향 그래프이다

 

트리 관련 용어

 

 

이진 트리(Binary Tree)

---

자식의 노드의 수가 최대 2개인 트리를 의미한다.

트리 순회(Tree Traversal)

1. 전위 순회(Pre-order Traversal) : 노드, 왼쪽 자식, 오른쪽 자식 순서로 방문하는 순회 방법
   • A-B-D-E-C-F-G 의 순서
2. 중위 순회(In-order Traversal) : 왼쪽 자식, 노드, 오른쪽 자식 순서로 방문하는 순회 방법
   • D-B-E-A-F-C-G 의 순서
3. 후위 순회(Post-order Traversal) : 왼쪽 자식, 오른쪽 자식, 노드 순서로 방문하는 순회 방법
   • D-E-B-F-G-C-A 의 순서

 

 

이진 탐색 트리(BST, Binary Serach Tree)

---

탐색을 위해 조건이 더해진 이진 트리

조건

• 부모 노드보다 왼쪽 자식의 노드가 작다.
• 부모 노드보다 오른쪽 자식의 노드가 크다.
• 같은 값을 가지는 노드는 없다.

 

시간복잡도

트리의 높이를 h라고 할 때, 삽입/삭제/탐색 모두 O(h)의 시간복잡도를 가진다.

오른쪽 그림과 같은 편향 트리의 경우 최악의 경우로 O(N)의 시간복잡도를 가진다. (N은 노드의 개수)

따라서, 평균 O(logN), 최악 O(N)의 시간복잡도를 가진다.

 

 

추가 질문

---

Q. 그래프와 트리의 차이가 무엇인가요?

• 트리는 그래프의 일종이다.
• 그러나, 트리는 그래프와 달리 방향성을 가지고, 사이클이 존재하지 않는다.

Q. 이진탐색트리에서 중위 탐색을 하게 되면, 그 결과는 어떤 의미를 가지나요?

• 오름차순의 형태가 나온다.
• 본문 이진탐색트리 그림에서 '1 - 7 - 9 - 10 - 11 - 14 - 21'로, 오름차순이다.

Q. 이진탐색트리의 한계점에 대해 설명해주세요.

• 편향트리의 경우 링크드 리스트와 같은 형태가 된다.
• 균형 잡힌 트리가 만들어지도록 조건을 설정해야 한다.

 

 

참고

---

IT위키

[자료구조] 트리(Tree)란

[자료구조] 이진 탐색 트리 (BST, Binary Search Tree)