이 레슨과 관련된 학습 키워드
컴퓨터 과학 & 프로그래밍 — 문제 해결의 도구 → 자료구조 — 효율적인 데이터 관리의 핵심 → 자료구조 — 효율적인 데이터 관리의 핵심 → 트리와 그래프
AVL rotations, Red-Black tree properties, B-Tree and B+Tree for databases, self-balancing principles, and practical selection guide.
1→2→3→4→5→6→7 (높이 6, 연결 리스트!) 4여러분, 오늘은 왜 균형 트리가 필요한지부터 이야기해 볼게요.
그림 왼쪽을 보세요, 정렬된 데이터를 BST에 넣으면 이렇게 한쪽으로 치우쳐요.
1, 2, 3, 4, 5를 순서대로 넣으면 일직선이 됩니다.
이건 사실상 연결 리스트와 다를 바가 없어요.
검색하려면 맨 위부터 하나씩 내려가야 하니 O(n)이 걸려요.
이제 오른쪽 균형 트리를 보세요.
같은 데이터인데 3이 루트이고 양쪽에 골고루 분배되어 있죠.
높이가 2밖에 안 되니까 검색이 O(log n)이에요.
100만 개 데이터에서 편향 BST는 100만 번, 균형은 20번이면 찾아요.
오른쪽 표를 보면 차이가 극명하죠.
삽입도 삭제도 마찬가지로 O(n) 대 O(log n)이에요.
그러면 어떻게 자동으로 균형을 맞출 수 있을까요?
그것이 바로 자가 균형 트리, Self-Balancing Tree예요.
삽입이나 삭제를 할 때마다 트리 구조를 조정해서 높이를 낮게 유지해요.
대표적으로 AVL 트리, Red-Black 트리, B-Tree가 있어요.
AVL은 1962년에 나온 최초의 자가 균형 트리예요.
Red-Black은 자바와 C++ 표준 라이브러리에서 쓰이고요.
B-Tree는 데이터베이스 인덱스에 핵심적으로 사용돼요.
이번 레슨에서 세 가지를 모두 깊이 있게 배워 볼 거예요.
먼저 AVL 트리부터 시작합시다.
선생님: 정렬된 데이터 1부터 7까지를 일반 BST에 넣으면 왜 문제가 될까요?
학생: 오른쪽으로만 계속 내려가서 일직선이 되고 연결 리스트처럼 O(n)이 되기 때문이에요.
선생님: 맞아요. 그러면 자가 균형 트리는 이 문제를 어떻게 해결하나요?
학생: 삽입할 때마다 트리 구조를 자동으로 조정해서 높이를 log n으로 유지해요.
선생님: 정확해요! 100만 개 데이터에서 편향은 100만 번, 균형은 약 20번 비교면 충분하죠.
학생: 차이가 엄청나네요. AVL, Red-Black, B-Tree 중에 어떤 게 제일 많이 쓰여요?
선생님: 용도에 따라 달라요. 메모리에서는 Red-Black, 디스크에서는 B-Tree가 표준이에요.