탐색2 Chapter12 탐색(Search) 2 2018/02/27 - [프로그래밍/자료구조] - Chapter11 탐색(Search) 1 12-1 균형 잡힌 이진 탐색 트리: AVL 트리의 이해이진 탐색 트리의 단점을 개선한 또 다른 이진 탐색 트리를 소개한다. 이진 탐색 트리의 문제점과 AVL트리 이진 탐색 트리의 탐색 연산은 O(log2n)의 시간 복잡도를 가진다. 이진 탐색 트리는 균형이 맞지 않을 수록 O(n)에 가까운 시간 복잡도를 보인다.이진 탐색 트리는 저장 순서에 따라 탐색의 성능에 큰 차이를 보인다. 이러한 탬삭 트리의 단점을 해결한 트리를 가리켜 '균형 잡힌 이진 트리'라 하며, 그 종류는 대략 다음과 같다.- AVL 트리- 2-3 트리- 2-3-4 트리- Red-Black 트리- B 트리 자동으로 균형을 잡는 AVL 트리와 균형 .. 2018. 2. 28. Chapter11 탐색(Search) 1 2018/02/23 - [프로그래밍/자료구조] - Chapter10 정렬(Sorting) 11-1 탐색의 이해와 보간 탐색단순히 탐색의 방법만을 열거하지 않는다. 탐색의 이해 "효율적인 탐색을 위해서는 '어떻게 찾을까'만을 고민해서는 안 된다. 그보다는 '효율적인 탐색을 위한 저장방법이 무엇일까'을 우선 고민해야 한다.' 보간 탐색(interpolation Search)- 정렬되지 않은 대상을 기반으로 하는 탐색 순차 탐색- 정렬된 대상을 기반으로 하는 탐색 이진 탐색 "이진 탐색처럼 그냥 중앙에서 탐색을 시작하지 말고, 탐색대상이 앞쪽에 위치해 있으면 앞쪽에서 탐색을 시작하자!" 탐색 키(Search Key)와 탐색 데이터(Search Data)보간 탐색의 구현이진 탐색의 경우 다음 문장을 통해서 탐색.. 2018. 2. 27. 이전 1 다음
