[알고리즘] 탐색(3) - AVL 트리
AVL트리 역시 레드-블랙 트리와 마찬가지로 자가 균형 이진 탐색 트리입니다. 레드-블랙 트리와 다른 점은 균형(balance)을 유지하기 위해 적용하는 조건이 다른데요. 그래서 같은 자가 균형 이진 탐색 트리이지만 같은 키를 삽입해도 트리의 결과는 다르게 나올 수 있습니다. ex) KEY = [2, 1, 8, 9, 7, 3, 6, 4, 5] 삽입 시 AVL트리 조건은 다음과 같습니다. 1. *높이 차가 2 이상이 되면 회전을 통해 높이차를 1 이하로 유지 * 높이 차 = 오른쪽 서브 트리의 높이 - 왼쪽 서브 트리의 높이 조건은 엄청 간단하죠?? 여기서 높이 차에 대해 예시를 통해 설명드리자면 각각의 노드 옆에 높이차를 적게 되는데, 이 높이 차는 해당 노드의 우측 서브 트리 높이- 왼쪽 서브 트리 높..
[알고리즘] 탐색(1) - 이진 탐색, 이진 탐색 트리 with Python
탐색 알고리즘? - 컴퓨터에 저장된 자료를 신속하고 정확하게 찾아주는 알고리즘 이진 탐색(binary search) 정렬되어 있는 배열에서 특정한 값을 찾아내는 알고리즘으로 탐색 시간 복잡도는 O(logN) 탐색 방법: 분할-정복 방법 사용 ex) 정렬된 배열 [12,15,23,48,62,98,111,130] 에서 23을 찾는다면?? 1. 가운데 값 선택 -> 48 2. 우리가 찾고자하는 23은 48 좌측에 위치함으로 탐색범위가 12~23으로 줄어듬, 줄어든 탐색범위에서 중간 값 선택 -> 15 3. 23은 15 우측에 위치, 값은 하나만 남게 되고 이 값은 23과 일치 소스코드(파이썬) def binary_search(a:list, search_key): left, right = 0, len(a) wh..