트라이(Trie) Swift

트라이

트라이는 문자열이 트리형태로 저장된 자료구조이다.

특정 문자열을 탐색할때 특화된 알고리즘으로, 트리는 K진 트리이다. (K는 문자열의 첫번째 문자의 종류)

 

예로 문자열 "apple", "banana", "avocado" 세가지가 있다고 하면 아래와 같은 트리형태로 만들 수 있다.

트리의 최상단노드는 비워두고, 그아래로 k개의 접두사를 갖는 자식노드들을 만든다.

문자열 세개중 중복되지 않는 접두사는 a,b로 최상단노드는 두개의 자식노드를 갖는다.

우리가 문자열을 비교할때, 앞에서부터 차례로 읽어나가듯이, 주어진 문자열을 순차적으로 연결시킨다.

그리고 문자열을 모두 연결시켰다면 마지막노드에 해당노드가 마지막임을 저장해둔다.(Bool 변수를 이용)

 

주어진 문자열에서 특정 문자열을 찾을때, 최상단 노드부터 시작하여 문자열을 검사해나간다.

이때 문자열이 연결되어 있지 않거나, 문자를 모두 찾아갔지만 해당 노드가 끝이아니라면, 해당 문자열은 찾을 수 없다.

 

트라이 자료구조는 특정문자열을 수정하거나 찾는데 O(N)만큼 걸리지만(트리형태의 자료구조에서 문자수만큼 연결하면된다.)

각 노드의 자식노드는 문자열의 최대 경우의수(소문자 26개, 대문자 26개)를 저장하기위해 메모리를 할당해야하므로

메모리가 추가적으로 많이필요하다.

 

트라이를 코드로 구현하면 다음과 같다.

import Foundation

// 트라이 자료구조
class Trie {
    // 트라이의 자식노드 메모리 할당(여기서는 소문자만 취급한다.)
    // 소문자의 아스키코드로 접근하기위해서 소문자의 갯수만큼 할당
    var child: [Trie?] = Array(repeating: nil, count: 26)
    // 해당 노드가 문자열의 마지막인지?
    var end = false
    
    // 트라이에 문자열을 넣는다. 외부에서 문자열String을 받음
    // 받은 문자열을 한개의 문자들로 나누고 insertCharater함수에 넘겨준다.
    // index는 0: 최상단노드부터 추가해주기 위해서
    func insert(_ s: String) {
        let arr: [Character] = Array(s)
        insertCharacter(arr, 0)
    }
    // 문자 배열과 인덱스를 넘겨받고 실행
    func insertCharacter(_ arr: [Character],_ index: Int) {
        // 해당 문자열을 모두 입력했다면 현재 노드가 마지막임을 설정하고 종료
        if arr.count == index {
            self.end = true
            return
        }
        // 아스키코드로 변환 범위: 0...25 (자식노드배열에 넣기위해)
        let num = toNumber(arr[index])
        
        // 현재 문자열의 아스키코드로 자식노드를 생성해준다.
        // apple을 입력해놓고 avocado를 입력할때, a는 이전에 생성해두었지만, v는 생성해두지 않았기에 생성
        if child[num] == nil {
            child[num] = Trie()
        }
        //남은 문자도 트리에 연결하기 위해 재귀호출
        child[num]?.insertCharacter(arr, index+1)
    }
    // 해당 문자를 아스키코드로 변환하지만 0~25 범위에 존재하게끔 소문자의 첫번째 문자 a의 아스키코드를 뺌
    func toNumber(_ c: Character) -> Int{
        return Int(c.asciiValue! - Character("a").asciiValue!)
    }
    
    // 문자열String을 받으면 해당 문자가 존재하는지 bool값 리턴
    // 문자열String을 역시 문자배열로 변환하여 내부함수 findCharacter를 실행
    func find(_ s: String) -> Bool{
        let arr: [Character] = Array(s)
        return findCharacter(arr,0)
    }
    // 문자열이 존재하는지 파악하기위해 재귀호출
    func findCharacter(_ arr: [Character],_ index: Int) -> Bool {
        // 문자열이 모두 존재하고, 마지막 문자가 끝나는노드라면 true
        // 문자열이 모두 존재했지만, 마지막 문자가 끝나지않는 노드라면 false
        if arr.count == index {
            if self.end { return true }
            return false
        }
        // 해당 문자를 아스키코드로 변환
        let num = toNumber(arr[index])
        // 해당문자의 자식노드가 존재하지않다면 더 찾을 수 없으므로 false
        if child[num] == nil { return false }
        // 그다음 문자도 확인
        return child[num]!.findCharacter(arr, index+1)
    }
}