트리

노력을 즐기는 사람·2020년 12월 25일
0

박상길님의 파이썬 알고리즘 인터뷰를 읽으며 내용을 정리한 포스팅입니다.

트리

트리는 재귀로 정의된 자기 참조 자료구조이다. 트리의 자식도 트리고 트리의 자식의 자식도 트리다. 이를 서브트리로 구성된다고 한다.

트리는 루트부터 시작되고 루트는 항상 자식 노드를 가진다. 각 노드들을 잇는 선은 간선이라고 한다.자식 노드의 개수는 차수라고 하며 크기는 자신을 포함한 모든 자식노드의 개수를 말한다. 높이는 현재 위치에서부터 리프까지의 거리, 깊이는 루트에서부터 현재 노드까지의 거리이다.

이진트리

트리 중에서도 가장 널리 사용되는 트리 자료구조는 이진 트리이진 탐색 트리이다
이진 트리는 모든 노드의 차수가 2이하인 트리를 말한다. (차수: 자식 노드의 수)

이진 트리의 유형

  • 정 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
  • 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
  • 포화 이진 트리(Perfect Binary Tree): 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로, 가장 완벽한 유형의 트리다.

그래프 vs 트리

  • 트리는 순환 구조가 아니다.
  • 트리는 특수한 형태의 그래프의 일종이며 그래프의 범주에 포함된다.
  • 트리는 부모 노드에서 자식 노드를 가리키는 단방향이다. 그래프는 양방향이다.

힙은 힙의 특성_(최소 힙에서는 부모가 항상 자식보다 작거나 같다)를 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조이다.

앞서 말했듯이 힙은 트리 기반의 자료구조이다.

파이썬에서 이용한 heapq 모듈이 힙으로 구현되어 있고 파이썬에서는 최소 힙만 구현되어 있다. 최소 힙은 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 되며 우선순위 큐에서 가장 작은 값을 추출하는 것은 힙의 루트를 가져오는 형태로 구현된다.

우선순위 큐 ADT는 주로 힙으로 구현하고 힙은 주로 배열로 구현한다. 결국 우선순위 큐는 배열로 구현하는 셈이다.

힙은 정렬된 구조가 아니다. 최소 힙의 노드는 부모가 가장 작다는 조건만 만족할 뿐 정렬되어 있지 않다.
예를들어 레벨이 낮은 노드가 레벨이 높은 노드보다 클 수도 있다는 뜻이다. 힙은 부모, 자식간의 관계만 정의할 뿐, 좌우에 대한 관계는 정의하지 않기 때문이다.

자식 노드가 둘인 힙은 이진 힙이라고 부르며 주로 이진 힙이 널리 사용된다. 힙은 완전 이진 트리이다.

위와 같이 힙을 배열로 손쉽게 표현할 수 있다.

  • 이진 힙은 완전 이진 트리 형태이기 때문에 배열에 빈틈없이 배치가 가능하다.
  • 계산을 편하게 하기 위해서 인덱스는 1부터 시작하도록 설계한다.
  • 힙은 다익스트라 알고리즘의 시간 복잡도를 O(V^2)에서 O(Elog V)로 줄어들 수 있게 만들었다.
  • 힙 정렬, 프림 알고리즘으로 구현하는 최소 신장 트리, 중앙값의 근사값을 빠르게 구하기 등에 활동된다.
  • 힙은 힙 정렬 알고리즘을 고안하면서 설계했다고 한다.

삽입

힙은 부모 노드가 자식 노드보다 작아야 한다는 규칙을 가지고 있다.
이러한 규칙을 깨지 않으면서 데이터를 삽입해기 위해 다음의 절차를 따른다.

  1. 일단 가장 하위 레벨의 가장 왼쪽에 삽입한다.
  2. 부모의 값과 비교해서 값이 더 작은 경우에 위치를 변경한다.
  3. 계속해서 부모 값과 비교해서 위치 변경을 반복한다. 가장 작을 경우 루트 노드가 된다.

삽입 한 후 아래와 같이 부모와 자식 간의 대소 관계에 따라 swap이 발생한다

추출

힙은 루트가 항상 작은 수를 가지고 있기 때문에 그냥 루트를 추출하면 된다.
그렇지만 부모 노드가 자식 노드보다 작아야 한다는 규칙이 깨지기 때문에 또 부모와 자식 노드의 대소 관게를 정리해주는 절차가 필요하다.

  1. 루트 노드를 추출한다.
  2. 루트 자리에 가장 하위 레벨이며 가장 왼쪽에 위치한 노드를 배치한다.
  3. 부모 노드와 자식 노드의 대소 관계를 비교하며 위치를 바꾸는 것을 반복한다.



트라이(Trie)

트라이는 검색 트리의 일종으로서 일반적으로 키가 문자열인 동적 배열 또는 연관 배열을 저장하는데 사용되는 정렬된 트리 자료구조이다.

트라이는 실무에서 매우 유용하게 쓰이는 자료구조이며 특히 자연어 처리(NLP) 분야에서 문자열 탐색을 위한 자료구조로 널리 쓰이고 있다.

트라이는 기존의 자료구조들과는 다르게 이진 트리가 아닌 다진 트리의 형태를 띤다

검색을 뜻하는 'retrieval'의 중간 음절에서 용어를 따왔다고 한다.

트라이는 각각의 문자 단위로 색인을 구축한 것과 유사한데 수백 개의 문자가 있어도 문자열의 길이만큼만 탐색하여 단어를 탐색할 수 있다. 이러한 특성을 통해서 자연어 처리 분야에서 형태소 분석기에서 분석 패턴을 트라이로 만들어두고 자연어 문장에 대한 패턴을 찾아 처리하는 등으로 활용하고 있다.

만약 angel, answer, angry 세 개의 단어를 트라이에 저장한다면 다음과 같다.

트라이는 문자열을 위한 트리의 형태이기 때문에 문자의 개수만큼 자식이 있어야한다. 그러므로 상당히 많은 자식 노드를 갖고 있게 된다.

profile
노력하는 자는 즐기는 자를 이길 수 없다

0개의 댓글