이진 탐색 트리가 한쪽으로 치우치면 무엇이 문제인가?

연결 리스트가 된다. 탐색이 절반씩 줄어든다는 전제가 깨져서 O(log n)이 O(n)으로 내려앉는다. 정렬된 데이터를 순서대로 넣으면 실제로 이 모양이 나온다.

그래서 스스로 균형을 잡는 트리를 쓴다. 넣거나 지울 때 높이 차이를 확인하고 회전으로 맞춘다. 회전 비용이 붙지만 최악을 O(log n)으로 묶는 값이다.

해시 테이블과 갈리는 지점은 순서다. 해시는 단건 조회가 더 빠르지만 범위 질의와 정렬 순회를 못 한다. "20에서 30 사이"를 물어야 하면 트리 쪽이다.

데이터베이스 인덱스가 이진 트리 대신 B-트리를 쓰는 이유도 여기 있다. 디스크는 블록 단위로 읽으므로 한 노드에 키를 많이 담아 높이를 낮추는 편이 유리하다.