BST2 자료구조 - BST와 균형트리 BST 균형트리 (AVL, RB, 자료구조)이진 트리 위에 "왼쪽은 작은 값, 오른쪽은 큰 값"이라는 단 한 줄의 정렬 규칙을 얹으면 곧바로 이진 탐색 트리(BST)가 된다. 이 한 규칙 덕분에 평균 O(log n) 시간에 탐색·삽입·삭제가 가능해지며, 자료구조 학습에서 처음 만나는 진짜 "실용적인" 트리이기도 하다. 다만 BST에는 결정적인 약점이 있는데, 데이터가 정렬된 순서로 들어오면 한쪽으로 편향되어 O(n)으로 떨어진다는 점이다. 이 약점을 해결하기 위해 등장한 것이 균형 트리(Balanced Tree)이며, 대표적으로 AVL 트리와 Red-Black(RB) 트리가 있다. 본 글은 BST의 정의·연산·시간복잡도부터 두 균형 트리의 차이까지 세심하게 정리한다(출처: 위키백과 — Binary Sea.. 2026. 5. 15. 자료구조 - 트리와 이진트리 트리 (이진트리, 순회, 자료구조)스택과 큐가 1차원 자료구조였다면, 트리는 한 단계 더 추상화된 계층 구조(hierarchical structure) 자료구조이다. 파일 시스템의 디렉터리, HTML DOM, 회사 조직도, 컴퓨터 게임의 의사 결정 흐름, 운영체제의 프로세스 트리까지 — 실세계의 거의 모든 "포함 관계"가 사실상 트리로 표현되며, 그 위에 정렬·탐색·압축 같은 거의 모든 고급 알고리즘이 얹어진다. 본 글은 정보처리기사 시험 출제 범위와 학교 자료구조 수업 입문 영역을 모두 닿도록 트리 일반·이진 트리·순회 알고리즘을 세심하게 정리한다(출처: 위키백과 — Tree (data structure)). 제가 학교 자료구조 시험에서 가장 자주 틀린 영역이 트리 순회의 결과 추적이었는데, 작은 트리.. 2026. 5. 15. 이전 1 다음