7.6 요약¶
1. 핵심 정리¶
- 이진 트리는 '하나를 둘로 나누는' 분할 정복 논리를 보여 주는 비선형 자료 구조다. 각 노드는 값 하나와 왼쪽, 오른쪽 자식을 가리키는 포인터 두 개를 포함한다.
- 어떤 노드의 왼쪽(오른쪽) 자식과 그 아래 노드들이 이루는 트리를 해당 노드의 왼쪽(오른쪽) 서브트리라고 한다.
- 주요 용어에는 루트 노드, 리프 노드, 레벨, 차수, 간선, 높이, 깊이 등이 있다.
- 이진 트리의 초기화, 노드 삽입과 삭제 방법은 연결 리스트와 비슷하다.
- 주요 종류는 포화 이진 트리, 완전 이진 트리, 정 이진 트리, 균형 이진 트리다. 포화 이진 트리가 가장 이상적이며, 연결 리스트는 퇴화한 최악의 상태다.
- 이진 트리는 노드 값과 빈자리를 레벨 순서대로 배열하여 배열로 표현할 수 있다. 부모와 자식의 인덱스 매핑 관계가 포인터를 대신한다.
- 레벨 순서 순회는 '한 겹씩 바깥으로 확장'하는 너비 우선 탐색이며, 보통 큐로 구현한다.
- 전위, 중위, 후위 순회는 '먼저 끝까지 간 뒤 돌아와 계속하는' 깊이 우선 탐색이며, 보통 재귀로 구현한다.
- 이진 탐색 트리는 효율적인 원소 탐색 자료 구조로, 탐색, 삽입, 삭제의 시간 복잡도는 모두 \(O(\log n)\)이다. 연결 리스트로 퇴화하면 각 복잡도가 \(O(n)\)으로 저하된다.
- AVL 트리는 균형 이진 탐색 트리라고도 하며, 회전 연산으로 삽입과 삭제가 반복되어도 균형을 유지한다.
- AVL 트리의 회전에는 오른쪽 회전, 왼쪽 회전, 오른쪽 후 왼쪽 회전, 왼쪽 후 오른쪽 회전이 있다. 삽입이나 삭제 후 아래에서 위로 회전하여 균형을 복구한다.
2. Q & A¶
Q: 노드가 하나뿐인 이진 트리의 높이와 루트의 깊이는 모두 \(0\)인가?
그렇다. 높이와 깊이는 보통 '거치는 간선 수'로 정의하기 때문이다.
Q: 이진 트리의 삽입과 삭제를 보통 여러 연산의 조합으로 수행한다고 했는데, 여기서 '여러 연산'은 무엇인가? 해당 자원에 속한 자식 노드의 자원을 해제하는 것으로 이해해도 되는가?
이진 탐색 트리를 예로 들면 삭제를 세 경우로 나누어 처리하며, 각 경우마다 여러 단계의 노드 연산이 필요하다.
Q: 이진 트리의 DFS에는 왜 전위, 중위, 후위라는 세 순서가 있고 각각 어디에 쓰이는가?
배열을 정방향이나 역방향으로 순회하듯이 전위, 중위, 후위는 이진 트리를 순회하는 세 방법이며 특정 순서의 결과를 얻는 데 사용한다. 예를 들어 이진 탐색 트리는 왼쪽 자식 값 < 루트 값 < 오른쪽 자식 값을 만족하므로 '왼쪽 \(\rightarrow\) 루트 \(\rightarrow\) 오른쪽' 우선순위로 순회하면 정렬된 노드 순서를 얻는다.
Q: 오른쪽 회전은 불균형 노드 node, child, grand_child 사이의 관계를 처리하는데, node와 그 부모의 기존 연결은 관리하지 않아도 되는가? 회전 후 끊어지지 않는가?
재귀의 관점에서 보아야 한다. right_rotate(root)는 서브트리의 루트를 전달받고, 마지막의 return child는 회전 후의 서브트리 루트를 반환한다. 새 서브트리 루트와 부모의 연결은 함수가 반환된 뒤 이루어지므로 오른쪽 회전 자체가 관리할 범위가 아니다.
Q: C++에서 함수를 private와 public으로 나누는 기준은 무엇인가? height()는 public, updateHeight()는 private에 두는 이유는 무엇인가?
주로 메서드의 사용 범위를 기준으로 한다. 클래스 내부에서만 쓰면 private로 설계한다. 예를 들어 updateHeight()는 삽입과 삭제의 한 단계일 뿐이라 사용자가 따로 호출할 의미가 없다. 반면 height()는 vector.size()처럼 노드 높이에 접근하는 기능이므로 편리하게 쓰도록 public으로 둔다.
Q: 입력 데이터 집합에서 이진 탐색 트리를 어떻게 구성하는가? 루트 선택이 중요한가?
그렇다. 구성 방법은 이진 탐색 트리 코드의 build_tree()에 제시되어 있다. 루트는 보통 입력을 정렬한 뒤 중간 원소로 정하고, 왼쪽과 오른쪽 서브트리를 재귀적으로 구성한다. 이렇게 하면 트리의 균형을 최대한 보장할 수 있다.
Q: Java에서 문자열을 비교할 때 반드시 equals()를 사용해야 하는가?
Java에서 기본 타입의 ==는 두 변수의 값이 같은지 비교한다. 참조 타입에서는 두 방식의 원리가 다르다.
==: 두 변수가 같은 객체, 즉 메모리의 같은 위치를 가리키는지 비교한다.equals(): 두 객체의 값이 같은지 비교한다.
따라서 값을 비교하려면 equals()를 사용해야 한다. 다만 String a = "hi"; String b = "hi";로 초기화한 문자열들은 문자열 상수 풀에 저장되어 같은 객체를 가리키므로, 이 경우에는 a == b로 내용이 같은지 비교할 수도 있다.
Q: 너비 우선 순회에서 맨 아래 레벨에 도달하기 전 큐의 노드 수는 \(2^h\)인가?
그렇다. 예를 들어 높이 \(h = 2\)인 포화 이진 트리의 전체 노드 수는 \(n = 7\)이고, 맨 아래 레벨의 노드 수는 \(4 = 2^h = (n + 1) / 2\)다.