트라이와 적응형 자료 구조

 

 

 

---

 

트라이란 무엇이고
적응형 자료 구조는 무엇인가?

 

 

---

 

 

 

 

트라이 (Trie)

 

--

트라이는

문자열을 저장하고 검색하기 위한 트리 형태의 자료 구조로

문자열을 접두사 기준으로 다른 하위 트리로 분할하는 트리 기반 자료 구조다.

 

각 노드는 하나의 문자와 관련되어 있으며

루트에서부터 리프 노드까지의 경로가 하나의 문자열을 나타낸다.

 

 

트라이는

이진 탐색 트리와 마찬가지로, 루트 노드에서 시작하고

루트 노드는 빈 접두사를 나타낸다.

 

루트 노드의 자식 노드는 각 문자열의 다음 문자를 정의한다.

이로 인해 각 노드는 둘 이상의 자식을 가질 수 있다.

 

최소 하나 이상의 자식 노드가 있는 노드를 '내부 노드',

자식이 없는 노드를 '리프 노드'라고 부른다.

 

 

트라이 자료 구조의 각 노드 객체 구조 [JAVA]

class TrieNode {
    // 단어의 끝임을 나타내는 플래그
    boolean isEntry;
    // 자식 노드를 저장할 배열 (영어 소문자 기준, 26개의 자식 노드를 가질 수 있음)
    TrieNode[] children;

    // 생성자
    public TrieNode() {
        this.isEntry = false;
        this.children = new TrieNode[26]; // 'a' to 'z'
    }
}

위 노드 객체는
영어 소문자만을 사용한다는 가정하에
최대 26개의 자식을 가질 수 있도록 배열로 자식을 가리키는 포인터를 가진다.
(이는 굳이 배열이 아니라 맵을 사용 하여 자식 포인터를 가질 수도 있다.)

이러한 경우
만약 노드의 값이 c라는 것을 표현하고 싶으면
자식 노드를 저장하는 배열에 c를 위치하는 배열 위치에 배치시킨다.
그러면 값을 노드에 저장하지 않아도 해당 노드의 값은 c라는 것을 알 수 있다.

 

문자열의 끝임을 구분하기 위해 isEntry 필드가 존재하며

여러 개의 자식 포인터를 가지기 위해 배열로 포인터를 담고 있다.

 

추가로 노드에 특정 항목이 삽입된 횟수와 같이 보조 데이터들도 추가할 수 있다.

 

 

트라이 또한 이진 탐색 트리와 마찬가지로 트라이 객체로 루트 노드를 감싸서 트라이 인터페이스를 정리할 수 있다.

class TrieNode {
    boolean isEntry;
    TrieNode[] children;

    public TrieNode() {
        this.isEntry = false;
        this.children = new TrieNode[26]; // 'a' to 'z'
    }
}

public class Trie {
    private TrieNode root;

    // 생성자
    public Trie() {
        root = new TrieNode();
    }

    // 단어를 트라이에 삽입하는 메소드
    public void insert(String word) {
        TrieNode node = root;
        
        . . .
    }
    . . .
}

 

 

이진 탐색 트리와 달리

트라이에는 항상 (null이 아닌) 루트가 존재한다.

 

트라이 자료 구조 자체를 생성하는 동시에 해당 루트가 생성되기 때문이다.

--

 

 

 

 

트라이 탐색

 

--

트라이 탐색은

이진 탐색 트리 탐색과 유사하다.

 

루트 노드에서 시작하여 아래로 진행하며,

탐색 대상으로 이어지는 가지를 선택한다.

 

여기서 트라이는

문자열의 다음 글자에 해당하는 가지를 선택한다.

즉, 전체 문자열을 비교하거나 접두사의 앞부분은 비교할 필요가 없다.

이미 이전 노드에서 그 작업을 수행했기 때문이다.

그냥 다음 문자 하나만 고려하면 된다.

 

이러한 접근 방식을 코드로 구현하는 경우

한 가지 복잡한 부분은 

탐색의 각 단게에서 수행할 비교가 달라진다는 점이다.

 

첫 번째 단계에서는

일치하는 첫 번째 문자를 확인해야 하지만

 

두 번째 단계에서는

두 번째 문자를 확인해야 한다.

 

현재 단계에서 확인해야 하는 문자의 위치를 나타내는 인덱스를 재귀적인 탐색 함수에 전달하고,

각 재귀 수준에서 이를 증가시키면서 이런 추가 상태를 추적할 수 있다.

 

 

재귀적으로 트라이를 탐색하는 예시 코드 [JAVA]

