자료구조 기초 - 트리 데이터 구조

트리

 트리 데이터 구조는 데이터를 계층으로 정렬한다.

 

루트 노드

 나무의 뿌리(트리 구조에서는 맨 위)에 해당하며, 나머지 요소들은 루트 노드를 기준으로 구성된다.

자식 노드(하위 노드)

 루트 노드에서 멀어지는 방향으로 연결된 다른 노드

 자식 노드는 하나의 부모 노드를 가진다.

부모 노드(상위 노드)

 루트 노드를 향한 방향으로 연결된 또 다른 노드

 부모 노드는 여러 개의 자식 노드를 가진다.

리프 노드(말단 노드)

 더 이상 자식 노드를 갖지 않는 트리의 마지막 노드.

엣지(간선)

 노드를 연결하는 선

서브 트리(하위 트리)

 노드 하나와 그 자식 노드들로 구성된 트리

순회(Traversal)

 트리를 탐색하는 과정

 

노드에는 데이터를 저장하며 이때 저장된 데이터를 식별하는데 쓰이는 키와 저장된 데이터인 값을 포함할 수도 있다.

키와 값 사이의 관계를 키-값(Key-Value) 유형의 구조라고 한다. 

 

이진 트리(Binary Tree)

 가장 많이 사용되는 데이터 구조라고 할 수 있으며, 각 부모 노드가 항상 2개의 자식 노드와 연결되어 있다.

 이진 트리의 가장 일반적인 유형은 이진 탐색 트리다.

 이진 탐색 트리는 노드의 키를 기준으로 정렬한 상태이며, 모든 노드의 키는 왼쪽 서브트리보다 크고 오른쪽 서브트리보다

 작다. 가장 작은 키를 갖는 노드는 최상위 노드에서 가장 왼쪽에 있는 서브 트리의 말단, 가장 큰 키를 갖는 노드는 최상위

 노드에서 가장 오른족에 있는 서브트리의 말단에 있다.

 

 이진 탐색 트리로 할 수 있는 동작은 주로 세 가지로 노드 추가, 노드 삭제, 노드를 선택해 탐색하고자 하는 키가

 존재하는지 확인하는 동작이다.

 이진 탐색 트리는 트리 구조로 정렬된 데이터를 저장하는 데 효율적이어서 폭넓게 사용된다.

 

어떤 이유로든 불균형 이진 트리가 있을 수 있으며, 일반적으로 많은 노드가 단 하나의 자식 노드를 갖는 구조이다.

이 문제를 해결하기 위해 트리의 균형을 조정하는 과정을 거쳐야 한다. 트리의 역할은 유지하되, 가능한 한 최소 높이

(자식 노드의 계층이 최소)로 만드는 것이다.

 

AVL(Adelson-Velsky and Landis) 이진 트리

 균형잡힌 트리는 메모리를 더 효율적으로 사용할 수 있다. AVL트리는 자가 균형 이진 탐색 트리다.

 

 서브트리 2개 사이에서 높이 차이를 감지하면 트리 회전이라는 균형 조정 과정을 수행한다.

 트리 회전에 의해 노드 하나는 위로 이동하고 다른 노드 하나는 아래로 이동한다.

 

 트리의 균형과 트리의 균형을 조정하는 과정에서 중요한 것은 자체적으로 균형을 조정하는 트리와 관련되어 존재하는

 시간 복잡도이다. AVL 트리의 시간 복잡도는 O(logn)이다.

 AVL 트리는 일부 데이터베이스 검색 시스템에서 사용된다.

 

RB(Red-Black) 트리

 AVL 이진 탐색 트리와 비슷하게 자체적으로 균형을 조정하는 트리이지만,

 트리의 구조 때문에 균형을 조정하는 과정에서 트리 회전수가 적어 AVL 트리보다 효율적이다.

 RB 트리의 시간 복잡도는 O(logn)이다.

 

 RB 트리는 노드마다 빨강 또는 검정으로 해석되는 비트를 포함한다.

 일반적으로 루트 노드는 검정이고, 빨강 노드는 검정 노드를 자식 노드로 갖는다.

 

B 트리

데이터베이스 시스템을 설계할 때 사용하는 데이터 구조로, 역시 자체적인 균형 조정 기능을 갖춘 트리 유형이지만

위의 트리와 달리 자식 노드 3개 이상을 갖는 부모 노드가 있다.

많은  파일 시스템에서 데이터 계층 구조로 B 트리를 사용한다. 

파일 시스템에서는 폴더가 있고, 노드의 키-값 구조를 통해 폴더 각각의 이름을 파일 시스템의 객체와 연결할 수 있다.

폴더 각각에는 여러 파일이 들어있는 또 다른 폴더가 존재할 수 있는, 이러한 예에 적용하는데 이상적인 데이터 구조다.

 

힙(Heap)

 이진 트리 데이터 구조의 한 종류이며, 값이 최대 혹은 최소인 노드에 빠르게 접근해야하는 응용 프로그램에 적합하다.

 우선순위 큐는 힙을 사용해서 구현할 수 있으며, 힙의 구조를 설계하는 방법에는 두 가지가 있다.

 

최대 힙

 루트 노드가 힙에서 가장 큰 값이고 노드 각각의 값이 부모 노드의 값보다 작거나 같도록 구성된 힙.

최소 힙

 루트 노드가 힙에서 가장 작은 값이고 노드 각각의 값이 부모 노드의 값보다 크거나 같도록 구성된 힙.

 

 힙 데이터 구조는 힙 메모리와 전혀 다른 개념이다. 힙 메모리는 힙 데이터 구조와 아주 다른 방식으로 구현된다.