STUDY/알고리즘
코딩 테스트 합격자 되기 - 트리
킵코
2024. 8. 3. 22:27
스터디 : 코딩테스트 합격자 되기 - 4주 차
강의 출처 : 인프런 코딩 테스트 합격자 되기 - 트리
트리
트리는 논리적 계층이 있는 구조로 노드로 구성되어 있다.
트리 용어 정의
- 루트 노드 : 트리에서 부모를 갖지 않는 노드 -> 노드 [1]
- 부모 노드 : 노드 [19]는 노드 [3]의 부모 노드
- 자식 노드 : 노드 [3]은 노드 [19]의 자식 노드
- 형제 노드 : 같은 부모를 갖는 노드 -> 노드 [7]과 노드 [5]
- 리프 노드 : 자식이 없는 노드 -> 노드 [13]
- 차수 : 트리 안에 있는 각 노드의 차수 가운데 최대 차수
- 레벨 : 트리의 높이
이진 트리
트리에 속한 모든 노드의 차수가 2 이하인 트리
이진 트리 구현 - 배열
루트 노드 인덱스가 1일 때, 왼쪽 자식 노드는 부모 노드 인덱스 * 2, 오른쪽 자식 노드는 부모노드 인덱스 * 2 + 1이다.
빈 공간이 많이 생길 수 있다.
이진 트리 구현 - 연결 리스트
각 리스트의 인덱스는 부모 노드이다. 자식 노드는 부모 노드에 해당되는 인덱스에 추가한다.
배열보다 공간 효율이 좋지만 자식 노드를 찾는데 오래 걸릴 수 있다.
이진 트리 순회
트리 노드를 모두 방문하는 방법으로 현재 노드를 언제 방문하는지에 따라 전위순회, 중위순회, 후위순회로 분류한다.
전위 순회
순회 순서
- 루트 방문
- 왼쪽 서브트리를 전위 순회로 순회
- 오른쪽 서브트리를 전위 순회로 순회
그림에 있는 트리를 전위 순회로 순회하면 1 -> 4-> 3-> 2 -> 5-> 8-> 7-> 6 순서로 순회한다.
중위 순회
순회 순서
- 왼쪽 서브트리를 중위 순회로 순회
- 루트를 방문
- 오른쪽 서브트리를 중위 순회로 순회
그림에 있는 트리를 중위 순회로 순회하면 1 -> 2 -> 3 -> 4 -> 5-> 6-> 7 순서로 순회한다.
후위 순회
순회 순서
- 왼쪽 서브트리를 후위 순회로 순회
- 오른쪽 서브트리를 후위 순회로 순회
- 루트를 방문
그림에 있는 트리를 중위 순회로 순회하면 D -> E -> B -> F -> G -> C -> A 순서로 순회한다.
이진 탐색 트리
탐색을 효율적으로 하기 위해 만든 이진트리이다. 왼쪽 자식 노드는 부모 노드보다 작은 값을 넣고,
오른쪽 자식 노드는 부모 노드보다 큰 값을 넣는다.
이진 탐색 트리 특성
- 최대 탐색 횟수는 트리의 높이와 같다
- 삽입과 동시에 정렬을 한다.
- map, set의 내부는 균형 이진 탐색 트리로 되어있다.