[자료구조] 트리(Tree)
트리
노드들이 나무 가지처럼 연결된 비선형 계층적 자료 구조
트리의 구성요소
-노드(Node) : 트리를 구성하고 있는 각각의 요소
-간선(Edge) : 노드와 노드를 연걸하는 선
-루트 노드(Root Node) : 트리 구조에서 최상단에 있는 노드
-Terminal 노드(leaf 노드, 단말 노드) : 자식이 하나도 없는 노드
-Internal 노드(내부노드, 비단말노드) : 단말 노드를 제외한 모든 노드. 루트 노드도 포함한다.트리 특징
-루트 노드를 제외한 모든 노드는 단 하나의 부모 노드를 가진다.
-트리의 구조는 데이터 저장보다는 저장된 데이터를 더 효과적으로 탐색하기 위해 사용된다.
-임의의 노드에서 다른 노드로 가는 경로는 단 한 개이다.
-싸이클이 존재하지 않는다.
-모든 노드는 서로 연결되어 있다.
-트리는 루트 노드로부터 레벨을 셀 수가 있다. 루트 노드의 레벨은 1이고 트리의 최고 레벨을 트리의 높이라고 부른다.
-같은 부모를 가지는 노드들을 형제 노드라고 부른다.트리 순회
- 전위 순회(Preorder)
루트 => 왼쪽트리 => 오른쪽 트리 순으로 순회- 중위 순회(Inorder)
왼쪽 서브트리 => 노드 => 오른쪽 서브트리 순으로 순회- 후위 순회(Postorder)
왼쪽서브트리 => 오른쪽 서브트리 => 노드 순으로 순회트리 종류
이진트리 (Binary Tree)
-모든 노드들이 최대 2개의 자식 노드를 가진 트리(자식 노드가 없거나 1개여도 가능)
편향 이진 트리(Skewed Binary Tree)
-하나의 차수로만 이루어져 있는 트리
-배열 또는 리스트와 같은 선형 구조이기 때문에 leaf node 탐색시 모든 데이터를 탐색해야하기 때문에 효율적이지 못하다.
포화 이진 트리(Full Binary Tree)
-Leaf Node를 제외한 모든 노드의 차수 2 또는 0인 트리
-해당 레벨에 몇 개의 노드가 존재하는지 바로 알 수 있기 때문에 노드의 개수를 파악할 때 용이
완전 이진 트리(Complete Binary Tree)
마지막 레벨을 제외하고 모든 레벨이 완전하게 채워져 있는 이진 트리로 모든 노드가 왼쪽부터 차례대로 채워져야한다.
이진 탐색 트리(Binary Search Tree)
이진 탐색 트리는 다음과 같은 특징을 가진 자료구조이다.
-모든 노드의 값은 중복되지 않는다.
-루트 노드의 왼쪽 서브트리는 해당 노드의 값보다 작은 값의 노드들로 이루어져 있다.
-루트 노드의 오른쪽 서브트리는 해당 노드의 값보다 큰 값의 노드들로 이루어져 있다.
-좌우 서브트리도 모두 이진 탐색 트리여야한다.
이진 탐색 트리 시간 복잡도
이진 탐색 트리에서의 검색, 삽입, 삭제는 결국 트리를 순회하며 타겟 데이터의 위치를 찾는 연산이 공통적으로 필요하므로 트리의 높이에 비례하여 시간 복잡도가 증가하게 된다.
따라서 균형적으로 생성되어 있는 트리의 높이를 H 라고 하면, H에 비례하여 O(H)의 시간 복잡도를 가지게 되는데 시간 복잡도는 원소의 개수로 표현해야 더 좋은 표현이라 할 수 있기 때문에 O(logN)으로 표기 가능하다.
갑자기 왜 O(logN)인가?
포화 이진 탐색 트리를 구성하고 있는 노드의 개수를 N 이라고 했을 때, 노드의 개수와 트리 높이와의 관계는 다음과 같다.
N = 2^(H+1) - 1
따라서 노드의 개수를 통해 트리의 높이를 계산할 수 있고, 정리하면 다음과 같은 식을 구할 수 있다. 
H = log(N + 1) - 1
이를 일반적인 Big-O 시간 복잡도로 표현하자면 위 식을 간소화한 O(logN)으로 표현할 수 있는 것이다.