반응형 CS/자료구조11 [자료구조] AVL트리 AVL트리란 이진탐색 트리의 단점을 보완하고자 나온 트리이다. 이진탐색 트리의 큰 문제점은 한쪽 방향으로 노드가 쏠릴 수 있다는것이다. 저장하는 순서에 따라 발생되는문제인데 예를 들어 1, 2, 3, 4, 5, 6을 순서대로 저장한다고 하면 오른쪽 으로만 노드가 쏠려버리게되어 성능이 매우 나빠진다. AVL트리는 이런 이진트리의 단점을 보완이자 극복해준다. 특징 - 이진탐색 트리의 속성을 가진다. - 왼쪽, 오른쪽 서브 트리의 높이 차이가 최대 1이다. - 높이 차이가 1보다 커지면 회전을 통해 균형을 맞춰 높이 차이를 줄인다. - 삽입, 삭제, 검색의 시간복자잡도가 O(logn)이다. 상태 - LL상태 왼쪽 서브트리로 노드가 치우쳐있을때 사용하는 방식으로 오른쪽으로 회전하여 균형을 맞춘다. 순서 y노드의.. 2024. 1. 19. [자료구조] 이진탐색 트리(Binary Search Tree) 이진 탐색 트리란 - 이진탐색과 연결리스트를 결합한 자료구조의 일종이다. - 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안되었다. 특징 - 각 노드에 중복되지 않은 키(key)가 있다. - 루트노드의 왼쪽 서브트리는 해당 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다. - 루트노드의 오른쪽 서브 트리는 해당 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다. - 좌우 서브 트리도 모두 이진 탐색 트리여야 한다. 탐색 과정 1. 루트 노드의 키와 찾고자하는 값을 비교한다. 찾고자 하는 값이라면 탐색을 종료한다. 2. 찾고자 하는 값이 루트 노드의 키보다 작다면 왼쪽 서브 트리로 탐색을 진행한다. 3. 찾고자 하는 값이 루트 노드의 키보다 크다면 오른쪽 서브 트리로 .. 2024. 1. 17. [자료구조] 보간 탐색(Interpolation Search 보간 탐색은 이진탐색과 유사하다. 이진 탐색은 정렬된 배열의 중앙에 위치한 데이터를 기준으로 탐색을 시작한다. 보간탐색은 이런한 방식에서 발생할 수 있는 비효율을 줄이기 위해 등장하였다. 탐색 기준 선정방식 중복된 키가 없이 정렬된 데이터 들에 대한 탐색이라는점을 고려하여 탐색할 대상이 대략적으로 어디에 위치해 있는지를 파악하는 식이 존재한다. 이는 데이터의 값과 그 데이터가 저장된 위치의 인덱스값이 비례하다는 생각을 근거를 기반에 두고있다. "x" 라는 데이터를 찾는 경우, 해당 데이터의 인덱스 값 "s"에 대한 식은 다음과 같다. low : 탐색 대상의 시작 인덱스 high : 탐색 대상의 마지막 인덱스 #include int ISearch(int ar[], int first, int last, in.. 2024. 1. 16. [자료구조] 이진 탐색(Binary Search) 이진 탐색이란? - 테이터가 정렬되어있는 배열에서 특정 값을 찾을때 중간에 있는 임의의 값을 선택하여 특정값X와 비교한다. X가 중간값보다 작으면 중간값을 기준으로 좌측의 데이터들을 대상으로, 중간값보다 크면 우측의 데이터들을 대상으로 동일한 방법으로 다시 중간값을 임의로 선택해서 비교하는 과정을 X값을 찾을때까지 반복한다. - 이진탐색에 사용되는 배열은 정렬이 되어있어야 한다. - 구역을 나누었을때 first(첫번째 인덱스)가 last(마지막 인덱스)보다 커지면 해당 배열에 특정값이 없다고 판단하여 탈출하는 부분을 구현해야한다. - 시간 복잡도 : O(logn) int BSearchRecursive(int arr[], int target, int low, int high) { if (low > high.. 2024. 1. 16. 이전 1 2 3 다음 반응형
