트리
- 계층적 구조 표현
트리 관련 용어
- 노드(node): 실제로 저장하는 데이터
- 루트(root) 노드: 최상위에 위치한 데이터
- 시작 노드
- 모든 노드와 직간접적으로 연결됨
- 리프(leaf) 노드: 마지막에 위치한 데이터들
- 더 이상 가지 치지 않음
- 부모-자식: 연결된 노드들 간의 상대적 관계
- 자식은 없을 수도, 많이 있을 수도
- 부모는 언제나 1개
- 트리가 그래프보다 더 제약이 있다.
- 조부모. 삼촌(uncle). 형제자매(sibling) 등도 있다.
- 깊이(depth): 노드 -> 루트 경로의 길이
- 높이(height): 노드-> 리프 경로의 최대 길이
- 레드 블랙트리에서 사용
- 하위 트리(subtree): 어떤 노드 아래의 모든 것을 포함하는 트리
- 재귀적: 하위 트리 그 자체가 트리
트리의 속성
- 부모와 자식 모두 노드
- 부모:자식 = 1: 다수
- 자식은 언제나 부모로부터 가지를 침
이진트리
- 자식이 최대 둘(왼쪽, 오른쪽)
- 무언가 계층적으로 이분해 나갈 때 적합
이진 탐색 트리(binary search tree, BST)
- 가장 많이 사용하는 트리
- 왼쪽 자식은 언제나 부모보다 작다, 오른쪽자식은 언제나 부모이상
- 정렬된 트리 - 재귀적으로 읽으면(중위순회)
- 정렬되어 있으니 효율적인 알고리즘 사용 가능
- 평균 삽입, 삭제, 탐색시간 O(logn)
- 최악의 경우 O(n): 한쪽에 줄줄이 있을 때
BST 탐색
- 이진 탐색 트리의 겨웅 왼쪽 하위 트리는 항상 나보다 작고 오른쪽 하위 트리는 크기 때문에 따라가면 탐색할 수 있음.
BST 삽입
- 새로운 노드를 받아줄 수 있는 부모 노드를 찾음
- 탐색과 방법이 같음.
- 새로운 노드를 받아줄 수 있는 부모 -> 오른쪽 하위트리로 가야하는데 오른쪽 자식이 없는부모, 왼쪽 하위트리로 가야하는데 왼쪽 자식이 없는 부모
- 자식 추가
BST 삭제
- 리프노드의 경우
- 리프노드는 그냥 삭제
- 자식이 있는 노드의 경우
- 트리에서는 무언가를 지울 때 항상 리프를 지움.
- 정렬 된 배열로 생각 하면 쉽다.
- 오른쪽 하위 트리에서의 최솟값 -> in order successor
- 왼쪽 하위 트리에서 최댓값 -> in order predecessor
순서
1. 지울 값을 가지고 있는 노드를 찾는다
2. 그 바로 전 값을 가진 노드를 찾는다.
- 왼쪽 하위 트리의 제일 오른쪽 리프 or 오른쪽 하위 트리의 제일 왼쪽 리프
3. 두값을 교환
4. 리프노드삭제
순회 방법(이름은 내노드를 기준으로 생각)
1. 중위 순회(in-order traversal)
- 왼쪽 하위 -> 현재 -> 오른쪽 하위트리
2. 전위(pre-order) 순회
- 현재 -> 왼쪽 -> 오른쪽
- 이진탐색에서 잘 쓰지 않음.
- 용도
- 트리 복사(다른 순회도 가능하지만 직관적이지 않음)
- 수식은 보통 중위 표기법을 사용 -> 전위 표기법으로 표기하면 컴퓨터로 계산하기 좀더 편함.
3. 후위(post-order) 순회
- 왼쪽 -> 오른쪽 -> 현재
- 위의 전위 2번째 용도는 후위 순회로 표현시 더 쉽게 구현
