최종 수정 : 25.1.2
이진 트리
트리의 구조는 정의하는 방법에 따라 연산이 단순하고 명확해진다.
1. 이진 트리의 정의
트리의 차수가 2 이하로 제한시켜 노드의 구즈를 링크를 두 개 갖는 연결 리스트로 정형화하여 구성할 수 있도록 한 트리가 이진 트리(binary tree)이다.
이진 트리는 모든 노드가 정확하게 두 서브 트리를 가질 수 있는 트리로 왼쪽 서브 트리와 오른쪽 서브 트리를 분명하게 구별할 수 있는 트리이다.
2. 이진 트리의 성질
- 이진 트리는 자노드의 개수가 2 이하인 일반 트리와 의미가 다르다. 이진 트리의 왼쪽 자노드는 일반트리의 부자 관계와 같고, 오른쪽 자노드는 일반 트리의 형제 관계이다. 이는 일반 트리를 이진 트리로 변환에서 본다.
- 노드가 없는 트리(empty tree)도 이진 트리이다.
- 이진 트리는 순서 트리이다. 즉, 자노드에서 위치가 중요한 의미를 가진다.
- 해당 레벨 l(l = 1, 2, 3, ...)에서 최대 노드 수는 2의 l - 1 제곱이다.
이진 트리의 성질에서 루트의 레벨을 0이라고 정의하기도 하는데, 그럴 때만 유의해서 최대 노드의 수를 생각하면 된다.
3. 이진 트리의 분류
1) 엄밀한 이진 트리
☞ 트리를 구성하는 각 노드의 차수가 0 또는 2인 트리이다.
2) Knuth 이진 트리
☞ 트리를 구성하는 노드의 차수가 2 이하인 트리이다. 모든 노드의 차수가 0, 1, 2 중 하나가 된다. 즉, 모든 이진 트리는 knuth 이진 트리이다.
3) 편향 이진 트리(사향 이진 트리 Skewed Binary Tree)
☞ 트리의 왼쪽 서브 트리나 오른쪽 서브 트리가 없고, 한쪽으로 기울어진 트리이다. 트리의 모양에 따라 왼쪽 편향, 오른쪽 편향 트리로 부른다. 이 트리는 리스트나 배열로 저장할 경우 기억공간의 낭비가 발생한다.
4) 완전 이진 트리(전이진 트리, Complete Binary Tree)
☞ 높이 h인 트리의 레벨 h - 1까지는 포화 이진 트리이고, 레벨 h에서 왼쪽부터 리프 노드가 채워진 트리를 지칭한다.
5) 포화 이진 트리(정이진 트리, Full Binary Tree)
☞ 엄밀한 이진 트리이면서 높이 h인 트리의 모든 단노드가 레벨 h에 있는 트리이다.
4. 일반 트리의 이진 트리 변환
일반 트리는 부노드와 자노드가 계층상 상하 관계로 표현된다. 이진 트리는 이러한 일반 트리를 이진 트리로 변환할 수 있다. 즉, 일반 트리와 이진 트리는 노드의 위치의 의미가 다르다.
참고
독학사 교재
댓글