[자료구조] 트라이

트라이

문자열을 효율적으로 탐색하는 자료구조로 O(n) 시간복잡도로 해당 문자열이 존재하는지 확인 할 수 있는 자료구조 이다.

• 삽입, 검색, 삭제, 업데이트 : O(n) 시간이 걸린다.
• Node 트리구조 기반의 자료구조를 활용한다.
• 만약 “abc123” 과 “abc12” 라는 문자열이 존재한다면 “abc12”는 같은 노드를 공유한다.
• 삽입 :
  • 루트노드에서 자식 노드로 방문해가면서 자식노드가 존재하지 않으면 자식노드를 만들어준다.
  • 마지막 노드에 도착하면 노드에 값을 넣어준다. ( 마지막 노드인것을 판별하기위한 플래그 )
• 삭제 :
  • 삽입과 다르게 for문이 아닌 재귀 방식으로 구현하였다.
  • 재귀방식으로 구현할경우 자식노드를 지워가면서 자식노드의 길이가 0이면 부모노드도 삭제 할 수 있다.
• 검색 :
  • 삽입과 마찬가지로 자식노드를 방문하면서 마지막 자식노드에 값이 존재한다면 문자열이 존재한다.
• 접두어 찾기 :
  • 접두어가 주어졌을때 접두어 까지의 부모노드를 탐색후, 그 이후 아래의 노드들을 모두 탐색해보아 원하는 접두어가 있는지 탐색한다.

class Node():
    def __init__(self, key):
        self.children = {}
        self.key = key
        self.data = None
        
class Trie():
    def __init__(self):
        self.head = Node(None)
        
    def find_all(self):
        current = self.head
        
        words = []
        current_nodes = [current]
        
        while current_nodes:
            next_nodes = []
            for node in current_nodes:
                for child in node.children:
                    next_node = node.children[child]
                    word = next_node.data
                    next_nodes.append(next_node)
                    if word is not None:
                        words.append(word)
            
            current_nodes = next_nodes
        
        return words
    
    def insert(self, string):
        current = self.head
        
        for char in string:
            if char not in current.children:
                current.children[char] = Node(char)
            
            current = current.children[char]
        
        current.data = string
        
    def remove(self, string):
        current = self.head
        
        def dfs(node : Node, string):
            if len(string) == 0:
                if node.data is None:
                    return False
                else:
                    node.data = None
                    return len(node.children) == 0
                
            char = string[0]
            if char not in node.children:
                return False
            
            ret = dfs(node.children[char], string[1:])
            
            if ret == True:
                node.children.pop(char)
                return len(node.children) == 0
            else:
                return False
            
        dfs(current, string)
        
    
    def search(self, string):
        current = self.head
        
        for char in string:
            if not char in current.children:
                return False
            
            current = current.children[char]
            
        return current.data != None
    
    
    def startwith(self, prefix):
        current = self.head
        
        for p in prefix:
            if not p in current.children:
                return None
            
            current = current.children[p]
        
        words = []
        
        if current.data:
            words.append(current.data)
        
        current_nodes = [current]
        
        while current_nodes:
            next_nodes = []
            for node in current_nodes:
                for key in node.children.keys():
                    word = node.children[key].data
                    if word is not None:
                        words.append(word)
                    
                    next_nodes.append(node.children[key])
            
            current_nodes = next_nodes
        
        return words