Tree

그래프의 여러 구조 중 단방향 그래프의 한 구조로
하나의 뿌리로부터 가지가 사방으로 뻗은 형태가 나무와 닮아있다로 해서 트리 구조라고 부른다.

Tree 구조와 특징

루트라는 하나의 꼭짓점 데이터를 시작으로 여러 개의 데이터를 간선으로 연결, 각 데이터를 노드라고 하며, 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 가진다.

• 깊이 : 루트로부터 연결된 하위 계층까지 깊이를 측정할 수 있음 (루트 노드의 깊이는 0)
• 레벨 : 같은 깊이를 가지고 있는 노드를 묶어서 레벨로 표현 (루트의 레벨은 1)
• 높이 : 끝 노드인 리프 노드를 기준으로 루트까지의 높이
  (리프 토느의 높이는 0)

Tree 실사용 예제

가장 대표적인 예제는 컴퓨터의 디렉토리 구조
모든 폴더는 하나의 루트 폴더에서 시작되어 가지를 뻗어나가는 모양새를 띈다.

Binary Tree

자식 노드가 최대 두 개인 노드들로 구성된 트리
자료 삽입, 삭제 방법에 따라 정 이진 트리, 완전 이진 트리, 포화 이진 트리로 나뉜다.

• 정 이진 트리
  각 노드가 0개 혹은 2개의 자식 노드를 갖습니다

Binary Search Tree

이진 탐색과 연결 리스트를 결합한 이진트리
이진 탐색의 효율적인 탐색 능력을 유지하면서 빈번한 자료 입력과 삭제를 가능하게끔 고안

이진 탐색 트리 특징

1. 각 노드에 중복되지 않는 키가 있음
2. 루트노드의 왼쪽 서브 트리는 해당 노드의 키보다 작은 키를 갖는 노드
3. 오른쪽 서브 트리는 해당 노드의 키보다 큰 키 노드

즉 , 모든 왼쪽 자식의 값이 루트나 부모보다 작고, 모든 오른쪽 자식의 값이
루트나 부모보다 큰 값을 가진다.

이런 특징을 가지기 때문에 기존 이진 트리보다 탐색이 빠르다
이진 탐색 트리의 연산은 높이가 h이면 O(h)의 복잡도를 가짐

Tree Traversal

전위 순회

중위 순회

후위 순회