트리 구조란 나무를 거꾸로 뒤집어 놓은 형태의 자료구조입니다.
사장을 최상위로, 그 아래 부서장, 팀원 등이 계층 구조를 이루는 형태입니다.
상위 폴더 안에 하위 폴더들이 계속 이어져 있는 구조입니다. C:\Users\Documents 처럼 경로가 만들어집니다.
조상부터 시작하여 자손이 아래로 이어지는 형태도 트리 구조입니다.
A tree structure is a data structure shaped like an upside-down tree.
The CEO is at the top, followed by department heads and team members forming a hierarchical structure.
Subfolders are nested inside parent folders. Paths like C:\Users\Documents are formed this way.
Starting from ancestors, descendants branch out downward — another tree structure.
Trees are everywhere: file systems, HTML DOM, database indexes, AI decision trees — they all use tree structures!
| 용어 | 설명 |
|---|---|
| 루트(Root) | 트리의 최상위 노드 |
| 부모(Parent) | 상위에 연결된 노드 |
| 자식(Child) | 하위에 연결된 노드 |
| 리프(Leaf) | 자식이 없는 맨 아래 노드 |
| 서브 트리 | 특정 노드 아래의 부분 트리 |
| 레벨(Level) | 루트를 0으로 하여 내려갈 때 증가 |
| 높이(Height) | 트리의 최대 레벨 |
모든 노드의 자식이 최대 2개인 트리입니다. 각 노드는 왼쪽 자식과 오른쪽 자식만 가질 수 있습니다.
| Term | Description |
|---|---|
| Root | The topmost node of the tree |
| Parent | A node connected above |
| Child | A node connected below |
| Leaf | A node with no children (bottom) |
| Subtree | A partial tree below a given node |
| Level | Increases from 0 (root) going down |
| Height | Maximum level of the tree |
A tree where every node has at most 2 children. Each node can have only a left child and a right child.
The word "binary" means two. A binary tree limits each node to a maximum of two branches — left and right.
모든 레벨의 노드가 꽉 차 있는 트리. 리프 노드가 모두 같은 레벨에 있습니다.
마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 채워진 트리입니다.
한쪽으로만 노드가 이어진 트리. 왼쪽 편향 또는 오른쪽 편향이 있습니다.
Every level is completely filled. All leaf nodes are at the same level.
All levels are full except possibly the last, which is filled from left to right.
Nodes extend in only one direction — left-skewed or right-skewed. Essentially a linked list.
A skewed tree has O(n) search time — the same as a linked list. A balanced tree gives O(log n). That's the difference between searching 1,000,000 nodes in 1M steps vs. 20 steps!
이진 트리의 노드는 세 부분으로 구성됩니다: 왼쪽 링크(left), 데이터(data), 오른쪽 링크(right).
Each node has three parts: left link, data, and right link.
We define a simple class with three attributes: left (pointer to left child), data (the value stored), and right (pointer to right child). Initially all are None.
node1 with data '화사'node2 ('솔라'), set as root's left childnode3 ('문별'), set as root's right childnode4 ('휘인'), node5 ('쯔위'), node6 ('선미') and link them to their parents화사 솔라 문별 휘인 쯔위 선미
node1.left.right.data means: from root → go left → go right → read data. This chain-style access is fundamental to tree traversal.
이진 트리의 모든 노드를 한 번씩 방문하는 것을 순회라고 합니다. 데이터 처리 순서에 따라 세 가지로 나뉩니다.
| 순회 방식 | 순서 | 기억법 |
|---|---|---|
| 전위 순회 | 현재 → 왼쪽 → 오른쪽 | 루왼오 |
| 중위 순회 | 왼쪽 → 현재 → 오른쪽 | 왼루오 |
| 후위 순회 | 왼쪽 → 오른쪽 → 현재 | 왼오루 |
전위: 화사→솔라→휘인→쯔위→문별→선미
중위: 휘인→솔라→쯔위→화사→선미→문별
후위: 휘인→쯔위→솔라→선미→문별→화사
Traversal means visiting every node exactly once. Three methods differ by when the current node is processed.
| Traversal | Order | Mnemonic |
|---|---|---|
| Preorder | Root → Left → Right | RLR |
| Inorder | Left → Root → Right | LRR |
| Postorder | Left → Right → Root | LRR |
All three traversals use the same recursive structure — only the position of print(node.data) changes!
Pre: 화사→솔라→휘인→쯔위→문별→선미
In: 휘인→솔라→쯔위→화사→선미→문별
Post: 휘인→쯔위→솔라→선미→문별→화사
print()의 위치만 다릅니다! 전위는 맨 위, 중위는 중간, 후위는 맨 아래에 놓습니다. 재귀 호출이 트리를 자동으로 탐색합니다.
The only difference is where print() is placed:
Preorder: print BEFORE recursive calls
Inorder: print BETWEEN recursive calls
Postorder: print AFTER recursive calls
if node == None: return stops the recursion when we reach an empty child. Without this, the function would crash with an AttributeError.
전위 순회 : 화사->솔라->휘인->쯔위->문별->선미->끝 중위 순회 : 휘인->솔라->쯔위->화사->선미->문별->끝 후위 순회 : 휘인->쯔위->솔라->선미->문별->화사->끝
TreeNode 클래스로 6개 노드(화사, 솔라, 문별, 휘인, 쯔위, 선미)의 이진 트리를 만들고 레벨별로 출력하시오. (Code08-01)
8개 노드 트리(화사→솔라/문별, 솔라→휘인/쯔위, 문별→선미, 휘인→다현(오른쪽), 선미→사나(오른쪽))를 생성하고, 전위·중위·후위 순회 결과를 출력하시오. (Self08-01)
Create a binary tree with 6 nodes (화사, 솔라, 문별, 휘인, 쯔위, 선미) using TreeNode class and print level by level. (Code08-01)
화사 솔라 문별 휘인 쯔위 선미
Build an 8-node tree (adding 다현 as 휘인's right child, 사나 as 선미's right child) and print preorder, inorder, and postorder results. (Self08-01)
전위: 화사->솔라->휘인->다현->쯔위->문별->선미->사나->끝 중위: 휘인->다현->솔라->쯔위->화사->선미->사나->문별->끝 후위: 다현->휘인->쯔위->솔라->사나->선미->문별->화사->끝
데이터의 크기를 기준으로 정렬된 이진 트리입니다. 활용도가 매우 높습니다.
한글은 가나다 순서로 비교합니다. '걸스데이' < '레드벨벳' < '마마무' < '블랙핑크' < '에이핑크' < '트와이스'
A Binary Search Tree (BST) is a binary tree organized by data values for efficient searching.
Searching a BST is like a binary search on a sorted array — at each node, you eliminate half the remaining data. Average search time is O(log n).
Python compares Korean strings by their Unicode (가나다) order. So '걸스데이' < '블랙핑크' is True in Python.
배열의 데이터를 순서대로 BST에 삽입합니다.
'레드벨벳' < '블랙핑크' → go left → left is None → insert as left child
'에이핑크' > '블랙핑크' → go right → right is None → insert as right child
'마마무' < '블랙핑크' → left → '마마무' > '레드벨벳' → right → None → insert
The while True loop walks down the tree until it finds an empty slot. The comparison name < current.data decides left vs. right at each step.
BST에서 '마마무'를 찾는 과정을 살펴봅니다.
Searching follows the same left/right logic as insertion.
findName == current.data → Found!findName < current.data → go leftfindName > current.data → go rightNone → Not foundWith 6 nodes, we found '마마무' in just 3 comparisons. In a balanced BST with 1,000,000 nodes, it takes at most ~20 comparisons!
마마무 을(를) 찾음.
자식이 없는 노드. 부모의 해당 링크를 None으로 설정하고 삭제합니다.
왼쪽 또는 오른쪽 자식만 있는 경우. 부모의 링크를 자식 노드로 연결합니다.
가장 복잡한 경우. 재귀를 사용해야 편리합니다.
No children. Simply set parent's link to None and delete the node.
Only left or right child exists. Connect parent's link directly to the grandchild, bypassing the deleted node.
Most complex case — requires finding a replacement node (typically the inorder successor or predecessor).
We need both current (the node to delete) and parent (to re-link). The search loop updates parent = current before moving to the next node.
마마무 이(가) 삭제됨.
['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스'] 배열로 BST를 구성하고, '마마무'를 검색하시오. (Code08-03 + Code08-04)
8개 그룹(['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스', '잇지', '여자친구'])으로 BST를 구성하고, 사용자가 입력한 그룹을 검색하시오. (Self08-02)
Build a BST from ['블랙핑크', '레드벨벳', '마마무', '에이핑크', '걸스데이', '트와이스'] and search for '마마무'. (Code08-03 + Code08-04)
마마무 을(를) 찾음.
Build a BST with 8 groups (adding '잇지', '여자친구') and search for a user-input group name. (Self08-02)
찾을 그룹이름--> 잇지 잇지 을(를) 찾았음.
도서관에 새로 입고된 책 정보를 두 개의 BST로 관리합니다. 책 이름 트리와 작가 이름 트리를 따로 구성하여 두 가지 방식으로 검색할 수 있습니다.
A library manages books with two separate BSTs: one indexed by book title, another by author name. Users choose which to search.
rootBook → BST sorted by book title (book[0])rootAuth → BST sorted by author name (book[1])The program asks: "Book search (1) or Author search (2)?" then searches the appropriate tree.
The book array is shuffled before building the trees. This creates different tree shapes each run, but the search still works correctly — that's the power of BST!
책검색(1), 작가검색(2)--> 1 검색할 책 또는 작가--> 어린왕자 어린왕자 을(를) 찾음. 책검색(1), 작가검색(2)--> 2 검색할 책 또는 작가--> 괴테 괴테 을(를) 찾음.
The variable root is set to either rootBook or rootAuth based on the user's choice. The rest of the search code is identical — only the starting tree differs!
The BST search algorithm is the same regardless of what data is stored. Build the tree once, search many times — this is the BST's main advantage.
Book(1), Author(2)--> 1 Search--> 어린왕자 어린왕자 found. Book(1), Author(2)--> 2 Search--> 괴테 괴테 found.
하루 동안 판매된 물건 20개(중복 포함)에서 BST를 이용해 중복 없는 판매 종류를 출력합니다.
BST에 삽입할 때 이미 같은 데이터가 있으면 삽입하지 않고 건너뜁니다. 이렇게 하면 자동으로 중복이 제거됩니다!
20 items sold today (with duplicates). Use a BST to output only unique item types.
The key change: add if name == current.data: break at the top of the while loop. When a duplicate is found, simply skip it — don't insert.
After building the BST (duplicates removed), use preorder traversal to print all unique items.
오늘 판매된 물건(중복O) --> [20 items...] 이진 탐색 트리 구성 완료! 오늘 판매된 종류(중복X)--> 바나나맛우유 도시락 레쓰비캔커피 삼각김밥 삼다수 코카콜라 츄파춥스
특정 폴더와 그 하위 폴더에서 이름이 같은 파일들을 BST를 이용해 찾아냅니다.
Scan a folder tree and use a BST to detect files with the same name.
os.walk() collects all filenames recursivelyname == current.data → it's a duplicate! Add to dupNameAryset() to remove duplicate entries in the result listIn the convenience store example, duplicates were skipped. Here, duplicates are collected. The BST insertion loop is the same — only what happens on a match differs!
os.walk(folder) yields (dirName, subDirList, fileNames) for every directory in the tree. It's Python's built-in way to recursively list files.
| 연산 | 리스트 (정렬) | BST (균형) |
|---|---|---|
| 검색 | O(n) 또는 O(log n) | O(log n) |
| 삽입 | O(n) | O(log n) |
| 삭제 | O(n) | O(log n) |
| 중복 제거 | O(n²) | O(n log n) |
삽입과 동시에 정렬이 유지됩니다. 별도의 정렬 과정이 필요 없습니다. 검색, 삽입, 삭제 모두 O(log n)으로 효율적입니다.
데이터가 이미 정렬되어 있으면 편향 트리가 되어 O(n)이 됩니다. 이를 방지하기 위해 AVL 트리, 레드-블랙 트리 같은 균형 트리를 사용합니다.
| Operation | Sorted List | Balanced BST |
|---|---|---|
| Search | O(n) or O(log n) | O(log n) |
| Insert | O(n) | O(log n) |
| Delete | O(n) | O(log n) |
| Dedup | O(n²) | O(n log n) |
Data stays sorted as it's inserted — no separate sorting step needed. Search, insert, and delete are all O(log n) for balanced trees.
If data arrives already sorted, the BST degrades to O(n) — essentially a linked list. Self-balancing trees (AVL, Red-Black) prevent this.
7가지 물건 중 랜덤으로 20개를 판매한 후, BST를 이용해 중복 없는 판매 종류를 전위 순회로 출력하시오. (Ex08-01)
특정 폴더와 하위 폴더에서 os.walk()로 파일명을 수집한 뒤, BST를 이용해 중복된 파일 이름을 출력하시오. (Ex08-02)
From 7 products, randomly sell 20 items. Use a BST to print unique item types via preorder traversal. (Ex08-01)
오늘 판매된 물건(중복O) --> [20 items...] 이진 탐색 트리 구성 완료! 오늘 판매된 종류(중복X)--> 바나나맛우유 도시락 레쓰비캔커피 삼각김밥 삼다수 코카콜라 츄파춥스
Collect filenames from a folder tree using os.walk(), then use a BST to find and print duplicate file names. (Ex08-02)
각 노드가 최대 2개의 자식을 가지는 트리 구조. TreeNode 클래스로 left, data, right 세 필드를 구현합니다.
전위(루왼오), 중위(왼루오), 후위(왼오루) — print()의 위치만 다릅니다. 모두 재귀로 구현합니다.
왼쪽 < 루트 < 오른쪽 규칙으로 정렬된 이진 트리. 삽입, 검색, 삭제 모두 O(log n)으로 효율적입니다.
중복 제거(편의점 판매), 중복 탐지(파일 검색), 다중 인덱스(도서관 검색) 등 실용적인 활용이 가능합니다.
Chapter 9에서는 그래프(Graph)를 학습합니다. 트리는 그래프의 특수한 형태입니다!
A tree where each node has at most 2 children. TreeNode class implements left, data, right fields.
Preorder (Root-L-R), Inorder (L-Root-R), Postorder (L-R-Root) — only the position of print() differs. All use recursion.
A sorted binary tree: left < root < right. Insert, search, delete all run in O(log n) for balanced trees.
Deduplication (store sales), duplicate detection (file search), multi-index search (library) — practical and powerful.
Chapter 9 covers Graphs. A tree is actually a special case of a graph!