트리
트리는 노드와 가지로 구성되어 있다. 각 노드는 가지를 통해 다른 노드와 연결된다.
루트
- 트리의 가장 위에 있는 노드를 루트노드라고 한다. 루트트리는 한개만 존재한다.리프
- 가장 아래쪽에 있는 노드를 리프라고 한다. 리프는 단말 노드(terminal node), 외부노드(external node)라고도 한다. 리프노드는 더이상 뻗어 나갈 가지가 없는 마지막 노드를 말한다.비단말 노드
- 리프를 제외한 노드를 비단말 노드(non-terminal node)라고 한다. 다른 말로는 내부 노드(internal node)라고도 불린다.자식
- 어떤 노드와 가지로 연결되어 있는 아랫쪽 노드를 자식이라 한다. 자식은 여러개 존재할 수 있다. 리프는 자식이 없다.부모
- 어떤 노드와 가지로 연결되어 있는 위쪽 노드를 부모라고 한다. 노드의 부모는 한개만 존재한다. 루트는 부모가 없다.레벨
- 레벨은 루트에서 얼마나 멀리 떨어져 있는지를 나타낸다. 루트는 레벨이 0이고 가지로 뻗어나갈 때 마다 1씩 증가한다.차수
- 각 노드가 갖는 자식의 수를 차수라고 한다.
순서 트리 검색
너비 우선 검색(BFS)
- 낮은 레벨부터, 왼쪽에서 오른쪽으로 검색한다.
깊이 우선 검색(DFS)
- 리프노드까지 검색을 한 후 더이상 검색할 곳이 없으면 부모 노드로 돌아가고 다른 리프노드까지 검색을 반복한다.
깊이 우선 검색은 리프로 내려가는 과정에서 노드를 방문할 때 세 종류의 스캔 방법이 있다.
이진 트리, 이진 검색 트리
이진트리
- 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 말한다.
완전 이진트리
- 루트부터 아래쪽 레벨로 노드가 가득차 있고 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 것을 완전 이진트리라고 한다.
이진 균형 검색 트리
이진이 아닌 균형 검색 트리
이진 검색 트리의 특징
- 구조가 단순하다.
- 중위 순회의 깊이 우선 검색을 통하여 노드값을 오름차순으로 얻을 수 있다.
- 이진 검색과 비슷한 방식으로 빠르게 검색할 수 있다.
- 노드를 삽입하기 쉽다.
참고) Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편