알고리즘 수업. 탐색 (1) (스테픈 2km완료)

알고리즘 드디어 탐색 수업이네요

정렬도 후다닥 끝나서..

탐색중에 이진탐색은 하도 써봐서

그나마 익숙하네요

이진 탐색트리의 평균 수행시간은 O(log n)

최악의 경우 .O(n)

삽입 연산 -> 노드의 이동이 거의 없음

삭제연산 -> 상수 번 이동 (0, 1 ,1 또는 2)

원소 의 삽입/ 삭제에 따라 경사 트리 형태가 될수있음

결국 최악의 수행시간 O(n)을 갖게됨

경사트리가 만들어지지 않도록 하는게 중요한듯

균형 탐색트리 -> 2-3-4 트리, 레드-블랙 트리 B-트리

2-노드 -? 1개의 키와 2개의 자식을 갖는 노드
3-노드 -> 2개의 키와 3개의 자식
4-노드 -> 3개의 키와 4개의 자식

각 노드의 한 키의 왼쪽 서브트리에 있는 모든 키값은 그 키값보다 작음

각 노드의 한키의 오른쪽 서브트리에 있는 모든 키값은 그 키값보다 큼

모든 리프 노드의 레벨은 동일함.

성질 기억하기

#오운완(20250403/4km/2km)