[게임 프로그래머 입문 올인원] 트리 자료구조 : 이진 탐색 트리 (70, 71강)

A. 트리 자료구조

1. 이진 트리(BT) 

a. 이진 트리란?

🌟 각 노드가 최대 두 개의 자식 노드를 가지는 트리 구조

 

• 계층적으로 데이터를 구성하는데 사용
• 이진 탐색 트리, 힙, AVL트리, 레드블랙 트리 등 다양한 종류의 자료구조 와 알고리즘에서 기본적인 구성 요소
• 레프트, 라이트 차일드로 만드는게 일반적 (2개뿐이니) 

 

b. 이진트리의 규칙

• 각 노드는 최대 두 개의 자식 노드를 가짐
• 각 노드는 하나의 부모 노드를 가질 수 있음
• 각 노드는 데이터를 저장하기 위한 값을 가질 수 있음
• 이진 트리는 재귀적으로 정의되며, 각 노드의 왼쪽과 오른쪽 서브트리 또한 이진 트리

 

👉 이진 탐색 알고리즘 선행공부

분할 정복(Divide and Conquer) 알고리즘 1 : 이진 탐색 (Binary Search)

 

 

2. 이진 탐색 트리(BST) 기초

a. 이진 탐색 트리란?

🌟 이진 탐색 트리 : 이진 트리 자료구조+ 이진 탐색 알고리즘

 

정렬된 데이터를 효율적으로 관리하고 검색할 수 있는 자료구조

데이터베이스 인덱스나 컴파일러 심볼 테이블 등에서 널리 사용

❕ 힙트리는 이 검색트리보다 조건이 훨씬 가볍다

 

b. 이진 탐색 트리의 특징

왼쪽을 타고 가면 현재 값보다 작고 오른쪽을 타고 가면 현재 값보다 크다

 

1) 이진 트리 구조

 

2) 정렬된 데이터 저장

 

모든 노드에 대해 왼쪽 서브트리의 값은 해당 노드의 값보다 작고,

오른쪽 서브트리의 값은 해당 노드의 값보다 큼

 

3) 탐색, 삽입, 삭제에 효율적

 

BST는 정렬된 데이터를 저장하기 때문에 이진 탐색 알고리즘을 트리 형태로 구현한 것

따라서 탐색, 삽입, 삭제 등의 연산을 효율적으로 수행

 

탐색, 삽입, 삭제 O(log n)

 

4) 균형잡힌 트리 유지

 

BST 성능은 트리의 균형 여부에 달림

균형을 유지하는 AVL트리, 레드-블랙 트리가 있음

 

c. 이진 검색 트리 문제

1) 데이터 추가

 

문제점으론 한쪽으로 기울어지면 균형이 깨진다

 

d. BST의 데이터 삭제

1) 삭제할 노드가 자식 1개일 경우

 

그냥 위로 계승하면 됨

 

2) 삭제할 노드가 자식 2개

 

부모 값을 지운다고 하면 (10)

 

지워진 10이라는 값 보다 다음으로 큰 값을 찾아 올린다

 

끝

 

💙 이진 트리와 이진탐색 트리의 차이점

1) 정렬된 데이터 저장

- 이진 탐색 트리 : 모든 노드가 정렬된 순서로 저장
- 이진 트리 : 저장 순서에 규칙 없음

2) 탐색 효율성

- 이진 탐색 트리 : 알고리즘 특성으로 데이터를 빠르게 검색 O(log n)
- 이진 트리 : 탐색 효율성 보장 X

3) 용도

- 이진 탐색 트리 : 주로 정렬된 데이터를 저장하고 검색하는 용도
- 이진 트리 : 데이터의 저장과 순회에 사용되며 다양한 트리 기반 알고리즘과 자료구조를 구현하는데 사용

👉 요약 : 이진 탐색 트리는 이진 트리의 일종.
정렬된 데이터를 효율적으로 관리하기 위해 사용하는 특수 이진 트리

 

 

3. 이진 탐색 트리 구현

a. 기본적인 구조 생성하기

📁 GameCoding > 📄 BinarySearchTree.h

 

