트라이란

• 문자열 집합을 관리하는 트리입니다.
• 문자열 저장, 검색에 용이함.
• 간선 마다 알파벳 하나가 대응 되면서 자식 노드와 연결된 간선 중 어떤 알파벳과 대응되는 간선은 최대 하나입니다.
• 밑의 그림으로 보면 알 수 있습니다.
  

  • 시간 복잡도 삽입/삭제/탐색 O(문자열의 길이)
  • 해시와 같은 시간 복잡도로 매우 빠르다.

코드

인덱스를 이용한 코드입니다.

#include<iostream>
#include <vector>
using namespace std;

class Trie {
	static constexpr size_t M = 26;
	static constexpr char OFFSET = 'a';

	struct TrieNode {
		int child[M];
		bool is_terminal;

		TrieNode() {
			memset(child, -1, sizeof(int) * M);
			is_terminal = false;
		}
	};

	vector<TrieNode> nodes;

public:
	//Trie():nodes(1){} ??

	void init() {
		nodes.resize(1);
		nodes[0] = TrieNode();
	}

	void insert(const string& str) { 
		int node_id = 0;
		for (auto& c : str) {
			if (nodes[node_id].child[c - OFFSET] == -1) { // 없으면
				nodes[node_id].child[c - OFFSET] = nodes.size();
				nodes.emplace_back();
			}
			node_id = nodes[node_id].child[c - OFFSET]; // 이동
		}
		nodes[node_id].is_terminal = true;
	}
	void remove(const string& str) {
		int node_id = 0;
		for (auto& c : str) {
			if (nodes[node_id].child[c - OFFSET] == -1) { // 없으면
				return; // 함수 종료
			}
			node_id = nodes[node_id].child[c - OFFSET]; // 자식으로 이동
		}
		nodes[node_id].is_terminal = false; // 노드 제거
	}

	bool find(const string& str) {
		int node_id = 0;
		for (auto& c : str) {
			if (nodes[node_id].child[c - OFFSET] == -1) { // -1이면 없으므로
				return false; // false 리턴
			}
			node_id = nodes[node_id].child[c - OFFSET]; // 자식으로 이동
		}
		// 문자열 이동을 끝낸 후
		return nodes[node_id].is_terminal; // 현재 노드의 t/f리턴
	}
};



int main()
{
	Trie trie;
	trie.init();
	trie.insert("abc");
	trie.insert("abb");
	trie.remove("abb");
	cout << trie.find("abb");
	return 0;
}