이진 트리, 이진 탐색 트리

이진 트리(Binary Tree)

각 노드가 최대 두 개의 자식 노드를 가질 수 있는 계층적 자료구조로 두 개의 자식 노드는 왼쪽 자식과 오른쪽 자식으로 구분된다.

class Node {
    int value;
    Node left, right;
}

정 이진 트리(Full Binary Tree):
- 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리
완전 이진 트리(Complete Binary Tree)
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드는 왼쪽부터 순서대로 채워져 있다.
- 어느 노드에 오른쪽 자식이 존재한다면 왼쪽 자식도 가지고 있어야 완전 이진 트리가 된다.
포화 이진 트리(perfect binary tree)
- 모든 내부 노드가 두 개의 자식 노드를 가지며 모든 노드가 동일한 레벨의 트리
균형 이진 트리(Balanced Binary Tree)
- 높이 균형이 맞춰진 트리

이진 트리는 레벨 순(왼 → 오)으로 각 노드에 index를 붙여 1차원 배열로 표현할 수 있다. 중간에 자식 노드가 빈 트리는 배열 사이에 null 값이 들어간다.

트리 탐색 방법

전위 탐색 (preorder)
- 노드 - 왼쪽 서브트리 - 오른쪽 서브트리
- A → B → D → E → H → C → F → G → I
중위 탐색 (inorder)
- 왼쪽 서브트리 - 노드 - 오른쪽 서브트리
- D → B → E → H → A → F → C → G → I
- 왼쪽 서브트리부터 탐색하기 때문에 루트인 A 노햣드는 중간에 방문하게 된다.
후위 탐색 (postorder)
- 왼쪽 서브트리 - 오른쪽 서브트리 - 노드
- D → H → E → B → F → I → G → C → A
- 왼쪽과 오른쪽 서브 트리 모두 탐색 후 노드를 방문한다. 루트인 A 노드는 가장 마지막에 방문하게 된다.

이진 트리의 일종으로, 빠른 탐색을 위한 규칙을 가지고 있다.
왼쪽 서브트리의 모든 노드 값은 부모 노드의 값보다 작고, 오른쪽 서브트리의 모든 노드 값은 부모 노드의 값보다 크다.
활용
- 데이터베이스: 인덱스를 빠르게 탐색하기 위해 균형 트리를 활용.
- 검색 엔진: 대규모 데이터 탐색에 이진 탐색 트리의 변형 사용.
- 파일 시스템: 디렉토리 탐색에 계층적 구조 적용.

이진 탐색 트리에서 탐색, 삽입, 삭제 작업의 시간 복잡도는 트리의 깊이에 비례한다.

완전 균형 트리에서는 모든 노드가 균등하게 분포하여 탐색 성능이 최적화된다.
불균형 트리에서 한쪽으로만 노드가 치우치는 최악의 경우엔 사실상 연결 리스트처럼 변형될 수 있다. 시간 복잡도는 O(N)로, 노드 수에 선형적으로 비례한다.

불균형 문제를 해결하기 위해 개발된 레드-블랙 트리, 2-3트리, b-트리 등이 있다.

선형 스캔을 한번 진행하는 경우, 데이터가 변하지 않는 경우에는 이진 탐색이 나을 수 있다.
데이터의 변동성이 큰 경우(예. 입사/퇴사)에 배열을 사용할 경우 정렬된 배열로 처리하려면 매번 배열을 갱신해야 하기 때문에 비용이 커질 수 있다. 이진 탐색 트리는 데이터 자체가 변경돼도 탐색 구조가 유지되기 때문에 효율적이다.

https://jh2021.tistory.com/34