HW)
연결리스트(Linked list)에 이어서, 자료 구조 3번째 노트로 이 번에는 '트리(Tree)' 에 대해서 이해해보자.
우선, 트리와 이진 트리(Binary Tree)의 개념, 구조, 연산 규칙을 정리하고, 활용 실습 대상으로 이진 탐색 트리(Binary Search Tree)를 파이썬으로 구현해보자.
트리(Tree)
> 트리는 테이터를 계층 구조(hierarchy) 즉 상-하 종속 관계로 저장하는 자료 구조이다.
- 트리는 “방향성 없는 그래프”의 일종으로, 순환(Cycle)이 없고 단 하나의 루트(root)를 가진다.
- 최상단에는 루트(Root)가 자리하고, 노드 간의 종속 관계는 부모(Parent)와 자식(Child)이라고 부른다.
> 용어
| 용어, 명칭 | 의미, 개념 |
| Root (루트) | 트리의 시작점 (상단, 꼭대기) |
| Node (노드) | 데이터 단위 (값 + 자식 참조 정보) |
| Edge (간선) | 노드 간 연결 |
| Parent (부모) | 위쪽 노드 |
| Child (자식) | 아래쪽 노드 (부모 노드에 종속) |
| Leaf (리프) | 자식 없는 노드 (단말 노드) |
| Subtree (서브트리) | 특정 노드에 종속된 하위 전체 트리 |
이진 트리(Binary Tree)
> 이진 트리는 각 노드가 최대 2개의 자식을 지닌 트리이다.
- 부모 노드를 기준으로 왼쪽 자식, 오른쪽 자식으로 구분한다.
> 종류
- 크게 3가지가 있다.
| 구분 | 정이진트리 (Full Binary Tree) |
완전이진트리 (Complete Binary Tree) |
포화이진트리 (Perfect Binary Tree) |
| 규칙 | 모든 노드가 0 or 2개의 자식을 가짐. | 마지막 레벨를 제외하고 모두 꽉 참. 마지막 레벨은 왼쪽부터 채움. |
모든 레벨(깊이)에 노드가 완전히 채워짐. (& 모든 leaf의 깊이가 동일함.) |
| 특징 | 자식이 1개인 노드가 없음. | 중간에 빈 노드가 있으면 안됨. ※ 힙(Heap) 자료구조가 이 형태 |
노드 수 = 2^k − 1 (k = 깊이 층 수 = 높이) ※ 2층 → 3개, 3층 → 7개, 4층 → 15개 |
> 순회 방법과 방문 규칙
- 공통사항으로 방문 방향은 위에서 아래로, 왼쪽에서 오른쪽이다.
| 순회(Traversal) 방법 | 방문 순서 | 해설 | 활용 |
| 전위 (Preorder) | root → left → right | 루트(root)를 먼저 방문 | 트리 구조 복사 |
| 중위 (Inorder) | left → root → right | 왼쪽 → 가운데 → 오른쪽 | BST에서 오름차순 정렬 결과가 됨 |
| 후위 (Postorder) | left → right → root | 루트를 마지막에 방문 | 트리 삭제(메모리 해제) |
| ※ 공통사항 레벨순서(Level-order) |
위→아래, left→right | BFS 방식 | 완전 이진 트리 검사 |
팔자는 ChatGPT5를 활용하여 수십 차례에 걸쳐서 체계적인 문답을 통해 트리의 모양을 출력할 수 있도록 코드를 정리하였다. 특히, 파이썬의 애니매이션 코드 능력을 빌렸다. 트리에서 노드를 연결하는 edge는 dash(' - ') 로 간략하게 하고 그 dash 라인을 기준으로 각 노드가 알파벳 또는 숫자로 나타낼 수 있도록 하였다. 이렇게 함으로써 그림 없이 텍스트만으로 설명하는 어려움을 최대한 해소하고자 노력하였다. 또한 각 노드가 어떤 규칙을 따르고 트리의 구조가 바뀌는지를 한 단계씩 나누어서 출력하고 그것에 대한 간략한 설명을 첨부하였기 때문에, 쉽게 눈으로 단계를 따라가면서, 트리에 대해서 충분히 이해할 수 있을 것이라 기대한다.
※각 코드들은 너무 길기 때문에 글 맨 뒤에 첨부하였고, 출력 결과들만 앞으로 가져왔다.
[출력 결과] 이진 트리 순회 방법 3가지에 대한 구현 결과
> 정 이진 트리 구조를 예제로 하여, 각 순회에 대한 노드 방문 순서를 아래 그림과 같이 출력하였다.
- 전위 순회 : A → B → D → E → C
- 중위 순회 : D → B → E → A → C
- 후위 순회 : D → E → B → C → A
'''
=== 이진 트리의 순회 결과 ===
A
--------- ---------
B C
---- ----
D E
> 전위 순회 (Preorder) : A B D E C
> 중위 순회 (Inorder) : D B E A C
> 후위 순회 (Postorder): D E B C A
'''
또한, 이진 트리의 실제 활용 사례에 여러가지가 있다고 한다. 글쓴이도 계속 공부해야할 것들이다. 이들 중에서, 이진 탐색 트리 (Binary Search Tree )를 파이썬으로 구현하여 노드에 입력된 숫자들이 어떤 규칙으로 트리의 구조에서 삽입되고 제거되는지 이해해보자.
> 이진 트리의 실제 프로그래밍 활용 사례
- 운영체제 (프로세스 트리)
- 파일 시스템 (폴더 구조)
- HTML/웹 브라우저 (DOM 트리)
- 게임/AI 트리 (의사결정 트리)
- 데이터베이스/검색 (B- Tree, B+ Tree)
- 파서 Parser (컴파일러 구문트리(AST)
- 알고리즘 (이진 탐색 트리(BTS), AVL, Red-Black Tree) 등 √
이진 탐색 트리(BTS, Binary Search Tree)
> 이진 탐색 트리는 '검색(Search)'에 유리하도록 정렬 규칙을 가진 트리이다.
※ 앞으로 약어로 BTS라고 부르겠다.
> BTS의 규칙
- 삽입, 삭제 규칙에 따른 노드의 (서브트리에서) 움직이는 원리(왼쪽, 오른쪽)
- 삽입 시에는 값의 크기를 비교하여 방향이 결정됨.
- 삭제 시에는 자식이 0, 1, 2개일 때마다 처리 방법과 규칙이 다름.
| 노드 삽입 규칙 (Add) | 노드 삭제 규칙 (Delete) |
| - 찾는 값 < 현재 노드 → 이동방향 왼쪽 - 찾는 값 > 현재 노드→ 이동방향 오른쪽 - 찾는 값 = 현재 노드 → 삽입하지 않음(중복 방지) - 빈 자리(빈 노드)를 만나면 → 새 노드 삽입 |
- 자식이 0개 → 리프 노드 자신을 삭제 - 자식이 1개 → 자식 노드를 부모 노드로 (위로) 올림. - 자식이 2개 → 오른쪽 서브트리의 최소값으로 대체 후, 자신을 삭제. 즉 중위 후속자(inorder successor)*로 교체 후, 자신을 삭제. |
※ 중위 후속자는 BST 정렬 규칙을 유지하기 위한 방법이다. 아래 출력 결과에서 '숫자 6을 삭제하는 경우'에 이 방법을 볼 수 있다.
[출력 결과] 이진 탐색 트리(BTS)의 삽입(add), 삭제(delete) 경우들에 대한 노드의 움직임 구현 결과
> 초기 기준 데이터 목록은 [8, 3, 10, 1, 6, 14, 4, 7, 13] 로 하였고, 숫자 8이 root이다.
- 그러면 규칙을 적용하여 목록 요소를 순차적으로 배치하면 아래와 같이 4층 구조가 된다.
'''
=== [1] BST (Top-Down 출력) ===
초기 BST:
설명: 루트 8을 기준으로, 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 배치됩니다.
8
-------- --------
3 10
---- ---- ----
1 6 14
--- --- ---
4 7 13
****************************************************************************************************
'''
> 삽입한 경우 : add
- 5, 2, 9를 각각 추가했을 때, 규칙에 따라서 어떻게 빈 노드에 배치되는지를 그림과 설명을 더하여 아래와 같이 출력하였다.
'''
# 추가한 경우
****************************************************************************************************
추가 숫자 : 5:
설명: 5 < 8 → 왼쪽(3) → 5 > 3 → 오른쪽(6) → 5 < 6 → 왼쪽(4) → 5 > 4 → 4의 오른쪽에 삽입.
8
---------------- ----------------
3 10
-------- -------- --------
1 6 14
---- ---- ----
4 7 13
---
5
****************************************************************************************************
추가 숫자 : 2:
설명: 2 < 8 → 왼쪽(3) → 2 < 3 → 왼쪽(1) → 2 > 1 이므로 1의 오른쪽에 삽입.
8
---------------- ----------------
3 10
-------- -------- --------
1 6 14
---- ---- ---- ----
2 4 7 13
---
5
****************************************************************************************************
추가 숫자 : 9:
설명: 9 > 8 → 오른쪽(10) → 9 < 10 이므로 10의 왼쪽에 삽입.
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 14
---- ---- ---- ----
2 4 7 13
---
5
****************************************************************************************************
'''
> 삭제한 경우 : delete
- 위, 추가의 마지막 결과로 얻은 트리에서 시작하여, 2, 14, 6을 각각 제거했을 때, 규칙에 따라서 어떻게 삭제가 되고 또한 트리 구조가 어떻게 변하는 지를 그림과 설명을 더하여 아래와 같이 출력하였다.
- 여기에서, 2를 삭제하는 것는 leaf를 삭제하는 예시이고, 14를 삭제하는 것은 자식 노드가 1개인 부모 노드를 삭제하는 예시이고, 6을 삭제하는 것은 자식 노드가 2개인 부모 노드를 삭제하는 예시이다.
'''
# 삭제한 경우
****************************************************************************************************
삭제 숫자 : 2 (리프):
설명: 2는 1의 오른쪽 리프이므로, 부모(1)의 오른쪽 포인터를 None으로 바꿔 바로 제거.
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 14
---- ---- ----
4 7 13
---
5
****************************************************************************************************
삭제 숫자 : 14 (자식 1개):
설명: 14의 유일한 자식은 13(왼쪽). 14를 제거하고 13 서브트리를 부모(10)의 오른쪽 자리에 승격.
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 13
---- ----
4 7
---
5
****************************************************************************************************
삭제 숫자 : 6 (자식 2개):
설명: 6은 왼쪽(4)·오른쪽(7) 두 자식 보유 → 중위 후속자 = 오른쪽 서브트리의 최소값(7)으로 값 교체 후, 원래 7 노드를 삭제.
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 7 9 13
----
4
---
5
****************************************************************************************************
'''
※더하여, add와 delete의 각 단계에서 규칙이 어떻게 적용되는 지를 좀 더 자세하게 살펴보면서 이해해보자.
- 필자는, 위 출력 결과만으로는 명확하게 이해하는 것에 부족함을 느꼈다. 이미 표에서 정리한 규칙들이 적용된 각 단계들을 보다 상세한 판정으로 구분하면서 하나씩 이해해보고자 ChatGPT5를 적극 활용하였다. 아래 출력 결과물을 따라가면, 노드(숫자)가 삽입되고 삭제되는 과정을 보다 명확하고 편하게 그리고 직관적으로 잘 이해할 수 있다.
'''
=== [2] BST 삽입/삭제 애니메이션 ===
설명: 5 < 8 → 왼쪽(3) → 5 > 3 → 오른쪽(6) → 5 < 6 → 왼쪽(4) → 5 > 4 → 4의 오른쪽에 삽입.
=== BST INSERT 경로: 삽입값 5 / 현재 노드 8 ===
[8]
-------- --------
3 10
---- ---- ----
1 6 14
--- --- ---
4 7 13
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 왼쪽으로 이동
=== BST INSERT 경로: 삽입값 5 / 현재 노드 3 ===
(8)
-------- --------
[3] 10
---- ---- ----
1 6 14
--- --- ---
4 7 13
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 오른쪽으로 이동
=== BST INSERT 경로: 삽입값 5 / 현재 노드 6 ===
(8)
-------- --------
(3) 10
---- ---- ----
1 [6] 14
--- --- ---
4 7 13
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 왼쪽으로 이동
=== BST INSERT 경로: 삽입값 5 / 현재 노드 4 ===
(8)
-------- --------
(3) 10
---- ---- ----
1 (6) 14
--- --- ---
[4] 7 13
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 오른쪽으로 이동
=== BST INSERT 완료: 5 ===
(8)
---------------- ----------------
(3) 10
-------- -------- --------
1 (6) 14
---- ---- ----
(4) 7 13
---
[5]
요약: 삽입 규칙에 따라 최종 위치에 노드 추가됨
****************************************************************************************************
설명: 2 < 8 → 왼쪽(3) → 2 < 3 → 왼쪽(1) → 2 > 1 → 1의 오른쪽에 삽입.
=== BST INSERT 경로: 삽입값 2 / 현재 노드 8 ===
[8]
---------------- ----------------
3 10
-------- -------- --------
1 6 14
---- ---- ----
4 7 13
---
5
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 왼쪽으로 이동
=== BST INSERT 경로: 삽입값 2 / 현재 노드 3 ===
(8)
---------------- ----------------
[3] 10
-------- -------- --------
1 6 14
---- ---- ----
4 7 13
---
5
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 왼쪽으로 이동
=== BST INSERT 경로: 삽입값 2 / 현재 노드 1 ===
(8)
---------------- ----------------
(3) 10
-------- -------- --------
[1] 6 14
---- ---- ----
4 7 13
---
5
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 오른쪽으로 이동
=== BST INSERT 완료: 2 ===
(8)
---------------- ----------------
(3) 10
-------- -------- --------
(1) 6 14
---- ---- ---- ----
[2] 4 7 13
---
5
요약: 삽입 규칙에 따라 최종 위치에 노드 추가됨
****************************************************************************************************
설명: 9 > 8 → 오른쪽(10) → 9 < 10 → 10의 왼쪽에 삽입.
=== BST INSERT 경로: 삽입값 9 / 현재 노드 8 ===
[8]
---------------- ----------------
3 10
-------- -------- --------
1 6 14
---- ---- ---- ----
2 4 7 13
---
5
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 오른쪽으로 이동
=== BST INSERT 경로: 삽입값 9 / 현재 노드 10 ===
(8)
------------------- -------------------
3 [10]
--------- --------- ---------
1 6 14
---- ---- ---- ----
2 4 7 13
----
5
선택 기준: 삽입값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)
판정: 왼쪽으로 이동
=== BST INSERT 완료: 9 ===
(8)
------------------- -------------------
3 (10)
--------- --------- --------- ---------
1 6 [9] 14
---- ---- ---- ----
2 4 7 13
----
5
요약: 삽입 규칙에 따라 최종 위치에 노드 추가됨
****************************************************************************************************
설명: 2는 1의 오른쪽 리프이므로 부모(1)의 오른쪽 포인터를 None으로 변경하여 바로 제거.
=== BST DELETE 탐색: 삭제값 2 / 현재 노드 8 ===
[8]
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 14
---- ---- ---- ----
2 4 7 13
---
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 왼쪽으로 이동
=== BST DELETE 탐색: 삭제값 2 / 현재 노드 3 ===
(8)
---------------- ----------------
[3] 10
-------- -------- -------- --------
1 6 9 14
---- ---- ---- ----
2 4 7 13
---
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 왼쪽으로 이동
=== BST DELETE 탐색: 삭제값 2 / 현재 노드 1 ===
(8)
---------------- ----------------
(3) 10
-------- -------- -------- --------
[1] 6 9 14
---- ---- ---- ----
2 4 7 13
---
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 오른쪽으로 이동
=== BST DELETE 대상 확인: 2 ===
(8)
---------------- ----------------
(3) 10
-------- -------- -------- --------
(1) 6 9 14
---- ---- ---- ----
[2] 4 7 13
---
5
=== BST DELETE 케이스 판정: 2 ===
(8)
---------------- ----------------
(3) 10
-------- -------- -------- --------
(1) 6 9 14
---- ---- ---- ----
[2] 4 7 13
---
5
케이스: 자식 0개(리프)
규칙: 리프는 바로 제거
판정: 부모 포인터를 None으로
=== 삭제 후 트리 ===
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 14
---- ---- ----
4 7 13
---
5
****************************************************************************************************
설명: 14는 자식이 1개(왼쪽 13) → 부모(10)의 오른쪽 자식 포인터를 13으로 연결해 승격.
=== BST DELETE 탐색: 삭제값 14 / 현재 노드 8 ===
[8]
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 14
---- ---- ----
4 7 13
---
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 오른쪽으로 이동
=== BST DELETE 탐색: 삭제값 14 / 현재 노드 10 ===
(8)
------------------- -------------------
3 [10]
--------- --------- --------- ---------
1 6 9 14
---- ---- ----
4 7 13
----
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 오른쪽으로 이동
=== BST DELETE 대상 확인: 14 ===
(8)
------------------- -------------------
3 (10)
--------- --------- --------- ---------
1 6 9 [14]
---- ---- ----
4 7 13
----
5
=== BST DELETE 케이스 판정: 14 ===
(8)
------------------- -------------------
3 (10)
--------- --------- --------- ---------
1 6 9 [14]
---- ---- ----
4 7 13
----
5
케이스: 자식 1개
규칙: 자식을 부모 위치로 승격
판정: 해당 자식 서브트리를 위로 올림
=== 삭제 후 트리 ===
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 13
---- ----
4 7
---
5
****************************************************************************************************
설명: 6은 왼쪽(4)·오른쪽(7) 두 자식 보유 → 중위 후속자(7)로 값 교체 후, 원래 7 노드를 삭제.
=== BST DELETE 탐색: 삭제값 6 / 현재 노드 8 ===
[8]
---------------- ----------------
3 10
-------- -------- -------- --------
1 6 9 13
---- ----
4 7
---
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 왼쪽으로 이동
=== BST DELETE 탐색: 삭제값 6 / 현재 노드 3 ===
(8)
---------------- ----------------
[3] 10
-------- -------- -------- --------
1 6 9 13
---- ----
4 7
---
5
선택 기준: 삭제값 vs 현재 노드 비교
규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽
판정: 오른쪽으로 이동
=== BST DELETE 대상 확인: 6 ===
(8)
---------------- ----------------
(3) 10
-------- -------- -------- --------
1 [6] 9 13
---- ----
4 7
---
5
=== BST DELETE 케이스 판정: 6 ===
(8)
---------------- ----------------
(3) 10
-------- -------- -------- --------
1 [6] 9 13
---- ----
4 7
---
5
케이스: 자식 2개
규칙(후속자): 중위 후속자 = 오른쪽 서브트리의 '최소' 노드
판정: 대상 값 ← 후속자 값 교체 후, 후속자 노드 삭제
=== 후속자 탐색 시작: 오른쪽 서브트리로 이동 ===
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 (6) 9 13
---- ----
4 [7]
---
5
선택 기준: 오른쪽으로 1칸 이동 후 왼쪽 끝까지
규칙: 왼쪽 자식이 있으면 계속 왼쪽으로 이동
=== 값 교체(개념): 대상 6 ← 후속자 7 ===
설명: 실제 구현은 '대상에 후속자 값을 대입' 후 '후속자 노드 삭제'입니다.
=== 삭제 완료 (자식 2개 케이스) ===
8
---------------- ----------------
3 10
-------- -------- -------- --------
1 7 9 13
----
4
---
5
****************************************************************************************************
'''
출력 결과는 여기까지 이다. 아래는 코드이다.
=====================================================
[Refs.]================================================
[코드] 이진 트리 순회 방법 3가지(전위, 중위, 후위)에 대한 구현
- 코드 앞부분은 트리의 구조와 노드 사이를 연결하는 모양을 출력하기 위한 내용이다. BTS 관련 코드 블럭은 메모되어서 구분할 수 있다.
# ======================================================
# 이진 트리 (Traversal + ASCII 시각화)
# ======================================================
# ───────────────────────────────────────────────
# 기본 노드 정의
# ───────────────────────────────────────────────
class Node:
def __init__(self, value, left=None, right=None):
# 각 노드는 값(value)과 왼쪽/오른쪽 자식 포인터를 가진다.
# 기본값을 None으로 둬서 리프(자식이 없는) 노드도 쉽게 표현 가능.
self.value, self.left, self.right = value, left, right
# ───────────────────────────────────────────────
# 대시(—) 도식으로 트리 출력
# ───────────────────────────────────────────────
def print_ascii_tree(root, cell=3, hpad=2, dash='-'):
"""
트리를 위→아래 방향으로 ASCII 문자(대시)를 이용해 시각화한다.
- cell : 각 노드 텍스트 최소 폭(글자 수). 노드 값이 짧아도 최소 폭만큼 자리 확보.
- hpad : 같은 레벨에서 좌/우 자식 사이를 벌리기 위한 수평 패딩(간격).
- dash : 부모-자식 노드 사이를 연결할 때 사용할 문자(기본 '-').
출력 전략(핵심 아이디어):
1) BFS로 '레벨별 노드 리스트'를 만든다(빈 자리도 None으로 채워 완전 이진트리 형태로 정렬).
2) 트리의 높이(height)와 노드 폭(nodew)을 기준으로 각 레벨의 x-좌표(센터)를 계산한다.
- 윗 레벨의 센터를 기준으로, 아래 레벨은 좌/우로 일정 거리(off)만큼 벌림.
3) 2배수 행(노드 행 + 대시 행)으로 그리드를 만들고, 각 노드/대시를 해당 좌표에 채운다.
"""
if not root:
print("(empty)")
return
# [1] BFS 기반으로 각 레벨(levels)을 구성
# - levels[d]는 깊이 d의 노드 목록(부족한 자리는 None으로 채움)
levels, q = [], [root]
while any(q): # q 안에 실제 노드가 하나라도 있으면 계속
levels.append([n for n in q]) # 현재 레벨 저장(원본 참조 그대로)
nq = []
for n in q:
if n:
# 실제 노드면 왼/오 자식을 큐에 추가
nq += [n.left, n.right]
else:
# 빈 자리(None)면, 아래에서도 자식 자리 2개를 None으로 유지
# -> 폭 계산과 정렬을 단순화(완전 이진트리 모양 유지)
nq += [None, None]
q = nq
# 트리 높이: 레벨 개수
height = len(levels)
# nodew: 각 노드 셀의 폭(문자 수)
# - 실제 노드 값 문자열 길이의 최댓값과 cell(최소 폭) 중 큰 쪽 선택
# - 셀 폭을 일정하게 해 텍스트가 겹치지 않게 함
nodew = max(cell, max(len(str(n.value)) for lvl in levels for n in lvl if n))
# base: 최하단 레벨에서의 기본 간격 스케일
# - (1 << (height - 1))는 2^(height-1)로, 레벨이 내려갈수록 간격이 절반씩 줄도록 만든 기준값
# - nodew + hpad 만큼의 기본 폭을 곱해 실제 간격 단위를 설정
base = (1 << (height - 1)) * (nodew + hpad)
# centers: 각 레벨에서 노드가 위치할 "센터 x좌표" 리스트들의 리스트
centers = []
for depth, lvl in enumerate(levels):
# off: 해당 깊이에서 부모-자식 간 수평 이동량
# - 윗 레벨에서 아래 레벨로 갈수록 간격(base >> depth)이 반으로 줄어듦
# - 단, 노드폭(nodew)보다 작은 간격은 비가시성/겹침을 유발하므로 최소 nodew로 보정
off = max(nodew, base >> depth)
if depth == 0:
# 루트의 기준 센터는 0으로 잡음(이후 전체를 좌로 얼마나 밀지 shift로 보정)
centers.append([0])
else:
# 이전 레벨의 센터들을 기준으로, 이번 레벨 센터는 좌/우로 off 이동해 배치
prev, curc = centers[-1], []
for p_x in prev:
curc += [p_x - off, p_x + off] # 왼자식, 오른자식
centers.append(curc)
# 전체 x좌표 범위를 조사하여, 음수/양수 섞인 좌표를 0~width-1로 옮기기 위한 이동량 계산
allx = [x for row in centers for x in row]
minx, maxx = min(allx), max(allx)
shift = -minx # 모든 좌표에 shift를 더해 최소 x가 0이 되도록 이동
# width: 전체 출력 폭(문자 수). 양 끝 센터와 노드 폭을 고려해 여유 2칸 추가
width = maxx - minx + nodew + 2
# rows: 출력 행 수
# - 각 트리 레벨은 "노드 행"과 그 아래 "대시(연결) 행"으로 구성되므로 2*height - 1
rows = height * 2 - 1
# 그리드 초기화: 공백으로 채운 2차원 문자 배열
grid = [[" "] * width for _ in range(rows)]
# 헬퍼: 특정 행 r, 센터 cx에 문자열 text를 중앙 정렬로 배치
def put_text(r, cx, text):
s = str(text)
# cx(센터)를 기준으로 문자열 길이의 절반만큼 좌측으로 시작점 이동
start = int(cx + shift - len(s)//2)
for i, ch in enumerate(s):
x = start + i
if 0 <= r < rows and 0 <= x < width:
grid[r][x] = ch
# 헬퍼: 두 x좌표(x1, x2) 사이를 dash 문자로 연결(한 줄의 수평 연결선)
# - 부모 노드의 오른쪽 가장자리와 자식 노드의 왼쪽 가장자리 사이를 잇는 느낌으로
# nodew//2 만큼 안쪽으로 살짝 당겨서 미관/겹침 방지
def put_dash_row(r, x1, x2):
if x1 > x2:
x1, x2 = x2, x1
# 부모/자식 센터에서 절반 폭을 더/빼서 실제 연결 시작/끝점을 조정
x1 = int(x1 + shift + nodew//2)
x2 = int(x2 + shift - nodew//2)
# 그리드 범위 내에서만 대시를 채움
for x in range(max(0, x1), min(width, x2+1)):
grid[r][x] = dash
# [2] 노드와 대시(연결선) 실제로 채우기
for d, lvl in enumerate(levels):
node_row = d * 2 # 노드가 그려질 행(짝수 행: 0,2,4,...)
# 현재 레벨의 각 노드를 자신의 센터 위치에 텍스트로 출력
for i, n in enumerate(lvl):
if n:
put_text(node_row, centers[d][i], n.value)
# 마지막 레벨이 아니면, 아래 행에 부모-자식 연결 대시를 그림
if d < height - 1:
dash_row = node_row + 1 # 대시는 노드 바로 아래(홀수 행)
for i, n in enumerate(lvl):
if not n:
continue # 빈 자리(None)는 스킵
p_x = centers[d][i] # 부모의 센터 x좌표
li, ri = i*2, i*2+1 # 다음 레벨에서 왼/오 자식의 인덱스
lc, rc = levels[d+1][li], levels[d+1][ri]
# 실제 자식이 존재하는 경우에만 연결선을 그림
if lc:
put_dash_row(dash_row, p_x, centers[d+1][li])
if rc:
put_dash_row(dash_row, p_x, centers[d+1][ri])
# [3] 완성된 그리드를 한 줄씩 출력
# - rstrip()으로 우측 공백 제거하여 출력 폭을 깔끔하게 유지
for r in range(rows):
line = "".join(grid[r]).rstrip()
if line:
print(line)
# ───────────────────────────────────────────────
# 순회 함수 (전위 / 중위 / 후위)
# ───────────────────────────────────────────────
def preorder(node, result):
# 전위 순회(Preorder): 루트 → 왼쪽 → 오른쪽
# - 현재 노드 방문 후, 왼쪽 서브트리, 오른쪽 서브트리 순으로 재귀
if node:
result.append(node.value) # 1) 루트 처리
preorder(node.left, result) # 2) 왼쪽
preorder(node.right, result) # 3) 오른쪽
def inorder(node, result):
# 중위 순회(Inorder): 왼쪽 → 루트 → 오른쪽
# - 이진 탐색 트리(BST)에서 중위 순회는 "정렬된 순서"를 반환한다는 성질이 있음
if node:
inorder(node.left, result) # 1) 왼쪽
result.append(node.value) # 2) 루트 처리
inorder(node.right, result) # 3) 오른쪽
def postorder(node, result):
# 후위 순회(Postorder): 왼쪽 → 오른쪽 → 루트
# - 삭제/해제 작업(자식 먼저 처리 후 부모)을 모델링할 때 자주 사용
if node:
postorder(node.left, result) # 1) 왼쪽
postorder(node.right, result) # 2) 오른쪽
result.append(node.value) # 3) 루트 처리
# ───────────────────────────────────────────────
# 트리 시각화 + 순회 결과 함께 출력
# ───────────────────────────────────────────────
def show_tree_with_traversals(root):
# 1) 트리를 그림으로 보여주고
print_ascii_tree(root)
# 2) 세 가지 순회 결과를 나란히 출력
pre, ino, post = [], [], []
preorder(root, pre)
inorder(root, ino)
postorder(root, post)
print("\n> 전위 순회 (Preorder) :", " ".join(map(str, pre)))
print("> 중위 순회 (Inorder) :", " ".join(map(str, ino)))
print("> 후위 순회 (Postorder):", " ".join(map(str, post)))
# ───────────────────────────────────────────────
# 이진 트리의 순회 방법 실행 예시
# ───────────────────────────────────────────────
if __name__ == "__main__":
# 예제 트리 구조(문자 레이블):
# A
# / ＼
# B C
# / ＼
# D E
tree = Node("A",
Node("B",
Node("D"),
Node("E")),
Node("C"))
print("=== 이진 트리의 순회 결과 ===")
show_tree_with_traversals(tree)
[코드] 이진 탐색 트리(BTS)의 추가(add), 삭제(delete) 경우들에 대한 노드의 변화 구현
- 코드 앞부분은 트리의 구조와 노드 사이를 연결하는 모양을 출력하기 위한 내용이다. BTS (단계별 애니매이션) 관련 코드 블럭은 메모되어서 구분할 수 있다.
- 참고로, 그 코드 앞부분 블럭은 다음 글의 주제인 힙(Heap)의 트리 구조를 그리는 데에도 동일하게 활용하였다.
#======================================================
# 트리(Tree) / 힙(Heap) 대시(—) 도식 + 표준 메시지(선택 기준/규칙/판정) + 애니메이션
# - 목표: 학습/시연용. 로직을 '보여주기'에 최적화된 설명형 구현.
# - 핵심 아이디어:
# (1) 트리는 레벨(BFS) 단위로 평면 좌표에 배치해 ASCII로 출력
# (2) 하이라이트: current=[X], visited=(X)로 표기
# (3) 힙은 배열 인덱스 ↔ 트리 포인터를 동기화해 시각화
# (4) '선택 기준/규칙/판정' 메시지로 학습 흐름을 문자로 안내
# ======================================================
import os, time
# ──────────────────────────────────────────────────────
# [공용 포인터 노드] : 출력/하이라이트에 사용
# - 값/왼자/오른자만 갖는 가벼운 구조. 학습용 시각화 포맷에 맞춤.
# - BST, Heap 배열을 모두 '포인터 트리'로 바꿔 출력할 때 재사용.
# ──────────────────────────────────────────────────────
class Node:
def __init__(self, value, left=None, right=None):
# value: 어떤 자료형도 가능(str/int 등). 출력 시 str()로 변환.
self.value, self.left, self.right = value, left, right
# ======================================================
# 대시(—) 도식 렌더러 (하이라이트 지원 + 괄호 잘림 방지 패치)
# - current 노드는 [X], 방문 노드는 (X) 로 출력(겹치면 current 우선)
# - 출력 폭 계산/넘침 보정/간격 유지가 핵심
# - spread: 레벨이 내려갈수록 좌우 확산 폭 축소 비율(0~1)
# - left_pad/right_pad: 괄호/대괄호 추가로 늘어난 폭을 안전하게 흡수
# ======================================================
def print_ascii_tree(root, current=None, visited=None,
cell=3, hpad=2, dash='-',
spread=0.4, left_pad=None, right_pad=None):
if not root:
print("(empty)")
return
# visited가 None이면 빈 set()으로. (가변 기본값 방지 패턴)
visited = visited or set()
# ── [1] 레벨 구성(BFS) : 부족한 자리는 None으로 채워 '완전 이진트리 형태'를 유지
# 이유: 좌표 계산(센터 확산)에 빈자리가 섞여도 인덱스가 어긋나지 않게 하기 위해.
levels, q = [], [root]
while any(q): # 현재 레벨에 실제 노드가 하나라도 있으면 진행
levels.append([n for n in q])
nq = []
for n in q:
if n: nq += [n.left, n.right]
else: nq += [None, None] # 빈 자리도 2칸 유지(다음 레벨 인덱스 보존)
q = nq
height = len(levels)
# ── [2] 텍스트 생성 규칙: 하이라이트 표기
# current=[X], visited=(X), 일반은 X
def text_of(n):
if not n: return ""
base = str(n.value)
# current가 visited에도 포함될 수 있으므로 current를 먼저 검사
if n is current: return f"[{base}]"
if n in visited: return f"({base})"
return base
# nodew: 노드 셀의 최소 폭(간격 보장) = max(cell, 표시 텍스트 최대 길이)
# - []/()등 장식 포함 길이를 반영해서 겹침 방지
nodew = max(cell, max(len(text_of(n)) for lvl in levels for n in lvl if n))
# base: 최하층 기준 폭 스케일(2^(h-1) * (nodew + hpad))
# - 깊이가 1 증가할 때마다 >> 1 (절반)로 줄여 확산폭 감소
base = (1 << (height - 1)) * (nodew + hpad)
# ── [3] 레벨별 센터 x좌표 계산
centers = []
for depth, lvl in enumerate(levels):
raw = (base >> depth) # 깊어질수록 간격 반감
off = max(nodew, int(raw * spread)) # spread로 확산을 '완만하게' 통제
if depth == 0:
centers.append([0]) # 루트는 x=0을 기준으로
else:
prev, curc = centers[-1], []
for p_x in prev:
# 부모 센터에서 좌/우로 off만큼 떨어진 지점에 자식 센터 배치
curc += [p_x - off, p_x + off]
centers.append(curc)
# ── [4] 전체 좌표 평행 이동 및 여백 설정
# - 괄호/대괄호로 인해 왼쪽이 잘리는 문제를 패딩으로 흡수
allx = [x for row in centers for x in row]
minx, maxx = min(allx), max(allx)
# 좌우 패딩 기본값: nodew+1. (문자 폭+여유 1칸)
LEFT_PAD = (nodew + 1) if left_pad is None else left_pad
RIGHT_PAD = (nodew + 1) if right_pad is None else right_pad
# shift: 전체를 오른쪽으로 민다(최소 x가 LEFT_PAD가 되도록)
shift = -minx + LEFT_PAD
# width: 좌/우 패딩 + 노드폭 고려 + 여유 2
width = (maxx - minx) + LEFT_PAD + RIGHT_PAD + nodew + 2
rows = height * 2 - 1 # 노드행과 대시행을 번갈아 배치
grid = [[" "] * width for _ in range(rows)]
# ── [5] 텍스트 그리기(중앙 정렬 + 좌/우 넘침 보정)
def put_text(r, cx, s):
# cx는 '센터 좌표', shift를 더해 그리드 좌표로 환산
start = int(cx + shift - len(s)//2)
# 좌측 넘침 시 앞부분 잘라내기(안전 출력)
if start < 0:
s = s[-start:]
start = 0
end = start + len(s)
# 우측 넘침 시 뒷부분 잘라내기
if end > width:
s = s[:width - start]
end = width
# 실제 그리드에 문자 배치
for i, ch in enumerate(s):
x = start + i
if 0 <= r < rows and 0 <= x < width:
grid[r][x] = ch
# ── [6] 부모-자식 사이 대시 연결
# '대시 블록 사이 1칸 공백'을 보장해 좌/우 연결선이 붙어보이지 않게 함.
def put_dash_between_centers(r, parent_cx, child_cx):
pc = int(parent_cx + shift) # 부모 기준 열
cc = int(child_cx + shift) # 자식 기준 열
if cc < pc:
# 왼쪽 자식: [cc, pc)까지 대시, pc는 공백(1칸)으로 남겨 간격 확보
for x in range(cc, pc):
grid[r][x] = dash
elif cc > pc:
# 오른쪽 자식: (pc, cc]까지 대시, pc는 공백(1칸)으로 남김
for x in range(pc+1, cc+1):
grid[r][x] = dash
# cc == pc는 비정상(같은 열) → 아무것도 하지 않음
# ── [7] 각 레벨 출력(노드행 + 대시행)
for d, lvl in enumerate(levels):
node_row = d * 2
# 노드 텍스트 출력
for i, n in enumerate(lvl):
if n: put_text(node_row, centers[d][i], text_of(n))
# 마지막 레벨이 아니면 연결 대시 출력
if d < height - 1:
dash_row = node_row + 1
for i, n in enumerate(lvl):
if not n: continue
p_x = centers[d][i]
li, ri = i*2, i*2+1
lc, rc = levels[d+1][li], levels[d+1][ri]
if lc: put_dash_between_centers(dash_row, p_x, centers[d+1][li])
if rc: put_dash_between_centers(dash_row, p_x, centers[d+1][ri])
# ── [8] 행 단위로 출력. 우측 공백은 rstrip()으로 제거해 화면 폭 최적화.
for r in range(rows):
line = "".join(grid[r]).rstrip()
if line: print(line)
# ======================================================
# Binary Search Tree (삽입/삭제 + 출력 변환)
# - 내부 저장은 간단한 전용 노드(_N)로 관리
# - 출력할 때만 공용 Node로 변환(as_node) → 시각화 모듈 재사용
# - 삽입/삭제는 전형적 BST 규칙(중복은 무시)
# ======================================================
class BST:
class _N:
def __init__(self, v):
self.value, self.left, self.right = v, None, None
def __init__(self):
self.root = None
def insert(self, x):
# 평균 O(log n), 최악 O(n). (평균=균형에 근접, 최악=사슬)
if not self.root:
self.root = BST._N(x); return
cur = self.root
while True:
if x < cur.value:
if cur.left: cur = cur.left
else: cur.left = BST._N(x); return
elif x > cur.value:
if cur.right: cur = cur.right
else: cur.right = BST._N(x); return
else:
# x == cur.value → 중복 무시(집합처럼)
return
def _min_node(self, n):
# n 서브트리의 최소값 노드(가장 왼쪽). 삭제 시 '중위 후속자' 탐색에 사용.
while n.left: n = n.left
return n
def _delete(self, n, x):
# 표준 BST 삭제: 3케이스(자식 0/1/2)
if not n: return None
if x < n.value:
n.left = self._delete(n.left, x)
elif x > n.value:
n.right = self._delete(n.right, x)
else:
# [케이스 A] 리프(자식 0) → 바로 제거(None 반환)
if not n.left and not n.right: return None
# [케이스 B] 자식 1 → 그 자식을 올림
if not n.left: return n.right
if not n.right: return n.left
# [케이스 C] 자식 2 → 오른쪽 서브트리의 최소값(중위 후속자)로 대체 후, 해당 노드 삭제
succ = self._min_node(n.right)
n.value = succ.value
n.right = self._delete(n.right, succ.value)
return n
def delete(self, x):
# 루트 갱신을 위해 _delete의 반환값을 루트에 재대입
self.root = self._delete(self.root, x)
# 출력용 포인터 트리로 변환
# - 내부 _N → 공용 Node 로 1:1 복제
def as_node(self):
def cv(n): return None if not n else Node(n.value, cv(n.left), cv(n.right))
return cv(self.root)
# 값→노드 매핑(하이라이트용) : BST 값이 유일하다는 가정
# - 출력용 Node 트리에서 value -> Node 객체를 찾아 빠르게 접근하기 위함
def build_value_map(root):
m = {}
def dfs(n):
if not n: return
m[n.value] = n
dfs(n.left); dfs(n.right)
dfs(root)
return m
# 값으로 하이라이트 지정해 그리기
def render_by_values(root, current_value=None, visited_values=None, title=None):
# value → Node 매핑으로 current/visited를 Node 세트로 변환
vmap = build_value_map(root) if root else {}
cur = vmap.get(current_value) if current_value is not None else None
visited_nodes = {vmap[v] for v in (visited_values or []) if v in vmap}
if title: print(title)
print_ascii_tree(root, current=cur, visited=visited_nodes)
# ======================================================
# BST 애니메이션(삽입/삭제) : 선택 기준 / 규칙 / 판정 메시지
# - 실제 삽입/삭제 호출 전후로 '경로 시각화' → 왜 그리로 가는지 메시지로 설명
# - as_node()로 포인터 트리 생성 후 값을 기준으로 하이라이트
# ======================================================
def animate_bst_insertions(bst, values, delay=0.7, clear_each_frame=True, name="BST"):
for x in values:
# 삽입 위치까지 '비정식 탐색'을 수행해 경로 안내(학습용 시각화)
path, cur = [], bst.root
while cur:
path.append(cur.value) # 방문 기록(visited 하이라이트용)
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
title = f"=== {name} INSERT 경로: 삽입값 {x} / 현재 노드 {cur.value} ==="
render_by_values(bst.as_node(), current_value=cur.value, visited_values=path[:-1], title=title)
print("\n선택 기준: 삽입값 vs 현재 노드 비교")
print("규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽 / x == 노드 → 중복(삽입 안 함)")
if x < cur.value:
print("판정: 왼쪽으로 이동"); time.sleep(delay); cur = cur.left
elif x > cur.value:
print("판정: 오른쪽으로 이동"); time.sleep(delay); cur = cur.right
else:
print("판정: 중복 값 → 삽입 생략"); time.sleep(delay*0.8); break
# 실제 삽입 호출(중복이면 내부에서 무시)
bst.insert(x)
# 삽입 후 결과 시각화
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), current_value=x, visited_values=path, title=f"=== {name} INSERT 완료: {x} ===")
print("\n요약: 삽입 규칙에 따라 최종 위치에 노드 추가됨")
time.sleep(delay)
def animate_bst_deletion(bst, x, delay=0.9, clear_each_frame=True, name="BST"):
# 1) 삭제 대상 탐색 경로 시각화
path, cur = [], bst.root
while cur and cur.value != x:
path.append(cur.value)
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), current_value=cur.value, visited_values=path[:-1],
title=f"=== {name} DELETE 탐색: 삭제값 {x} / 현재 노드 {cur.value} ===")
print("\n선택 기준: 삭제값 vs 현재 노드 비교")
print("규칙: x < 노드 → 왼쪽 / x > 노드 → 오른쪽")
if x < cur.value:
print("판정: 왼쪽으로 이동"); time.sleep(delay); cur = cur.left
else:
print("판정: 오른쪽으로 이동"); time.sleep(delay); cur = cur.right
# 못 찾은 경우 안내 후 종료
if not cur or cur.value != x:
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
print(f"값 {x} 를 찾을 수 없습니다."); time.sleep(delay*0.6); return
# 대상 하이라이트
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), current_value=x, visited_values=path, title=f"=== {name} DELETE 대상 확인: {x} ===")
time.sleep(delay)
# 2) 케이스 판정(0/1/2 자식)
p = bst.root
while p and p.value != x:
p = p.left if x < p.value else p.right
hasL, hasR = bool(p.left), bool(p.right)
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), current_value=x, visited_values=path, title=f"=== {name} DELETE 케이스 판정: {x} ===")
if (not hasL) and (not hasR):
print("\n케이스: 자식 0개(리프)")
print("규칙: 리프는 바로 제거")
print("판정: 부모 포인터를 None으로")
time.sleep(delay); bst.delete(x)
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), title="=== 삭제 후 트리 ==="); time.sleep(delay*0.8); return
if hasL ^ hasR:
print("\n케이스: 자식 1개")
print("규칙: 자식을 부모 위치로 승격")
print("판정: 해당 자식 서브트리를 위로 올림")
time.sleep(delay); bst.delete(x)
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), title="=== 삭제 후 트리 ==="); time.sleep(delay*0.8); return
# 자식 2개 케이스
print("\n케이스: 자식 2개")
print("규칙(후속자): 중위 후속자 = 오른쪽 서브트리의 '최소' 노드")
print("판정: 대상 값 ← 후속자 값 교체 후, 후속자 노드 삭제")
time.sleep(delay)
# 3) 후속자 탐색(오른쪽으로 1칸 → 왼쪽 끝으로 가기)
q = p.right
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), current_value=q.value if q else None, visited_values=[x],
title="=== 후속자 탐색 시작: 오른쪽 서브트리로 이동 ===")
print("\n선택 기준: 오른쪽으로 1칸 이동 후 왼쪽 끝까지")
print("규칙: 왼쪽 자식이 있으면 계속 왼쪽으로 이동")
time.sleep(delay)
while q and q.left:
q = q.left
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), current_value=q.value, visited_values=[x],
title="=== 후속자 탐색: 왼쪽으로 이동 ===")
print("\n선택 기준: 현재 노드의 왼쪽 존재 여부")
print("판정: 왼쪽으로 이동"); time.sleep(delay)
succ_value = q.value if q else None
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
print(f"=== 값 교체(개념): 대상 {x} ← 후속자 {succ_value} ===")
print("\n설명: 실제 구현은 '대상에 후속자 값을 대입' 후 '후속자 노드 삭제'입니다.")
time.sleep(delay*0.8)
# 실제 삭제 수행(대상 x를 삭제하면 내부에서 후속자 치환/삭제가 일어남)
bst.delete(x)
if clear_each_frame: os.system('cls' if os.name == 'nt' else 'clear')
render_by_values(bst.as_node(), title="=== 삭제 완료 (자식 2개 케이스) ===")
time.sleep(delay)
[코드 실행 - 출력 보기] add와 delete의 적용 결과를 실행하여 출력하는 실행 코드.
# ======================================================
# 실행 예시
# [1]에 ‘추가 5 → 추가 2 → 추가 9’와
# ‘삭제 1(리프) → 삭제 14(자식 1개) → 삭제 3(자식 2개)’를 순서대로 출력
# [2]~[4] 기존 애니메이션 유지
# ======================================================
if __name__ == "__main__":
# --- [1] BST 기본 출력 + 단계별 삽입/삭제(정적) ---
print("=== [1] BST (Top-Down 출력) ===")
bst = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst.insert(v)
# '*' 개수
stars = 100
print("초기 BST:")
print("설명: 루트 8을 기준으로, 작은 값은 왼쪽 서브트리에, 큰 값은 오른쪽 서브트리에 배치됩니다.")
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
print("# 추가한 경우")
print("\n" + '*' * stars + "\n")
# 추가 5
print("\n추가 숫자 : 5:")
print("설명: 5 < 8 → 왼쪽(3) → 5 > 3 → 오른쪽(6) → 5 < 6 → 왼쪽(4) → 5 > 4 → 4의 오른쪽에 삽입.")
bst.insert(5)
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
# 추가 2
print("\n추가 숫자 : 2:")
print("설명: 2 < 8 → 왼쪽(3) → 2 < 3 → 왼쪽(1) → 2 > 1 이므로 1의 오른쪽에 삽입.")
bst.insert(2)
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
# 추가 9
print("\n추가 숫자 : 9:")
print("설명: 9 > 8 → 오른쪽(10) → 9 < 10 이므로 10의 왼쪽에 삽입.")
bst.insert(9)
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
print("# 삭제한 경우")
print("\n" + '*' * stars + "\n")
# 삭제 2 (리프)
print("\n삭제 숫자 : 2 (리프):")
print("설명: 2는 1의 오른쪽 리프이므로, 부모(1)의 오른쪽 포인터를 None으로 바꿔 바로 제거.")
bst.delete(2)
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
# 삭제 14 (자식 1개)
print("\n삭제 숫자 : 14 (자식 1개):")
print("설명: 14의 유일한 자식은 13(왼쪽). 14를 제거하고 13 서브트리를 부모(10)의 오른쪽 자리에 승격.")
bst.delete(14)
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
# 삭제 6 (자식 2개)
print("\n삭제 숫자 : 6 (자식 2개):")
print("설명: 6은 왼쪽(4)·오른쪽(7) 두 자식 보유 → 중위 후속자 = 오른쪽 서브트리의 최소값(7)으로 값 교체 후, 원래 7 노드를 삭제.")
bst.delete(6)
print_ascii_tree(bst.as_node())
print("\n" + '*' * stars + "\n")
[코드 실행 - 출력 보기] 위 add와 delete의 적용 결과를 단계별로 적용된 규칙을 보다 자세하게 출력해서 보기.
# --- [2] BST 애니메이션(선택 기준/규칙/판정 메시지) ---
print("\n=== [2] BST 삽입/삭제 애니메이션 ===")
stars = 100
# 애니메이션 전용 트리: '초기 BST' 상태에서 시작)
bst_anim = BST()
for v in [8, 3, 10, 1, 6, 14, 4, 7, 13]:
bst_anim.insert(v)
# 삽입 5
print("설명: 5 < 8 → 왼쪽(3) → 5 > 3 → 오른쪽(6) → 5 < 6 → 왼쪽(4) → 5 > 4 → 4의 오른쪽에 삽입.")
animate_bst_insertions(bst_anim, values=[5], delay=0.5, clear_each_frame=False, name="BST")
print("\n" + '*' * stars + "\n")
# 삽입 2
print("설명: 2 < 8 → 왼쪽(3) → 2 < 3 → 왼쪽(1) → 2 > 1 → 1의 오른쪽에 삽입.")
animate_bst_insertions(bst_anim, values=[2], delay=0.5, clear_each_frame=False, name="BST")
print("\n" + '*' * stars + "\n")
# 삽입 9
print("설명: 9 > 8 → 오른쪽(10) → 9 < 10 → 10의 왼쪽에 삽입.")
animate_bst_insertions(bst_anim, values=[9], delay=0.5, clear_each_frame=False, name="BST")
print("\n" + '*' * stars + "\n")
# 삭제 2 (리프)
print("설명: 2는 1의 오른쪽 리프이므로 부모(1)의 오른쪽 포인터를 None으로 변경하여 바로 제거.")
animate_bst_deletion(bst_anim, x=2, delay=0.7, clear_each_frame=False, name="BST")
print("\n" + '*' * stars + "\n")
# 삭제 14 (자식 1개)
print("설명: 14는 자식이 1개(왼쪽 13) → 부모(10)의 오른쪽 자식 포인터를 13으로 연결해 승격.")
animate_bst_deletion(bst_anim, x=14, delay=0.7, clear_each_frame=False, name="BST")
print("\n" + '*' * stars + "\n")
# 삭제 6 (자식 2개)
print("설명: 6은 왼쪽(4)·오른쪽(7) 두 자식 보유 → 중위 후속자(7)로 값 교체 후, 원래 7 노드를 삭제.")
animate_bst_deletion(bst_anim, x=6, delay=0.7, clear_each_frame=False, name="BST")
print("\n" + '*' * stars + "\n")
코드는 최대한 상세한 설명과 주석을 첨부하여 우선 이렇게 정리해두자. 이 코드에 쓰인 기능들과 구현 방식에 대한 이해는 계속 익숙해지도록 먼저 반복해서 계속 숙달해보자. 우선 트리에 대해서 이미지를 떠올리면서 이해하는 것에 집중하고, 앞으로 필요한 것들만 추려서 스스로 구현할 수 있도록 노력하자! 그렇게 한 걸음씩~~~ 해내야 한다.
즐거운 파이썬~ 즐 파이씽~!
[주의] 내용에 오류가 있을 수 있습니다.
'[Code] Study & Practice' 카테고리의 다른 글
| [Python] MySQL & Jupyter 연동 - 객체지향 프로그래밍(OOP)을 활용한 DB 작업 프로그램 예제 (0) | 2025.11.05 |
|---|---|
| [Python] 자료 구조5 - 힙(Heap)의 개념, 구조, 규칙 (0) | 2025.11.01 |
| [Python] 자료 구조3 - Hash table의 개념과 index 충돌 해결 방식 비교 (0) | 2025.10.30 |
| [Python] 자료 구조2 - Single & Double Linked List(연결 리스트)의 개념과 차이점 (1) | 2025.10.28 |
| [Python] 자료 구조1 - 스택(Stack)과 큐(Queue)의 개념과 차이점 (0) | 2025.10.27 |