9장 트리

트리

트리는 노드와 가지로 구성되어 있다. 각 노드는 가지를 통해 다른 노드와 연결된다.

루트

• 트리의 가장 위에 있는 노드를 루트노드라고 한다. 루트트리는 한개만 존재한다.리프
• 가장 아래쪽에 있는 노드를 리프라고 한다. 리프는 단말 노드(terminal node), 외부노드(external node)라고도 한다. 리프노드는 더이상 뻗어 나갈 가지가 없는 마지막 노드를 말한다.비단말 노드
• 리프를 제외한 노드를 비단말 노드(non-terminal node)라고 한다. 다른 말로는 내부 노드(internal node)라고도 불린다.자식
• 어떤 노드와 가지로 연결되어 있는 아랫쪽 노드를 자식이라 한다. 자식은 여러개 존재할 수 있다. 리프는 자식이 없다.부모
• 어떤 노드와 가지로 연결되어 있는 위쪽 노드를 부모라고 한다. 노드의 부모는 한개만 존재한다. 루트는 부모가 없다.레벨
• 레벨은 루트에서 얼마나 멀리 떨어져 있는지를 나타낸다. 루트는 레벨이 0이고 가지로 뻗어나갈 때 마다 1씩 증가한다.차수
• 각 노드가 갖는 자식의 수를 차수라고 한다.

---

순서 트리 검색

너비 우선 검색(BFS)

• 낮은 레벨부터, 왼쪽에서 오른쪽으로 검색한다.

깊이 우선 검색(DFS)

• 리프노드까지 검색을 한 후 더이상 검색할 곳이 없으면 부모 노드로 돌아가고 다른 리프노드까지 검색을 반복한다.

깊이 우선 검색은 리프로 내려가는 과정에서 노드를 방문할 때 세 종류의 스캔 방법이 있다.

• 전위 순회
  • 노드 방문 - 왼쪽 자식 - 오른쪽 자식
• 중위 순회
  • 왼쪽 자식 - 노드 방문 - 오른쪽 자식
• 후위 순회
  • 왼쪽 자식 - 오른쪽 자식 - 노드 방문

---

이진 트리, 이진 검색 트리

이진트리

• 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 말한다.

완전 이진트리

• 루트부터 아래쪽 레벨로 노드가 가득차 있고 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 것을 완전 이진트리라고 한다.

이진 균형 검색 트리

• AVL 트리
• 레드-블랙 트리

이진이 아닌 균형 검색 트리

• B트리
• 2-3 트리

이진 검색 트리의 특징

• 구조가 단순하다.
• 중위 순회의 깊이 우선 검색을 통하여 노드값을 오름차순으로 얻을 수 있다.
• 이진 검색과 비슷한 방식으로 빠르게 검색할 수 있다.
• 노드를 삽입하기 쉽다.

참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편