[자료구조] 이진 트리

이진 트리의 정의 트리의 일종으로, 각 노드가 최대 2개의 하위 노드로 구성되어 있는 트리를 말한다. 하위 트리는 왼쪽과 오른쪽으로 구분된다. 이진 트리는 모양에 따라서 포화 이진 트리, 완전 이진 트리, 편향 이진 트리로 나눠진다. 포화 이진 트리는 아래와 같이 모든 노드가 2개의 하위 노드를 가진 경우이다. 완전 이진 트리는 트리의 높이가 k 일 때, 높이 k - 1 까지는 모든 노드가 있어야 하고, 높이 k에 존재하는 노드들은 왼쪽에서 오른쪽으로 순서대로 존재해야 한다. 아래와 같이 번호가 부여되면, k번 노드의 부모는 k / 2, 왼쪽 / 오른쪽 자식은 2k / 2k + 1로 노드의 번호를 알 수 있다. 이러한 특성 때문에 1차원 배열에 저장하기 쉽다. 편향 이진 트리는 한쪽 방향으로만 노드가 구..

2020.08.07