행복한 연어의 이야기

검색 알고리즘은 검색 로직뿐만 아니라 삽입 삭제 로직도 같이 구현했습니다. 1. AVL 트리 앞서 설명해드린 이진 트리 탐색 (Binary Tree Search)에는 단점이 있습니다. 이진 트리 탐색은 O(log²n) 의 시간 복잡도를 가지지만 균형이 잡히지 않은 트리일수록 O(n)에 가까워 진다는 것 입니다. 트리의 균형을 잡기위한 여러가지 특성의 트리(균형잡힌 트리)가 있으며 그중에 오늘 소개 드릴 트리는 AVL 입니다. (AVL 은 이 트리를 개발한 사람의 이름 약자입니다.) 2. 구현 방법 검색, 삽입, 삭제는 앞서 구현한 이진 트리 탐색 (Binary Tree Search)과 동일합니다! 다만 삽입과 삭제시 트리의 균형을 검사하여 리밸런싱을 해주는 작업이 추가되었을 뿐입니다. 우선 트리가 균형을..