// 재귀적으로 트라이를 검색하는 메소드
// current = 현재 노드 / target = 탐색할 목표 문자열 / index = 현재 인덱스 (트리 노드의 깊이)
public TrieNode trieNodeSearch(TrieNode current, String target, int index) {
    // 현재 위치가 문자열 끝에 도달한 경우
    if (index == target.length()) {
        if (current.isEntry) {
            return current;
        } else {
            return null;
        }
    }
    // 목표 문자열의 끝에 도달하지 않은 경우
    // 다음 문자를 검사함녀서 탐색을 계속 진행
    char nextLetter = target.charAt(index);		// 현재 인덱스에 해당하는 문자
    int nextIndex = letterToIndex(nextLetter);		// 현재 문자를 인덱스로 변환 (예시 a = 0, b = 1, ...)
    TrieNode nextChild = current.children[nextIndex];	// 변환한 인덱스에 위치하고 있는 다음 노드를 찾음
    
    if (nextChild == null) {
        return null;
    } else {
        return trieNodeSearch(nextChild, target, index + 1);	// 다음 인덱스를 가지고 재귀 호출
    }
}

Trie trie = new Trie();	// 트라이 생성

trie.insert("cat");	// "cat"문자열 삽입

TrieNode result = trie.trieNodeSearch(trie.root, "cat", 0);

 

 

 

트라이 예시 자료 구조

 

이렇게

트라이는 데이터가 있는 노드만 포함하기 때문에,

막다른 골목을 만나면 문자열이 트라이에 존재하지 않음을 알 수 있다.

 

얼핏 보면 많은 내부 노드를 추가하면 탐색 비용이 증가할 것 같아 보일 수 있지만

이러한 구조는 탐색을 크게 개선한다.

 

목표 문자열의 각 문자에 대해 현재 노드에서 단 한 번만 탐색을 수행하고

해당 문자에 해당하는 자식을 확인한 다음 적절한 자식 노드로 이동한다.

즉, 탐색 시 문자 비교 횟수는 목표 문자열의 길이에 선형적으로 비례해진다.

 

다만 이러한 효율성을 얻기 위해 메모리 사용 부분에서 상당한 비용을 지불해야 한다.

문자열마다 하나의 노드와 자식 노드를 가리키는 두 개의 포인터를 저장하는 대신

문자열의 문자마다 노드 하나와 잠재적 자식 노드를 가리킬 많은 포인터를 저장하게 된다.

 

위에 작성한 트라이 객체처럼 자식을 배열로 담게 되면
배열은 생성 당시 크기가 일정해야 하므로
자식 노드가 2개만 존재하더라도 나머지 24개의 배열 공간은 낭비가 된다.

그리고 각 노드마다 자식 노드를 담는 26크기의 배열이 존재하므로
노드 * 배열크기 26 으로 메모리를 차지하게 된다.

그래서 자식 노드의 개수가 적을 때는
자식 노드를 동적으로 저장할 수 있는 자료구조를 사용하는 방법을 고려하는 것이 좋을 수 있다.
예시로 'HashMap'이나 'TreeMap'과 같은 동적 자료구조를 사용하는 것이 효율적이다.

다만 배열을 사용할 때에는 문자를 인덱스로 구분했지만
맵을 사용하는 경우에는 직접 맵에 문자를 저장하여 문자로 직접 구분해야 한다.

--

 

 

 

 

트라이 노드 추가 및 제거

 

--

이진 탐색 트리와 마찬가지로,

트라이 또한 노드를 추가하거나 제거함으로써 데이터 변화를 정확하게 표현하는 동적 자료 구조다.

 

 

트라이 노드 추가

최상위 수준의 Trie 함수는 (null이 아닌) 루트 노드와 올바른 초기 깊이를 사용해

재귀적인 탐색 함수를 호출함으로써 삽입을 시작한다.

(트라이 생성 과정에서 초기 루트 노드를 할당하므로 루트 노드를 생성하는 것은 별도로 취급할 필요가 없다.)

 

 

트라이 노드 추가 예제 코드 [JAVA]

public class Trie {
    private TrieNode root;

    // 생성자
    public Trie() {
        root = new TrieNode();
    }

    // 재귀적으로 트라이에 단어를 삽입하는 메소드
    public void trieNodeInsert(TrieNode current, String newValue, int index) {
        // 현재 위치가 문자열 끝에 도달한 경우
        if (index == newValue.length()) {
            current.isEntry = true;
            
        } else {
            char nextLetter = newValue.charAt(index);	// 현재 인덱스의 문자를 가져옴
            int nextIndex = nextLetter - 'a'; // 해당 문자를 인덱스로 변환
            TrieNode nextChild = current.children[nextIndex];	// 변환한 인덱스에 존재하는 자식 노드를 가져옴
            
            if (nextChild == null) {
                // 자식 노드가 존재하지 않으면 새 노드를 생성
                nextChild = new TrieNode();
                current.children[nextIndex] = nextChild;
            }
            // 재귀적으로 다음 인덱스를 가지고 삽입 호출
            trieNodeInsert(nextChild, newValue, index + 1);
        }
    }
    
    // trieNodeInsert()메서드로 단어를 삽입하는 메서드
    public void insert(String word) {
        trieNodeInsert(root, word, 0);
    }
}

