lsh424

AVL트리 역시 레드-블랙 트리와 마찬가지로 자가 균형 이진 탐색 트리입니다. 레드-블랙 트리와 다른 점은 균형(balance)을 유지하기 위해 적용하는 조건이 다른데요. 그래서 같은 자가 균형 이진 탐색 트리이지만 같은 키를 삽입해도 트리의 결과는 다르게 나올 수 있습니다. ex) KEY = [2, 1, 8, 9, 7, 3, 6, 4, 5] 삽입 시 AVL트리 조건은 다음과 같습니다. 1. *높이 차가 2 이상이 되면 회전을 통해 높이차를 1 이하로 유지 * 높이 차 = 오른쪽 서브 트리의 높이 - 왼쪽 서브 트리의 높이 조건은 엄청 간단하죠?? 여기서 높이 차에 대해 예시를 통해 설명드리자면 각각의 노드 옆에 높이차를 적게 되는데, 이 높이 차는 해당 노드의 우측 서브 트리 높이- 왼쪽 서브 트리 높..