다섯 살도 알 수 있게 · 시스템SW
이진트리·이진탐색트리가 뭐예요?
이진트리와 이진탐색트리를, 갈림길마다 왼쪽·오른쪽만 골라 부품을 찾는 선반 지도 이야기로 풀어봤어요.
번호가 뒤죽박죽이면 한 줄로 늘어선 상자를 하나씩 다 열어봐야 해요.운 나쁘면 마지막 상자까지 다 열어봐야 해요.
한 줄로 가지런히 정렬해도, 앞에서부터 따라가면 여전히 하나씩 짚어요.맨 앞부터 따라가면 하나씩 짚어가야 하는 건 똑같아요.
이진트리 탐색 = 갈림길마다 후보를 반씩 줄여가는 선반 지도예요.19를 찾을 땐: 31보다 작으니 왼쪽 → 12보다 크니 오른쪽 → 19예요.
노드갈림길 하나, 부품 번호가 적힌 칸
왼쪽<나<오른쪽찾는 번호가 작으면 왼쪽, 크면 오른쪽
매번 반씩한 번 갈 때마다 후보가 절반으로
균형(Balance)트리가 쏠리면 반씩 줄이는 효과가 사라져요
찾는 번호가 갈림길 번호보다 작으면 왼쪽, 크면 오른쪽으로 가요.작은 값은 왼쪽, 큰 값은 오른쪽 규칙을 모든 갈림길에서 지켜요.
트리가 한쪽으로 쏠리면 탐색이 다시 한 줄처럼 느려져요.그래서 트리의 균형을 맞추는 알고리즘도 따로 있어요.
한 줄로
이진트리 = 갈림길마다 왼쪽·오른쪽 둘로만 갈라지는 지도. 이진탐색트리(BST)는 거기에 왼쪽은 작은 값, 오른쪽은 큰 값이라는 규칙을 더한 것.
이진트리는 각 노드가 최대 두 자식(왼쪽·오른쪽)을 갖는 트리 구조예요. 이진탐색트리(BST)는 여기에 '왼쪽 서브트리의 모든 값 < 노드 값 < 오른쪽 서브트리의 모든 값' 규칙을 더해, 탐색·삽입·삭제를 평균 O(log n)에 할 수 있게 해요. 하지만 삽입 순서가 한쪽으로 치우치면 트리가 일렬로 늘어서 최악의 경우 O(n)이 되고, 이를 막기 위해 AVL 트리·레드-블랙 트리 같은 균형 트리가 쓰여요.
어른들은 이렇게 불러요
- 노드
Node - 갈림길 하나, 부품 번호가 적힌 칸. 최대 두 개의 가지(왼쪽·오른쪽)를 가져요.
- 이진탐색트리(BST) 규칙
BST Rule - 왼쪽은 작은 값, 오른쪽은 큰 값. 모든 갈림길에서 똑같이 지켜져요.
- 균형(Balance)
Balance - 트리가 한쪽으로 쏠리지 않게 하는 것. 쏠리면 탐색이 다시 한 줄처럼 느려져요.
- 스택·큐(선형 구조)
Stack/Queue (linear structures) - 물건을 쌓거나 줄 세우는 한 줄짜리 규칙. 가지 없는 '한 줄' 구조는 여기서 다뤄요. → 상자는 쌓고, 차는 줄 세우고
- 복잡도(Big-O)
Time Complexity - 자료가 늘 때 걸리는 시간을 재는 자. 균형 트리는 O(log n), 한 줄은 O(n)이에요. → 차가 많아질 때 얼마나 느려질까
- 캐시 메모리
Cache Memory - 자주 쓰는 공구만 담는 작은 공구함. 자주 쓰는 걸 가까이 둬서 빠르게 하는 다른 방법이에요. → 바로 옆에 놓아둔 공구함
- 가상메모리·페이지 테이블
Virtual Memory/Page Table - 가상 칸과 진짜 칸의 대응표. 실제로는 페이지 테이블도 트리 모양으로 구현되곤 해요. → 창고 전체를 내 것처럼 보여주는 가짜 지도
- CPU 스케줄링
CPU Scheduling - 순서판에 적힌 차 순서 규칙. 일부 스케줄러도 내부적으로 트리 구조를 써요. → 리프트에 누가 먼저 올라갈까
다음 이야기
차가 많아질 때 얼마나 느려질까 →