위 예시 코드는 자식 노드를 배열로 구성한 경우의 예시 코드로
맵을 이용한 경우에는 다르게 작성해야 한다.
(인덱스를 이용하는 방법대신 직접 문자로 저장하는 방식)

 

 

"auto"라는 문자열을 재귀적인 삽입 메서드로 삽입을 해보자.

public static void main(Stirng[] args) {
    Trie trie = new Trie();
    ...
    
    trie.insert("auto");
}

 

 

 

 

트라이 노드 제거

노드 제거도 비슷한 과정을 따르지만 삽입과는 순서가 반대다.

즉, 문자열의 끝에 해당하는 노드에서 시작해

트리를 거슬러 올라가면서 더 이상 필요가 없는 노드를 제거한다.

 

이때 제거할 노드 외에 다른 문자열의 유효한 접두사를 나타내는 자식 분기가 최소 하나라도 있는 내부 노드에 도달하거나, 트리에 저장된 문자열 자체를 나타내기 때문에 올바른 리프 역할을 할 수 있는 내부 노드에 도달하면 노드 제거를 중단한다.

 

 

트라이 노드 제거 예제 코드 [JAVA]

public class Trie {
    private TrieNode root;

    // 생성자
    public Trie() {
        root = new TrieNode();
    }

    // 재귀적으로 트라이에서 단어를 삭제하는 메소드
    // current = 현재 트라이 노드 / target = 삭제할 목표 문자열 / index = 현재 문자 인덱스
    public boolean trieNodeDelete(TrieNode current, String target, int index) {
        // 문자열의 끝에 도달한 경우
        if (index == target.length()) {
            if (current.isEntry) {
                current.isEntry = false;
            }
            
        } else {
            char nextLetter = target.charAt(index);	// 인덱스의 문자를 가져옴
            int nextIndex = nextLetter - 'a';	// 가져온 문자를 인덱스로 변환
            TrieNode nextChild = current.children[nextIndex];	// 변환한 인덱스에 위치하고 있는 자식 노드 가져옴
            // 만약 해당 자식 노드가 존재하면 다시 재귀 호출해서 반복
            if (nextChild != null) {
                if (trieNodeDelete(nextChild, target, index + 1)) {
                    current.children[nextIndex] = null;
                }
            }
        }
        
        // 현재 노드가 정상적인 항목이거나 자식이 존재하면 제거하면 안되므로
        // 현재 노드가 문자열의 끝인지 확인 (isEntry값이 true인 경우)
        if (current.isEntry) {
            return false;
        }
        // 현재 노드의 자식 노드가 모두 비어 있는지 반복하여 확인
        for (TrieNode child : current.children) {
            if (child != null) {
                return false;
            }
        }
        return true;
    }

    // 단어를 트라이에서 삭제하는 메소드
    public void delete(String word) {
        trieNodeDelete(root, word, 0);
    }
}

 

 

"apple"라는 문자열을 재귀적인 제거 메서드로 삽입을 해보자.

public static void main(Stirng[] args) {
    Trie trie = new Trie();
    ...
    
    trie.delete("apple");
}

 

 

문자열을 제거하려면 루트에서 대상 리프 노드까지 왕복해야 하므로

제거 비용도 목표 문자열의 길이에 비례한다.

 

탐색이나 삽입과 마찬가지로
해당 비용은 트라이에 저장된 전체 문자열의 개수와는 무관하다.

--

 

 

 

 

트라이가 중요한 이유

 

--

문자열을 가지고 이진 탐색 트리를 구현하게 되면 아래와 같은 모습이다.

 

 

문자열의 맨 앞 문자를 기준으로 두 문자열의 맨 앞 문자를 비교하여

작으면 좌측 자식 노드로

크면 우측 자식 노드로 위치하게 된다.

만약 동일하다면 그다음 문자를 기준으로 비교한다.

 

여기서 만약 "main"이라는 문자열을 탐색하려면

매번 노드의 문자열과 "main"문자열을 비교해 가면서 탐색해야 한다.

(문자열을 비교하는 비용은 숫자를 비교하는 비용보다 훨씬 비싸다.)

 

 

이렇게 문자열을 가지고 이진 탐색 트리를 구현하게 되면

탐색 비용이 단어의 길이와 수에 따라 결정된다는 문제가 있는데

이를 해결하는 방법이 트라이다.

 

위에 작성한 트라이 예시들로는

트라이의 큰 장점을 발휘하지 못할 수 있다.

 

실제로 추가된 가지로 인한 부가 비용 때문에 이진 탐색 트리나 정렬된 배열보다 트라이가 덜 효율적일 수 있다.

 

하지만 더 많은 문자열을 추가하고 공통 접두사를 가지는 문자열의 수가 늘어날수록 비용 측면에서 트라이가 더 효율적이다.

 

• 트라이에서의 탐색 비용은 저장된 항목의 개수와 무관하게 변하며
• 이진 탐색 트리처럼 노드마다 두 문자열을 비교하지 않는다. (문자열 비교 자체가 비용이 많이 든다.)

--