알고리즘
-
Binary Search Tree (이진 탐색 트리)알고리즘 2020. 12. 11. 21:06
Binary Search Tree 이진탐색과 연결리스트를 결합한 자료구조이다. 각 노드의 왼쪽 서브트리에는 해당 노드보다 작은 값만 있어야한다. 각 노드의 오른쪽 서브트리에는 해당 노드보다 큰 값만 있어야한다. operation : SEARCH, MINIMUM, MAXIMUM, PREDECESSOR, SUCCESSOR, INSERT, DELETE average case : O(log n) (평균 높이 : log n) worst case : O(n) Search 루트에서 시작. k를 찾을 때 key[x]>k 이면 x의 왼쪽 subtree에서 search key[x] 그냥 삭제 Case2: 삭제할 노드에 자식노드가 1개 있을 때 -> 해당 노드를 지우고 해당 노드의 자식과 부모를 연결 Case3: 자식노드가..
-
hash알고리즘 2020. 12. 10. 17:59
hashing dictionary (key, value)를 implementing insert, search, delete 연산의 average-case : O(1) find minimum과 같은 sort연산은 비효율적이다. dictionary dynamic-set data structure. 동적으로 크기가 변한다. operation : insert, search, delete hash table key : hash function의 input. U : universe of keys. 모든 가능한 키의 집합 K : actual keys. 딕셔너리에 매칭된 실제 키 Hash Table을 만들 때 U를 저장할 필요 없다. |k|=n의 사이즈를 테이블로 만든다. 하지만 좁은 장소에 여러개를 저장해야하므로 h..