이진 트리

이진 트리

- 모든 노드의 차수를 2 이하로 제한한 트리

- 부모-자식 관계가 하위로 계속해서 이어지는 계층 구조

- n개의 노드는 n-1개의 간선을 가진다.

- 높이가 h인 트리의 노드의 최소 개수는 h+1, 최대 개수는 

이진 트리의 종류

- 완전 이진 트리

 -> 높이가 h이고, 노드의 개수는 ~개

- 포화 이진 트리

 -> 높이가 h일 때, 노드의 개수가 최대 노드 개수()이다.

 -> 공백 노드가 없기 때문에 노드를 더이상 추가할 수 없다.

- 편향 이진 트리

 -> 노드의 개수가 최소 개수이고, 왼쪽 또는 오른쪽 서브 트리만 가지고 있다.

이진 트리의 구현

1. 순차 자료 구조

- 배열 : 인덱스를 이용해 노드에 쉽게 접근 가능. 부모 노드와 자식 노드를 찾기 쉬움.

- 완전 이진 트리의 경우, 메모리 낭비가 심하지 않지만, 

편향 이진 트리의 경우, 메모리 낭비가 크고, 삽입, 삭제 연산도 비효율적

2. 연결 자료 구조

- 메모리 공간을 절약 가능, 삽입, 삭제 용이.

- 노드에 접근하기 위해서는 트리를 순회하여야 한다.

이진 트리의 순회

- 트리 내의 모든 노드를 방문

- 트리는 선형 구조가 아닌 계층 구조로 되어 있기 때문에 단순히 링크를 따라가면 안 된다.

- D : 현재 노드의 데이터를 읽기

- L : 왼쪽 서브 트리로 이동

- R : 오른쪽 서브 트리로 이동

- 전위 순회 (Preorder)    : D-L-R

- 중위 순회 (Inorder)      : L-D-R

- 후위 순회 (Postorder)   : L-R-D

 => 각 순회는 모두 재귀적이다.

이진 탐색 트리

[ 트리 탐색을 위한 정의 ]

- Key : 자료를 식별할 수 있는 유일한 값

- 루트 노드의 키 > 키 : 왼쪽 서브 트리

- 루트 노드의 키 < 키 : 오른쪽 서브 트리

- 루트 노드를 기준으로 가장 왼쪽 아래 노드가 가장 작은 값, 가장 오른쪽 아래 노드가 가장 큰 값

- 탐색 연산

 -> 루트 노드의 키부터 검사

루트 노드의 키 > 키 : 왼쪽 서브 트리 탐색

루트 노드의 키 < 키 : 오른쪽 서브 트리 탐색

루트 노드의 키 = 키 : 탐색 완료

- 삽입 연산

 -> 루트 노드부터 탐색하여, 키 값을 비교한다.

탐색 연산으로 키 값을 비교하여 서브 트리로 이동한다.

노드의 자식이 nullptr이면 삽입할 노드를 자식으로 연결한다.

- 삭제 연산

- 삭제할 노드를 탐색한 후,

1. 차수가 0인 경우

- 삭제할 노드의 부모를 저장

- 부모의 왼쪽 자식인지 오른쪽 자식인지 확인

- 부모 노드에서 자식 노드를 삭제

2. 차수가 1인 경우

- 삭제할 노드의 부모를 저장

- 부모의 왼쪽 자식인지 오른쪽 자식인지 확인

- 부모 노드의 자식 노드에 삭제할 노드의 자식 노드를 연결

- 노드 삭제

3. 차수가 2인 경우

- 삭제할 노드의 왼쪽 서브 트리에서 키 값이 가장 큰 노드를 탐색하여 후계자 노드로 저장

 -> 오른쪽 서브 트리에서 키 값이 가장 작은 노드를 탐색하여 후계자 노드로 저장해도 됨

- 후계자 노드의 부모 노드를 저장

- 삭제할 노드의 키에 후계자 노드의 키를 저장

- 부모 노드의 자식을 삭제

BinarySearchTree.cpp

BinarySearchTree.h