트라이
-
[Data Structure] TrieCS/Data Structure 2021. 12. 29. 18:28
Binary Trie 특징 이진 탐색 트리 형태의 불균형 트리 자료구조이다. 완전 매칭과 부분 매칭에 효율적인 자료구조이다. 해시의 대체로 사용된다. 두 타입의 노드를 가진다. - Branch(link, interior, non-leaf) Node: 데이터 없이 자식 노드의 포인터만 저장 - Element(data, leaf) Node: 데이터 저장 시간복잡도: O(k), k=키의 최대 비트 수 Search(탐색) 탐색할 데이터를 K라고 할 때 i번째 레벨에서 K의 i번째 비트 = 0 → 왼쪽 서브 트리 이동 K의 i번째 비트 = 1 → 오른쪽 서브트리 이동 리프 노드에 저장된 데이터과 탐색할 데이터를 비교한다. Insertion(삽입) Insert 00001 Insert 10011 Insert 0010..