이진 트리
From Wikipedia, the free encyclopedia
컴퓨터 과학에서 이진 트리(二進-, 영어: binary tree)는 각각의 노드가 최대 두 개의 자식 노드를 가지는 트리 자료 구조로, 자식 노드를 각각 왼쪽 자식 노드와 오른쪽 자식 노드라고 한다. 단순히 집합론의 개념을 사용하는 재귀적 정의에서 (비어있지 않은) 이진 트리는 하나의 튜플 (L, S, R)로, L과 R은 이진 트리 또는 공집합이고 S는 싱글턴 집합이다. 일부 구현자는 공집합인 이진 트리도 허용한다.
그래프 이론 측면에서, 여기서 정의한 이진 (그리고 K-항) 트리는 실제로 일종의 방향성 그래프(arborescence)다. 따라서, 하나의 이진 트리는 bifurcating arborescence라고도 불리는데, 이 용어는 현대 컴퓨터 과학 기술이 널리 퍼지기 이전의 아주 오래된 프로그래밍 책에서 볼 수 있다. 이진 트리가 정렬 트리이면서, 루트 트리인 경우, 방향성 그래프가 아닌 비방향성 그래프로 해석할 수도 있다. 일부 저술자는 이진 트리 대신 루트 이진 트리를 사용해, 트리가 루트를 가지고 있지만, 위에서 설명한 것처럼, 이진 트리가 항상 루트를 가지고 있다는 사실을 강조한다. 이진 트리는 k가 2인 정렬 K-항 트리의 특수한 경우다.
수학에서, 이진 트리라고 명명한 것이 저술자마다 현저히 다를 수 있다. 어떤 이들은 컴퓨터 과학에서 보통 사용되는 정의를 사용하지만, 다른 이들은 정확하게 두 개의 자식 노드를 가진 잎이 없는 모든 트리로 정의하고 꼭 (왼쪽과 오른쪽으로) 자식 노드를 정렬하지도 않는다.
컴퓨팅에서, 이진 트리는 아주 다른 두 가지 방식으로 사용된다:
- 첫째, 어떤 값 또는 각 노드와 연관된 레이블에 기반한 노드에 액세스하는 수단. 이 방식의 이진 트리는 이진 탐색 트리와 이진 힙 구현에 사용되며, 효율적인 검색과 정렬을 위해 사용된다. 하나의 자식 노드만 있는 경우에도 왼쪽 또는 오른쪽으로 루트가 아닌 노드를 지정하면 이러한 일부 적용에 있어 문제가 되며, 특히 이진 탐색 트리에서 현저하다. 하지만, 특정 노드를 트리 내에 배치하는 것은 개념 정보의 일부가 아니다. 예를 들어, 일반적인 이진 탐색 트리에서 노드가 놓이는 위치는 추가되는 순서를 거의 따르며, 의미의 변경없이 재배치할 수 있다(예를 들어 자가 균형 이진 탐색 트리).
- 둘째, 연관 분기 구조를 이용한 데이터 표현. 이러한 경우 다른 노드의 아래와(또는) 왼쪽 또는 오른쪽에 노드를 특정하게 배치하는 것은 정보의 일부이다(즉, 이러한 배치를 변경하는 것은 의미 변경을 뜻한다). 일반적인 예는 허프만 코딩과 cladogram에 나타난다. 오늘 날의 문서를 장, 절, 구문 등으로 나누는 것은 이진 트리가 아닌 n-항 트리를 이용한 유사 예제다.