코딩 테스트 스터디 - 09 트리

트리의 개념

• 노드와 간선으로 이루어진 계층적 자료 구조 (부모 자식 관계가 있음)
• 순환 X
• 코테에서는 이진 트리만 알면 된다

이진 트리 표현

1. 배열로 표현

• 루트 노드 인덱스 1
• 왼쪽 자식 노드 : 부모 노드 인덱스 * 2
• 오른쪽 자식 노드 : 부모 노드 인덱스 * 2 + 1
• 문제점 : 빈 공간이 많다 (버려지는 공간이 많아 효율이 별로), 그러나 구현은 쉽다

2. 인접 리스트 (이게 더 좋을 수도?_

• 각 리스트의 인덱스는 부모 노드
• 자식 노드는 부모 노드에 해당되는 인덱스에 추가

• 트리 노드 갯수와 인접 리스트 아이템 갯수가 거의 같음.
• 배열보다 공간 호율은 좋은데, 자식 노드를 찾는데 오래 걸림 (순차 탐색 필요). 그러나 이진 트리는 자식 2개라 크게 단점은 아닌..

이진 트리 순회

트리의 노드를 모두 방문하는 방법
현재 노드를 언제 방문하는지에 따라 전위, 중위, 후위 순회

전위 순회

부모 -> 왼쪽 -> 오른쪽

중위 순회

왼쪽 -> 부모 -> 오른쪽

• 예시 : 이진탐색트리의 원소를 정렬된 상태로 순위 (왼쪽 < 부모/ 오른쪽 > 부모)후위 순회왼쪽 -> 부모 -> 부모
• 예시 : 폴더 삭제하기 (제일 깊이 있는 폴더부터 삭제)

이진 탐색 트리

• 탐색을 효율적으로 하기 위해 만든 이진 트리
• 왼쪽 : 부모 노드보다 작은 값
• 오른쪽 : 부모 노드보다 큰 값

탐색 효율

최악의 경우 h번 (트리 높이) 탐색. -> O(N). 균형이 잘 잡힌 경우 ~~O(log N)
삽입할 때마다 정렬..

특성

• 최대 탐색 횟수 = 트리의 높이.
• 삽입과 동시에 정렬
• map, set : 균형 이진 탐색 트리로 구현됨. 키 값 기준 정렬이 되므로 필요 없다면 unordered 붙은 STL로 (해시)

출처 : 코딩 테스트 합격자 되기