트리란?
트리는 데이터 사이의 계층 관계를 표현하기 위해 사용되는 그래프의 한 종류이다.
트리는 왜 쓰는가?
1. 계층 구조를 자연스럽게 표현한다.
방대한 양의 데이터를 빠르게 검색, 삽입, 삭제할 수 있다. 파일 시스템, 조직도, HTML DOM 등 처럼 원래 데이터가 상위- 하위 관계를 가질 때의 구조를 그대로 반영한다.
2. 배열/ 리스트 vs 트리
균형잡힌 트리 한정으로 탐색이 빠를 수 있다.
배열과 리스트에서 특정 값을 찾으면 시간 복잡도는 O(n) 인데, 균형 이진 탐색 트리(BST) 에서 찾으면 O(log n) 이다. 균형 잡힌 트리는매번 절반씩 후보를 줄여나가는 구조 덕분이다. 균형 잡히지 않은 트리는 시간 복잡도가 O(n) 이다.
삽입/ 삭제가 배열보다 유리하다.
배열 중간에 삽입/ 삭제하면 뒤 원소를 다 옮겨야 한다 (O(n)). 트리는 링크(포인터) 만 갈아끼우면 되어서 위치 재정렬 부담이 없다. 노드와 노드 사이 참조만 바꾸면 된다. 이 부분은 연결 리스트와 비슷하다.
정렬된 상태를 유지하면서 삽입이 가능하다.
균형 이진 탐색 트리 (BST) 는 삽입하면서도 항상 왼쪽 서브트리 값 < 나 < 오른쪽 서브트리 값 규칙을 지킨다. 매번 재정렬할 필요 없이 순서가 유지된다.
재귀 구조로 구현하여 알고리즘이 깔끔해진다.
트리의 모든 서브트리는 그 자체로 또 트리이다. 그래서 재귀 점화식이 나와 적용할 수 있다.
트리의 구조
트리의 구조를 Claude 아티팩트 기능을 이용해 한장으로 정리하였다.
순서트리
형제 노드의 순서 관계가 있는지에 따라 2종류로 분류된다. 형제 노드의 순서 관계가 있으면 순서트리이다.
1. 너비 우선 검색
낮은 레벨부터 왼쪽 → 오른쪽으로 검색하고, 한 레벨에서 검색을 마치면 다음 레벨로 내려가는 방법이다.
2. 깊이 우선 검색
리프에 도달할 때까지 아래쪽으로 내려가면서 검색하는 것이다. 리프에 도달 후 더 이상 도달할 곳이 없으면 부모 노드로 돌아가고, 다시 자식 노드로 내려간다.
깊이 우선 검색에는 3가지 종류의 스캔 방법이 있다.
- 전위 순회
- 노드 방문 → 왼쪽 자식 → 오른쪽 자식
- 중위 순회
- 왼쪽 자식 → 노드 방문 → 오른쪽 자식
- 후위 순회
- 왼쪽 자식 → 오른쪽 자식 → 노드 방문
이와 관련된 아티팩트를 생성했는데, 천천히 돌려보면 이해하기 쉽다.
무순서트리
형제 노드의 순서 관계가 없으면 무순서트리이다.
이진 트리
- 이진트리는 왼쪽 자식과 오른쪽 자식만을 갖는 트리이다.
- 두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관없다.
- 왼쪽 자식을 루트로 하는 서브트리는 왼쪽 서브트리, 오른쪽 자식을 루트로 하는 서브트리는 오른쪽 서브트리이다.
완전 이진 트리
- 완전 이진 트리는 루트 아래쪽 레벨로 노드가 가득 차 있고, 같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리이다.
- 높이가 K 인 완전 이진 트리가 가질 수 있는 노드의 수는 2^(k+1) - 1 개이다.
- n 개의 노드를 저장할 수 있는 완전 이진 트리의 높이는 log n 이다.
이진 검색 트리
- 왼쪽 서브트리 노드의 키값 < 자신의 노드 키값
- 자신의 노드 키 값 < 오른쪽 서브트리 노드의 키 값
이진 검색 트리와 이진 탐색
이진 검색 트리에 대한 설명을 보며 문제를 절반씩 줄여나간다는 점이 이진 탐색이랑 비슷하다고 생각이 들었다. 두 개 다 전체 탐색 범위를 절반으로 줄이는 기준이 있고, 그 기준과 비교하여 한쪽만 선택하여 들어가고, 다른 쪽은 확인하지 않는다.
차이점은 배열로 구현되었느냐, 트리로 구현되었느냐의 차이이다. 이분 탐색은 정렬된 배열에서 인덱스로 중간 값을 계산한다. 트리는 이미 각 노드의 구조가 크고 작음의 정보값을 들고 있다.
균형 검색 트리
이진 검색 트리는 키의 오름차순으로 삽입되어 트리의 높이가 깊어지는 단점이 있다. 때문에 높이를 O(log n) 으로 제한하여 고안된 검색 트리를 균형 검색 트리 라고 한다.
AVL 트리
레드, 블랙 트리
