> 자료구조 구현16 트리(tree)의 기본 * 트리(Tree): 노드와 간선으로 구성되어 있는 자료 구조 (그래프의 일종으로 Cycle이 일어나지 않는 특징을 가진다) * 이진 트리(Binary Tree): 모든 노드가 최대 2개의 간선을 가지는 트리 * 이진 탐색 트리(Binary Search Tree): 이진 트리 + 규칙 하나 자신보다 왼쪽에 위치한 노드는 자신보다 작은 값을 가지며, 오른쪽 노드는 큰 값을 가진다 * 시간 복잡도: O(log n) (최악의 경우, O(n) - 링크드 리스트와 동일한 성능) - 한번 실행할 때마다, 50%의 실행시간을 단축한다는 것을 의미 - 이미지 출처: www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-inser.. 2020. 10. 6. 해시 충돌(hash collision) 해결(2) - 해시테이블 저장 공간 사용 2. Linear Probing 기법 - 폐쇄 해싱(Close Hashing): 충돌시, 해시테이블 저장 공간을 이용해 데이터를 연쇄적으로 연결시켜 저장하는 기법 hash_table = list([ 0 for i in range(6)]) def get_key(data): return ord(data[0]) + ord(data[1]) # address는 같아도 key값은 다르게 함 def hash_func(key): return key % 6 def save(data, value): index_key = get_key(data) address = hash_func(index_key) if hash_table[address] != 0: # 0이 아니면 주소에 data가 들어가 있다! for x in rang.. 2020. 10. 6. 해시 충돌(hash collision) 해결(1) - 링크드 리스트 사용 1. Chaining 기법 - 개방 해싱(Open Hasing): 충돌시, 링크드 리스트를 이용해 데이터를 연쇄적으로 연결시켜 저장하는 기법 hash_table = list([ 0 for i in range(6)]) def get_key(data): return ord(data[0]) + ord(data[1]) # address는 같아도 key값은 다르게 함 def hash_func(key): return key % 6 def save(data, value): index_key = get_key(data) address = hash_func(index_key) if hash_table[address] != 0: # 0이 아니면 주소에 data가 들어가 있다! for x in range(len(hash_t.. 2020. 10. 5. 해시 테이블(hash table)의 기본 * 해시(Hash): 임의의 데이터를 고정 길이의 데이터로 매핑하는 것 (Key는 고정 길이일 수도, 아닐 수도) * 해시 테이블(Hash table): Key에 Value를 저장하는 자료 구조 - Key 값을 통해 직접 Value 값에 접근이 가능하다 - 보통 배열로 해시 테이블 공간만큼 생성하여 사용한다 - 대표적인 예: Python의 Dictionary 타입 (python에서는 이 타입을 이용하면 되기 때문에 해시 테이블을 굳이 구현할 필요가 없다) * 해시 값(Hash value): Key값을 받은 해싱 함수가 특정 연산을 시행하여 반환해주는 값 (고정된 길이) 이를 통해, 해시 테이블에서 Key에 맞는 Value 값을 일관되게 찾을 수 있다 (Key값을 구하는 함수를 따로 만들 수 있다) has.. 2020. 10. 5. 이전 1 2 3 4 다음