본문 바로가기

알고리즘14

13-1강. 해슁(Hashing) 1 SUHA(Simple Uniform Hashing Assumption) - 각각의 키가 모든 슬롯들에 균등한 확률로() 독립적으로(independently) 해슁된다는 가정 => 사실 현실적이지 않다. - 성능분석을 위해서 주로 하는 가정일 뿐 - hash 함수는 deterministic하므로 현실에서는 불가능하다 - Load factor alpha = n/m: - n : 테이블에 저장될 키의 갯수 - m : 해쉬테이블의 크기, 즉 연결리스트의 깃수 - 각 슬롯에 저장된 키의 평균 갯수 - 연결리스트 T[j]의 길이를 Nj라고 하면, E[Nj] = alpha - 만약 n = O(m)이면 평균검색시간은 O(1) 2020. 11. 24.

11-3강. 이진검색트리 (Binary Search Tree) 지난 강의 공부 내용... 이진검색트리의 탐색, 삽입 이진검색트리/이진탐색트리의 삭제 Case 1 : 자식노드가 없는 경우 -> 해당 노드를 그냥 삭제한다. Case 2 : 자식노드가 1개인 경우 -> 자신의 자식노드를 원래 자신의 위치로 보낸다. Case 3 : 자식노드가 2개인 경우 -> 해당 노드의 자리는 그대로 두고, 데이터만 삭제한다. 그리고 해당 노드와 가자아 가까운 값인 다른 노드를 해당 자리로 가져 온다. 그 다른 노드는 삭제하려는 노드의 successor이다. 삭제하려는 노드의 successor는 최대 1개의 자식노드를 가진다. TREE-DELETE(T, z)// z : 삭제할 노드 { if left[z] == null or right[z] == null then y 2020. 11. 15.

제11-1강. 이진검색트리(Binary Search Tree) 이진검색트리(Binary Search Tree) - 여러 개의 키(key)를 저장 - 다음과 같은 연산들을 지원하는 자료구조 INSERT - 새로운 키의 삽입 SEARTCH - 키 탐색 DELETE - 키의 삭제 ex) 심볼테이블 search insert delete 배열 정렬된 경우 O(logn) O(n) O(n) 정렬되지 않은 경우 O(n) O(1) O(1) 연결리스트 정렬된 경우 O(n) O(n) O(1) 정렬되지 않은 경우 O(n) O(1) O(1) 다양한 방법들 - 정렬된, 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n) - 이진탐색트리(Binary Search Tree), 레드-블랙트리(red-black tree), A.. 2020. 11. 10.

제 10강 트리와 이진트리 트리 (Tree) 계층적인 구조를 표현하는 데 사용한다. 예를 들면 조직도나 디렉토리와 서브디렉토리의 구조를 표현할 때, 가계도를 표현할 때 쓴다. 트리는 노드(node) 들과 노드들을 연결하는 링크(link)들로 구성된다. 루트(root) : 맨 위의 노드 링크(link) : 노드들을 연결하는 선 (=edge, branch) 트리의 부모-자식 관계 트리 구조 상에서 상대적으로 위에 있는 노드를 부모 노드라 하고, 아래에 있는 노드를 자식 노드라 한다. 트리의 형제 관계 부모가 동일한 노드들을 형제(sibling) 관계라고 한다. 루트 노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가진다. 리프노드 자식이 없는 노드들을 리프(leaf) 노드라 한다. 리프노드가 아닌 노드들을 내부(internal.. 2020. 11. 8.

이전 1 2 3 4 다음

티스토리툴바