728x90 알고리즘42 이진검색트리-3 delete - case 1 : 자식 노드가 없는 경우 -case 2 : 자식노드가 1개인 경우 - case 3 : 자식노드가 2개인 경우 - 지우려는 값의 successor을 찾는다 - 지우려는 값에 successor을 복사하고 successor의 값은 지운다. delete의 수도코드 - 처음 if는 자식이 1개 이하인 경우이다. if문안에 들어가면 y에 지우려는 값을 넣는다 - if문안에 못들어가면 y에는 지우려는 값의 successor값을 넣는다. - 다음 if문에는 y의 왼쪽 값이 있다면 x에 왼쪽 값, 오른쪽 값이 있다면 x에 오른쪽 값을 넣는다. - 만약 x의 값이 없다면 y의 부모를 x의 부모로 만들어준다. - 만약 y의 부모가 null 즉 y가 루트면 x를 트리의 루트로 만들어준다. - 만.. 2021. 3. 8. 이진검색트리-2 최솟값 - 이진 검색트리의 최솟값은 루트에서 계속 왼쪽으로 갔을 때 마지막 노드이다 - 시간복잡도 : o(h) 최댓값 - 이진 검색트리의 최댓값은 루트에서 가장 오른쪽 노드이다. - 시간복잡도 : o(h) successor - 노드 x의 successor란 key[x]보다 크면서 가장 작은 키를 가진 노드 - 모든 키들이 서로 다르다고 가정 successor를 찾는 3가지 경우 1. 노드 x의 오른쪽 부트리가 존재할 경우, 오른쪽 부트리의 최솟값 2. 오른쪽 부트리가 없을 경우, 부모를 따라 루트까지 올라가면서 처음으로 누군가의 왼쪽 자식이 되는 노드 3. 그런 노드 y가 존재하지 않을 경우 successor가 존재하지 않음 (즉, x가 최댓값) - 오른쪽 서브트리가 존재하면 그 서브트리에서 최솟값을 찾.. 2021. 3. 7. 이진검색트리-1 dynamic set, search structure - 여러 개의 키를 저장 - 다음과 같은 연산들을 지원하는 자료구조 insert - 새로운 키의 삽입 search - 키 탐색 delete - 키의 삭제 - 예 : 심볼 테이블 search insert delete 배열 정렬 o(logn) o(n) o(n) 정렬 x o(n) 1 1 연결 리스트 정렬 o(n) o(n) o(1) 정렬 x o(n) o(1) o(1) - 정렬된 혹은 정렬되지 않은 배열 혹은 연결 리스트를 사용할 경우 insert, search, delete 중 적어도 하나는 o(n) - 이진탐색트리, 레드-블랙 트리, avl-트리등의 트리에 기반한 구조들 - direct address table, 해쉬 테이블 등 검색트리 - dymamic .. 2021. 3. 7. 트리와 이진트리 트리 - 계층적인 구조를 표현 - 조직도 - 디렉토리와 서브디렉토리 구조 - 가계도 트리 용어 트리 : 노드들과 노드들을 연결하는 링크로 구성 링크 : 노드와 노드들을 연결 루트 : 맨위의 노드 노드 : 부모 노드와 자식 노드가 존재, 부모 노드와 링크되며 밑에 있는 노드를 자식노드라고 함 서브트리 : 한 노드와 그 노드의 자손들로 이루어진 트리 레벨 : 트리의 층 별로 트리의 1층,2층... 으로 만든다. 트리의 기본적인 성질 - 노드가 n개인 트리는 n-1개의 링크를 갖는다. - 루트에서 어떤 경로로 가는 경로는 유일하다. 또한 임의의 두 노드간의 경로도 유일하다. 이진 트리 - 이진 트리에서 각 노드는 최대 2개의 자식을 갖는다. - 각각의 자기 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지가.. 2021. 3. 7. sorting in linear time 선형시간 정렬 알고리즘 - O(n) -> comparison sort가 아님 counting sort - n개의 정수를 정렬하라. 단 모든 정수는 0에서 k사이의 정수이다. ->데이터의 사전지식이 있음 - ex) n명의 학생들의 시험점수를 정렬하라. 단 모든 점수는 100이하의 양의 정수이다. ex) k = 5인 경우 ->0~5까지의 숫자가 나온다! , n은 8! - c라는 배열에는 A배열의 원소를 count하기 위해 만듬 위의 배열 그림을 이렇게 수도코드로 만들수 있다. 하지만 여기에는 문제가 있다. 단순한 배열을 정렬하는 상황이라면 문제가 되지 않겠지만 대부분의 경우 정렬한 값들은 레코드의 key값이기 때문에 위의 수도코드 방식으로 정렬하면 레코드의 값들을 정렬할 수 없다. 따라서 다른 방법을 찾아야.. 2021. 3. 2. 정렬의 lower bound comparison sort - 데이터들간의 상대적 크기관계만을 이용해서 정렬하는 알고리즘 - 따라서 데이터들간의 크기 관계가 정의되어 있으면 어떤 데이터에든 적용가능(문자열, 알파벳, 사용자 정의 객체 등) - 버블소트, 삽입정렬, 합병정렬, 퀵소트, 힙정렬 등 non-comparison sort - 정렬한 데이터에 대한 사전지식을 이용 - 적용에 제한 - bucket sort - radix sort ** 오늘 정리할 내용 qucik sort, heap sort, merge sort에서 평균 시간복잡도는 O(nlogn)이다. 여기서 O(nlogn)보다 더 작은 시간복잡도는 불가능한가?에 대한 내용이다. 결론부터 말한다면 comparison sort에서는 불가능하다. 하한(lower bound) : 특정.. 2021. 3. 1. 이전 1 ··· 3 4 5 6 7 다음 728x90
