[자료구조] TRIE IDEA

• 본 게시글은 대학생이 수업을 듣고 내용을 정리한 것입니다.
• 따라서 완벽하지 않은 부분이 있을 수 있습니다.
• 아울러 본 게시글에 포함된 코드들은 대략적인 개념 이해만을 위해 작성된 것으로 완전하지 않은 코드임을 알려드립니다.

---

Huffman Coding

• 등장 빈도에 따라 압축한다.
• 등장빈도가 큰 것은 짧게, 등장빈도가 작은 것은 길게 표현한다.
• 노드들을 리프 위치에 등장빈도 순으로 일렬로 정렬하고, 등장빈도가 작은 것부터 둘 씩 묶는다.
• 묶인 것은 합을 표현한다.
• 그렇게 트리가 완성되면 왼쪽은 0, 오른쪽은 1로 엣지에 표기한다.
• root부터 각 노드에 도달할 때까지의 엣지 코드가 최종 허프만 코드가 된다.
• 이는 랜덤한 경우에 더 유용하다. 연속된 문자가 많을 경우 각각을 8a와 같은 식으로 압축하는 것이 더 효율적일 것이다.

---

TRIE idea

• 리프에만 값이 존재하도록 하는 허프만 코드의 아이디어 차용
• 빈도수 대신 각 숫자는 비트형태로 전환하여 사용
• 최악의 경우에도 logN 시간 안에 작업이 가능하다. (N은 숫자의 자리수)
• ( a >> ( i - 1 ) ) % 2 == 0를 4부터 1까지 진행하여 그를 기반으로 탐색, 삽입, 삭제한다.

---

TRIE 구현

class Node {
​​​​Node *p, *l, *r;
}

Node BTR;

void init(Node *R) {
​​​​R->p = R->l = R->r = NULL;
}

int *Search (Node * R, unsigned a) {
​​​​Node *C = R;
​​​​for (int i = 4; i >= 1; i--) {
​​​​​​​​if (( a >> ( i - 1 ) ) % 2 == 0) {
​​​​​​​​​​​​if (C->l == NULL) break;
​​​​​​​​​​​​else C = C->l;
​​​​​​​​}
​​​​​​​​if (( a >> ( i - 1 ) ) % 2 == 1) {
​​​​​​​​​​​​if (C->r == NULL) break;
​​​​​​​​​​​​else C = C->r;
​​​​​​​​}
​​​​}
​​​​if (i == 0) return C;
​​​​else return NULL;
}

int *Insert (Node * R, unsigned a) {
​​​​Node *C = R, N;
​​​​int cre = 0;
​​​​for (int i = 4; i >= 1; i--) {
​​​​​​​​if (( a >> ( i - 1 ) ) % 2 == 0) {
​​​​​​​​​​​​if (C->l == NULL) {
​​​​​​​​​​​​​​​​N = new Node;        
​​​​​​​​​​​​​​​​N->p = C; 
​​​​​​​​​​​​​​​​N->l = N->r = NULL;        
​​​​​​​​​​​​​​​​C->l = N;
​​​​​​​​​​​​​​​​C = C->l;
​​​​​​​​​​​​​​​​cre = 1;
​​​​​​​​​​​​}
​​​​​​​​​​​​else C = C->l;
​​​​​​​​}
​​​​​​​​if (( a >> ( i - 1 ) ) % 2 == 1) {
​​​​​​​​​​​​if (C->r == NULL) {
​​​​​​​​​​​​​​​​N = new Node;        
​​​​​​​​​​​​​​​​N->p = C; 
​​​​​​​​​​​​​​​​N->l = N->r = NULL;        
​​​​​​​​​​​​​​​​C->r = N;
​​​​​​​​​​​​​​​​C = C->r;
​​​​​​​​​​​​​​​​cre = 1;
​​​​​​​​​​​​}
​​​​​​​​​​​​else C = C->r;
​​​​​​​​}
​​​​}
​​​​if (cre) return C;
​​​​else return NULL;
}

int Delete(Node * R, unsigned a) {
​​​​Node *C, *T;
​​​​C = Search(R, a);
​​​​if (C == NULL) return 0;
​​​​while (C->p ! = NULL) {
​​​​​​​​if (C->l == NULL && C->r == NULL) {
​​​​​​​​​​​​T = C;
​​​​​​​​​​​​C = C->p;
​​​​​​​​​​​​delete T;
​​​​​​​​}
​​​​​​​​else break;
​​​​}
​​​​return 1;
}