[자료구조] 트리(Tree) - 트라이 트리(Trie tree)

아래의 영상들을 바탕으로 작성되었습니다. 좋은영상 감사합니다.

 

Trie(트라이) Tree에 대해서 - https://youtu.be/TohdsR58i3Q

Trie - Insert and Search | GeeksforGeeks - https://youtu.be/dUBkaqrcYT8

0. 트라이 트리(Trie tree)란?

(2023.03.16 수정)

문자열 검색을 빠르게 해주는 이진 검색 트리 구조.

한 레벨당 한 문자씩 저장되므로

M이 문자열의 최대 길이라면 문자열 검색시 시간복잡도는 O(Mlogn) 다.

트라이를 이용하면 시간복잡도 O(M)이 걸리는 문자열 검색구조를 만들 수 있다.

 

참고 -> https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%9D%BC%EC%9D%B4_(%EC%BB%B4%ED%93%A8%ED%8C%85)

 

 

1. 삽입(Inserting)

1. root는 비워둔다

2. 삽입하려는 첫글자가 root의 child로 저장되어있으면 해당 child를 따라 내려간다.(없으면 첫글자를 sibling으로 삽입한다.)

3. 동일한 문자가 있을경우 그냥 다음글자로 내려가고, 동일한 문자가 없을경우 새로운 문자를 child의 sibling로 삽입한다.

4. 맨 마지막 글자를 체크 또는 삽입할때까지 반복한다.

 

2. 트라이에서의 문자열 탐색(Searching in a trie)

1. root의 child부터 시작한다.

2. child에 첫번째 문자가 저장되어 있는지 체크한다.

3. 저장되어 있다면 해당 child로 내려간다.

4. 다음 문자가 child에 저장되어 있을때까지 반복한다.

5. 검색하려는 문자열의 길이가 leaf의 레벨과 딱 떨어지면 검색성공, 아니면 검색 실패.

 

3. 트라이의 삽입, 탐색 구현(c++)

there, their, answer, any, bye를 트라이에 삽입시 아래처럼 되도록 구현해보기.

(연습용으로 구현한 코드입니다. 잘못된 부분이 있으면 언제든 알려주세요. 감사합니다 (--)(__))

 

(1) .h

	#pragma once
	#include <iostream>
	#include <vector>
	using namespace std;
	class Node
	{
	public:
	char data;
	vector<Node*> siblings;
	};
	class Trie
	{
	private:
	Node* root = new Node;
	public:
	void push(string str) {
	insert(str, 0, root);
	}
	void insert(string str, int idx, Node* node)
	{
	if (idx >= str.length()) return;
	int next = -1;
	for (int i = 0; i < node->siblings.size(); i++) {
	if (str[idx] == node->siblings[i]->data) {//동일한 문자가 있는 경우
	next = i;
	break;
	}
	}
	if (next != -1)
	insert(str, idx + 1, node->siblings[next]);
	else//동일한 문자가 없는경우, 자식으로 추가
	{
	Node* newNode = new Node;
	newNode->data = str[idx];
	node->siblings.push_back(newNode);
	insert(str, idx + 1, newNode);
	}
	}
	bool search(string str)
	{
	return findWord(str, 0, root);
	}
	bool findWord(string str, int idx, Node* node)
	{
	if (!node->siblings.empty() && idx >= str.length()) return false;
	if (idx >= str.length()) return true;
	int next = -1;
	for (int i = 0; i < node->siblings.size(); i++) {
	if (str[idx] == node->siblings[i]->data) {
	next = i;
	break;
	}
	}
	if (next != -1)//동일한 문자가 있음
	return findWord(str, idx + 1, node->siblings[next]);
	else//검색 실패
	return false;
	}
	void print() {
	order(root, 1);
	}
	void order(Node* node, int depth)
	{
	for (int i = 0; i < node->siblings.size(); i++)
	{
	cout << "(" << depth << ") " << node->siblings[i]->data << " ";
	if (!node->siblings[i]->siblings.empty()) {
	order(node->siblings[i], depth + 1);
	}
	else cout << endl;
	}
	}
	};

view raw 트라이_헤더.h hosted with ❤ by GitHub

(2) .cpp

	#include "header.h"
	int main(){
	Trie* trie = new Trie;
	trie->push("there");
	trie->push("their");
	trie->push("answer");
	trie->push("any");
	trie->push("bye");
	trie->print();
	vector<string> v{"ans","banana","answer","bye","byeyo","a"};
	for (int i = 0; i < v.size(); i++)
	{
	if (trie->search(v[i])) cout << "검색 O : " << v[i] << endl;
	else cout << "검색 X : " << v[i] << endl;
	}
	return 0;
	}

view raw 트라이_메인.cpp hosted with ❤ by GitHub

실행결과