노드라는 개념으로 생성, 트리니까 노드를 기억하게

 

b. Insert  함수 생성하기

노드를 만들어서 위치를 골라 넣어주는 함수

 

1. 맨 첫번째 데이터는 그냥 넣어주기
2. 추가할 위치 찾기
   • 키값이 부모의 키값보다 작으면 왼쪽
   • 키값이 부모의 키값보다 작으면 오른쪽
3. 위치를 찾았으면 연결

 

📁 GameCoding > 📄 BinarySearchTree.cpp

 

1, 2

2, 3

 

c. Print 함수 생성하기

부모님 출력 후 왼오 왼오 방향으로 출력

 

📁 GameCoding > 📄 BinarySearchTree.h

 

Print 함수 생성

 

📁 GameCoding > 📄 BinarySearchTree.cpp

 

추가해주고

 

이 함수도 추가

 

커서 조정 후 키 출력, 예쁘게 출력하는 코드 추가

 

📁 GameCoding > 📄 BinarySearchTree.h

 

기본 프린트 코드 생성

 

d. 사용해보기 : 추가

📁 GameCoding > 📄 GameCoding.cpp

 

이진탐색트리 추가후 내용 입력

 

잘 나온다

 

e. Search 함수 생성하기

검색 용도로 활용하기 위한 함수 생성

 

📁 GameCoding > 📄 BinarySearchTree.h

 

검색하는 함수 추가

 

📁 GameCoding > 📄 BinarySearchTree.cpp

 

재귀함수로 키 찾기 구현

 

f. 삭제 1: 헬퍼함수 생성하기

최소, 최대, 그 다음으로 큰값

 

📁 GameCoding > 📄 BinarySearchTree.h

 

 

📁 GameCoding > 📄 BinarySearchTree.cpp

 

min 함수 구현 (왼쪽 값 타고가기)

 

min 함수처럼 return nullptr 때려야함

 

next 함수를 구현하기는 조금 어렵다

 

10 다음 15를 찾는게 next함수

 

그럼 두가지 케이스를 구별해서 만들어야 하는데

1. 노드가 있으면 오른쪽 값을 가서 거기서 제일 작은 값 
2. 부모님들 중 왼쪽 자식으로 들고있는 조상을 만날 때 까지 들고있으면 됨

 

next 함수 구현

 

g. Replace 함수 생성하기 

서브트리끼리 교체하는 함수 (삭제시 균형 맞추기)

 

📁 GameCoding > 📄 BinarySearchTree.h

 

 

📁 GameCoding > 📄 BinarySearchTree.cpp

 

1) 부모님이 없으면 루트로 연결

왼쪽 자식이였으면 왼쪽으로 연결

오른쪽 자식 이였으면 오른쪽으로 연결

 

2) 부모 노드를 바꿔주고

3) 노드 정리

 

 

h. delete 함수 생성하기

키와 노드를 삭제해주는 함수 생성

 

📁 GameCoding > 📄 BinarySearchTree.h

 

 

📁 GameCoding > 📄 BinarySearchTree.cpp

 

키는 그냥 삭제해주면 됨

 

자식이 있는경우를 처리해야 함

 

 

i. 사용해보기 : 삭제

📁 GameCoding > 📄 GameCoding.cpp

 

 

🧡 이진 탐색과 이진 탐색 트리의 문제점

한쪽으로 데이터가 치우치게 되면 연결리스트랑 동일해져 시간복잡도는 결국 n이 됨

이진탐색을 구현할 수 있는 트리의 기반을 마련하는게 레드-블랙트리 
다음시간엔 구현하는건 너무 어려워서 하지않고, 동작의 원리만 알고 넘어감

 

 

 

---

출처 : https://www.inflearn.com/course/%EA%B2%8C%EC%9E%84-%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8-%EC%9E%85%EB%AC%B8-%EC%98%AC%EC%9D%B8%EC%9B%90-rookiss#curriculum

[게임 프로그래머 입문 올인원] C++ & 자료구조/알고리즘 & STL & 게임 수학 & Windows API & 게임 서버