이진 트리
이진 트리
- 모든 노드의 차수를 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