Trie 자료구조 – Swift

for c in currentNode.children.keys.sorted() {트리(trie)자료 구조는 트리(tree)와 발음이 비슷한데, 실제로도 tree와 비슷한 형태로 문자열이나 이와 유사한 형태의 연속열들을 저장할 수 있는 자료 구조이다. 보통 영단어들을 저장할 때 유용한데, 다음과 같은 장점들을 가진다.

  • 특정한 값을 찾을 때, 다른 구조들에 비해서 최악의 경우에서도 대개 더 나은 시간 복잡도를 보인다.
  • 해시테이블과 달리 키 충돌을 고려할 필요가 없다.
  • 특정한 요소에 다다르는 경로를 찾기위한 부가적인 해시 알고리듬을 요구하지 않는다.
  • 알파벳순으로 정렬하기가 매우 쉽다.

Trie는 어떤 단어의 첫글자와 그 다음에 올 수 있는 글자, 그리고 그 다음글자… 이런 식으로 각 글자들을 순서대로 직렬로 연결한다. 그리고 특정한 글자에서 다음글자는 0개 이상일 수 있다.

트리(trie)는 tree와 비슷하게 노드들의 연결로 구성된다. 영단어를 저장하는 trie의 경우 각각의 노드는 낱개의 알파벳문자 값을 가지며, 다음 글자로 오게될 문자들을 참조한다. 따라서 구현의 시작은 트리노드가 되어야 한다.

class TrieNode<T: Hashable> {
  var value: T?
  weak var parent: TrieNode<T>?
  var children:[T:TrieNode] = [:]
  var isTerminating = false

  init(value: T?, parent: TrieNode?=nil) {
    self.value = value
    self.parent = parent
  }

  convenience init() {
    self.init(value:nil, parent:nil)
  }
}

그리고 trie 자체는 nil value를 가지는 빈 루트 노드를 갖는 형식으로 초기화될 수 있다.

class Trie {
  let root = TrieNode<Character>()
}

단어 삽입

트리에 단어를 하나 추가한다고 생각해보자. 단어의 첫 글자는 루트의 자식이 되고, 그 다음 글자는 그 글자의 자식이되고… 이런 식으로 일련의 체인이 만들어질 것이다. 그런데 app과 apple 처럼 앞 부분을 공유하는 단어들이 같은 트리에 들어가는 경우에는 이미 존재하는 노드까지는 중복으로 설정할 필요가 없겠고, 다음 노드로 진행하면 된다. 전반적인 처리 방식은 연결 리스트(linked list)와 유사할 것이다.

extension TrieNode {
  func add(_ value: T) -> TrieNode {
    // 현재 노드에서 글자 하나를 추가한다. 
    // 리턴되는 노드는 해당 글자값을 갖는 서브 노드
    // 이미 그 글자를 가지고 있다면 해당 서브노드를 바로 리턴한다.
    guard children[value] == nil
      else { return children[value]! }
    let newNode = TrieNode(value: value, parent: self)
    children[value] = newNode
    return newNode
  }
}

extension Trie {
  func insert(word: String) {
    // 트리에 새 단어를 추가한다.
    // 단어의 앞 글자부터 루트에 추가해나가면서
    // 단어의 끝까지 글자를 추가한 후 마지막 노드에 
    // 종결 플래그를 설정한다. 
    var currentNode = root
    var currentIndex = word.startIndex
    while currentIndex < word.endIndex {
      let c = word[currentIndex]
      let nextNode = currentNode.add(c)
      currentIndex = word.index(after:currentIndex)
    }
    currentIndex.isTerminating = true
  }

단어 검사

다음은 trie에서 특정 단어를 포함하고 있는지 여부를 판단하는 메소드를 작성해보자. 삽입때와 마찬가지로 루트로부터 각 글자에 해당하는 자식이 있는지를 계속 검사해나간다. 마지막 글자까지 포함하고 있다면, 마지막 글자를 포함하는 해당 노드가 종료노드인지도 검사해야 한다. “hottest”를 삽입한 후에 “hot”을 검사하면 모든 글자를 다 갖고 있기 때문에 이런 구분이 필요하다.

extension Trie {
  func contains(_ word: String) -> Bool {
    var currentNode = root
    var currentIndex = word.startIndex
    while currentIndex < word.endIndex {
      let c = word[currentIndex]
      guard let x = currentNode.children[c] 
      else { return false }
      currentNode = x
      currentIndex = word.index(after:currentIndex)
   }
   return currentNode.isTerminating
}

순회하기

이번에는 트리 내에 삽입된 단어들을 알파벳 순으로 순회한다. 특정 레벨에서 하위 노드의 키값을 알파벳순으로 정렬한 다음, 빠른 자식부터 방문하는 식으로 순회하면 알파벳순으로 순회할 수 있다. 다음은 완성된 단어를 발견했을 때의 처리 핸들러를 인자로 받아서 알파벳순으로 탐색한 결과에서 단어가 완성될 때 해당 핸들러를 호출하는 식으로 구현한 순회 메소드이다.

extension Trie {
  func traverse(handler: @escaping (String) -> Void)) {
    func visit(_ node: TrieNode, with characters:[Character]) {
      if node.isTerminating {
         handler(String(characters))
      }
      for c in node.children.keys.sorted() {
         let nextNode = node.children[c]!
         visit(nextNode, with: characters + [c])
      }
    }
    visit(root, with:[])
  }
}

 

(Swift) – 힙(Heap) – 자료구조에 대해

heap은 일종의 바이너리 트리를 단일 배열을 이용해서 구현한 구조로,  부모 자식 간의 직접적인 참조를 갖지 않고 배열의 인덱스에 의해서 위치 관계를 파악한다. 특히 내부 배열의 상태는 부분적으로 정렬되는 것과 비슷한데, 항상 “맨 앞의 원소를 꺼내었을 때 그 값이 최대 혹은 최소가 된다”는 특성을 가진다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다. 주로 자료 구조에서는 최대/최소 힙, 바이너리 힙, 힙 큐 혹은 우선순위 큐와 같은 이름으로 불린다.

참고로 이 자료 구조의 파이썬 구현은 [우선순위 큐 혹은 최소/최대힙]에서 한 번 설명한 바 있다.

힙으로 할 수 있는 일은 다음과 같다.

  1. 우선순위 큐를 만든다.
  2. 힙 정렬 수행
  3. 변경가능한 집합의 최소값(혹은 최대값)을 빈번히 계산해야 할 때 유용하다. (특히 최단거리 탐색 시)

(Swift) – 힙(Heap) – 자료구조에 대해 더보기

이진탐색트리 (Binary Search Tree) 구현하기 – python

Binary Search Tree

이진 탐색 트리는 이진 트리 구조 속에 이진 탐색 알고리듬을 이용하여 키-값 쌍을 저장하는, 어찌보면 맵(혹은 사전이라고도 하는) 구조와 유사한 형태이다. 이진 탐색 자체가 데이터가 정렬된 상태를 전제하기 때문에, 구조 내에 자료를 삽입/삭제하는 과정이 단순하지는 않지만, 어떤 정렬된 상태의 키를 기준으로 데이터를 찾는데는 매우 유리한 구조이다.

이진 탐색 트리는 특정 노드가 어디에 위치하는데에는 크게 관심이 없다. 단지 이를 사용하여 효율적인 탐색을 할 수 있게 한다. 보면 알겠지만 해시테이블이 메모리 공간을 더 사용하고 반대급부로 성능을 얻는 것과는 달리, 이진 탐색 트리는 트리 구조 자체의 특성을 사용하므로 부가적인 메모리 공간의 낭비는 적다고 볼 수 있다.
이진탐색트리 (Binary Search Tree) 구현하기 – python 더보기

Parse Tree

이진트리 애플리케이션

파스 트리

트리 데이터 구조를 구현하는 방법을 알게 되면 이제 이 자료구조를 사용하여 실제 문제를 풀 수 있는 사용처에 대해서 살펴보자. 트리는 부분 요소로 나눠지는 데이터를 표현하기에 좋으므로 파싱과 관련된 작업에 많이 사용된다. 이럴 때 사용되는 트리를 파스 트리(Parse Tree)라 하는데, 파스 트리는 실제 문장이나 수학식을 표현하는데 사용될 수 있다.

http://interactivepython.org/runestone/static/pythonds/_images/nlParse.png

다음은 간단한 수학식을 트리로 표현한 것이다.

             *
           /   \
          +     -
         / \   / \
        7   3  5  2

> ( 7 + 3) * ( 5 - 2 )

Parse Tree 더보기

우선순위 큐 혹은 최소/최대힙

우선순위 큐 (priority queue)는 큐와 비슷하게 뒤쪽으로 원소를 삽입하고 앞쪽으로 꺼낼 수 있는 자료 구조이다. 하지만 각 원소는 내부적으로 논리적인 우선순위 값을 가지고 있고, 따라서 선입선출(FIFO)의 규칙에 의해서 나오는 것이 아니라, 큐 내부에서는 높은 우선순위를 갖는 원소가 앞쪽으로 오게 된다. 즉, 큐와 마찬가지로 원소를 꺼낼 때는 앞에서부터 꺼내게 되는데, 이 순서가 큐 내부에서의 우선순위 순과 일치하게 되는 것이다. 일종의 자동으로 정렬되는 큐라고 생각하면 된다. 언어나 알고리듬 책에 따라서는 이를 최소/최대힙(min/max heap) 혹은 힙큐(heap queue)라고 부르기도 한다. 우선순위 큐 혹은 최소/최대힙 더보기