O(nlog(n))
left
(가장 첫 index), mid
(중간 index), right
(가장 마지막 index) 변수가 있다고 하자.mid
인덱스의 배열 값과 찾는 값을 비교한다.mid
인덱스의 배열 값이 찾는 값보다 크면, left
를 mid+1
로 옮긴다. mid
값을 다시 계산하여 1을 반복한다.mid
인덱스의 배열 값이 찾는 값보다 작으면, right
를 mid-1
로 옮긴다.mid
값을 다시 계산하여 1을 반복한다.mid
인덱스의 배열 값이 찾는 값과 같으면 탐색이 끝난다.AVL 트리
트리가 편향될 경우 좌회전, 우회전하여 균형을 유지하는 이진 탐색 트리
삽입
삭제
단말 정점(리프 노드)을 삭제하는 경우
4
와의 간선을 끊으면 3
은 참조가 되지 않아 사라진다.하나의 서브 트리를 가지는 경우
4
를 삭제하는 과정을 생각하면, 5
의 왼쪽 간선이 3
을 가리키도록 하면 된다. 4
는 참조가 되지 않으므로 삭제된다.두 개의 서브트리를 가지는 경우
7
을 삭제하는 과정을 생각하면, 7
을 8
(오른쪽 서브트리의 가장 작은값)로 교체하거나 7
을 6
(왼쪽 서브트리의 가장 작은 값)으로 교체하는 경우 둘 다 이진 탐색트리의 규칙을 만족하게 된다.프로그머스 데브코스 프론트엔드 Day4 [강의] 이진탐색