AVL 트리

노드가 삽입될 때의 사진이다.
1-2 노드 오른쪽에 3이 추가가 되면 왼쪽 서브트리와 오른쪽 서브 트리의 높이 차이가 1보다 크기 때문에 왼쪽으로 회전하게 된다.

노드가 삭제될 때의 사진이다.
2-1-3-4 의 노드에서 왼쪽에 있는 2번이 삭제되면 오른쪽 서브트리의 높이 차이가 2보다 크기 때문에 왼쪽으로 회전한다.

AVL 트리와 레드-블랙 트리의 차이점

항목	AVL 트리	레드-블랙 트리
균형 유지 방식	높이 기반	색상 기반 (Red/Black)
균형 조건	서브트리 높이 차이 <= 1	루트에서 리프까지의 블랙 노드 수 동일
삽입/삭제 비용	자주 회전 (비용 높음)	적은 회전 (비용 낮음)
탐색 속도	상대적으로 빠름 (균형 잡힘)	상대적으로 느림
구현 복잡도	상대적으로 복잡	상대적으로 단순
사용 사례	탐색 빈번	삽입/삭제 빈번 (STL 사용)

AVL 트리가 STL 컨테이너가 되지 못한 이유

삽입/삭제 시 불균형을 자주 감지하기 때문에 회전을 더 많이 수행한다. 덕분에 탐색은 빠르지만 STL 용도에서는 탐색보단 삽입/삭제가 더 빈번하기 때문에 회전 규칙이 더 다양하고 복잡한 AVL 트리는 이런 범용 라이브러리에 어울리지 않는다.