태그 보관물: data structure

Trie

트리(Trie) 자료구조

이 글에서는 Tree와의 구분을 위해 Trie라는 영문 표기를 사용합니다. 이 둘은 똑같이 트리1라 발음하며, 오타가 아닌 서로 다른 자료 구조입니다.

Trie는 특히 영단어들을 저장하는데 유용한 자료구조로 다음과 같은 장점을 가진다.

  • 값을 찾는 것은 최악의 경우에서 더 나은 시간 복잡도를 보인다.
  • 해시테이블과는 달리 키 충돌을 염려하지 않아도 된다.
  • 특정한 요소에 다다르는 경로를 찾기위한 부가적인 해시 알고리듬을 요구하지 않는다.
  • 트리 자료구조는 알파벳순으로 정렬하기가 매우 쉽다.

Continue reading “Trie” »

힙(Heap) – 자료구조 (Swift)

heap은 일종의 바이너리트리로, 단일 배열을 이용해서 구현하며, 각 노드간의 포인터를 가지지 않는다. 트리는 내부적으로 부분적으로 정렬된 상태를 유지한다. 따라서 루트 요소를 꺼내면 정렬된 상태를 얻을 수 있다. 힙은 흔히 최대힙과 최소힙으로 구분하는데 이는 동일한 것이며 단지 정렬 순서만 다르다.

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

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

배열의 인덱스가 0부터 시작한다고 가정하면, 다음과 같은 방식으로 배열을 이진트리로 바꿀 수 있다.

  1. 인덱스 0인 요소가 루트가 된다.
  2. 루트의 왼쪽 자식의 인덱스는 1 (0 * 2 + 1), 오른쪽 자식은 오른쪽 자식은 2 (0 * 2 + 2)가 된다.
  3. 특정 인덱스의 부모요소의 인덱스는 (i – 1) / 2 로 구할 수 있다.

힙에 원소를 추가하면 배열의 맨 뒤에 원소를 붙이고, 해당 자리에서 부모보다 그 원소가 작으면 부모와 위치를 교환한다. 이 과정을 더 이상 올라갈 수 없을 때 까지 반복하면 된다.

힙에서 루트를 꺼내는 경우에는 배열의 맨 마지막 요소를 루트 자리에 넣는다. 그런다음 좌/우 자식 중에서 더 작은 요소가 자신보다 작으면 위치를 교환한다. 이 과정을 더 이상 계속할 수 없을 때까지 반복한다.

기본 구성

힙의 기본구성은 데이터를 저장할 배열과, 각 원소간의 순서를 비교할 평가함수이다. 이 둘은 외부에 노출될 필요는 없다. T가 Comparable 프로토콜을 따르는 타입이어도 되지만, 여기서는 커스텀한 비교 장치를 따로 가질 수 있도록 한다.


public struct Heap<T> {
    public typealias Comparator = (T, T) -> Bool
    private var __isOrderedBefor: Comparator
    private var elements: [T] = []

    init(comparator: Comparator) {
        __isOrderedBefor = comparator
    }
}

프로퍼티

힙이 비어있는지, 가장 상위에 올라와 있는 요소가 무엇인지와 같은 프로퍼티도 만들어준다. 물론 힙이 비어있는 경우 이 값은 nil이 될 수 있다.


var isEmpty: Bool { return elements.isEmpty }
var peak: T? { return elements.isEmpty ? nil : elements[0] }

그런데 위에서 정의했듯이 peak 은 그냥 배열의 .first 아닌가.


var peak: T? { return elements.first }

이렇게 수정한다. Continue reading “힙(Heap) – 자료구조 (Swift)” »