CS/자료구조

[자료구조] 트리(Tree)와 힙(Heap)

ummchicken 2023. 1. 24. 14:10

비선형 자료 구조란?

일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말한다.

일반적으로 트리나 그래프를 말한다.

 

 

 

트리(Tree)

트리는 계층적 관계(Hierarchical Relationship)을 표현하는 자료구조이다.

Node(노드)와 Edge(간선)로 이루어진 자료구조이다.

 

 

 

용어

- 노드 (Node) : 트리를 구성하고 있는 각각의 요소를 의미한다.

- 간선 (edge) : 노드와 노드를 연결하는 선

- 루트 노드 (Root Node) : A
트리 구조에서 최상위에 있는 노드를 의미한다.

- 단말 노트 (leaf node) : F, G, H, I, J
차수가 0인 노드, 즉 자식 노드가 없는 노드.

- 형제 노드 (sibling node) : H와 I는 형제 노드이다.
같은 부모 노드의 자식 노드들

- 조상 노드 : H의 조tkdshemsms D, B, A이다.
간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들.

- 자손 노드 : B의 자손 노드들은 D, E, H, I, J이다.
서브 트리에 있는 하위 레벨의 노드들

- 서브 트리 : 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

 

 

 

트리의 특징

  • 비선형 구조 
    • 1 : N 관계를 가지는 자료구조

 

  • 트리에는 사이클이 존재할 수 없다. (만약 사이클이 만들어진다면, 그것은 트리가 아니고 그래프다.)
  • 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한개의 부모 노드만을 가진다.
  • 리스트에서 head를 가지고 있으면, 리스트 전체를 가지고 있는 것과 같다. 트리에서는 노드가 그 역학을 한다.
  • 노드가 N개인 트리는 항상 N - 1개의 간선(edge)를 갖는다.

 

 

 

종류

이진 트리 (Binary Tree)

모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리이다.
각 노드가 자식노드를 최대 2개까지만 가질 수 있다.

 

 

 

- Full Binary Tree (정이진 트리) 
: 자식 노드가 0 또는 2개인 이진 트리

- Complete Binary Tree (완전 이진 트리)
: 왼쪽에서부터 채워져 있는 이진 트리를 의미한다.
마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 
마지막 레벨의 겨우 왼쪽부터 채워져 있다.

- 변질 이진 트리 (degenerate binary tree)
: 자식 노드가 하나밖에 없는 이진 트리를 의미한다.

- Perfect Binary Tree (포화 이진 트리)
: 모든 노드가 꽉 차 있는 이진 트리를 의미한다.

- 균형 이진 트리 (balance binary tree)
: 왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리를 의미한다.
map, set을 구성하는 레드 블랙 트리는 균형 이진 트리 중 하나이다.

 

※ 정 이진 트리 예시

 

 

 

 

 

이진 탐색 트리 (Binary Search Tree)

이진 탐색 트리는 이진 트리의 한 종류이다. 이진 트리에 추가적인 조건이 붙는다.

- 각 노드의 자식이 2개 이하이다.

- 각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다.

- 중복된 노드가 없어야 한다.
(중복이 없어야 하는 이유는?
: 검색 목적 자료구조인데, 굳이 중복이 많은 경우에 트리를 사용하여 검색 속도를 느리게 할 필요 없음. 
트리에 삽입하는 것보다, 노드에 count값을 가지게 하여 처리하는 것이 훨씬 효율적)
이진탐색트리의 목적은?
: 이진탐색 + 연결리스트

- 이진 탐색 : 탐색에 소요되는 시간복잡도는 O(logN), 
하지만 삽입, 삭제가 불가능하다.

- 연결 리스트 : 삽입, 삭제의 시간복잡도는 O(1), 
하지만 탐색하는 시간복잡도가 O(N).

▶▶▶ 이 두 가지를 합하여 장점을 보두 얻는 것이 '이진 탐색 트리'
즉, 효율적인 탐색 능력을 가지고, 자료의 삽입 삭제도 가능하게 만들자.

 

 

 

 

그래프와 트리의 차이

그래프는 정점과 간선으로 이루어진 자료구조를 말하며, 

트리는 그래프 중 하나로, 연결그래프이고 방향을 고려하지 않았을 때 
사이클이 일어나지 않는 그래프를 트리라고 한다.

트리는 그래서 간선의 개수에서 1을 뺀 게 노드의 개수를 가지는 특성을 가진다.

 

 

 

이진 탐색 트리란?

이진 탐색 트리는 이진 트리로, 최대 2개의 자식 노드를 가진다.

추가적으로 키가 유일하며,
각 노드의 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 크다

 

 

 

이진 탐색 트리의 문제점(시간 복잡도)은?

이진 탐색 트리는 선형적으로 구성될 때 시간 복잡도가 O(n)으로 커지는 문제점이 있다.
선형적으로 구성하지 않고, 균형 잡힌 트리로 구성하기 위해 나온 트리로 
AVL 트리과 레드 블랙 트리가 있다.

이 문제를 해결하기 위해 레드블랙 트리나 B-Tree 같은 밸런스 트리 종류들이 탄생했다.

※ AVL 트리 : 스스로 균형을 잡는 이진 탐색 트리이다.
두 자식 서브트리의 높이는 항상 최대 1만큼 차이 난다는 특징이 있다.
탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이며, 
삽입, 삭제를 할 때마다 균형이 맞지 않는 것을 맞추기 위해 트리 일부를 
왼쪽 혹은 오른쪽으로 회전시키며 균형을 잡는다.

 

 

 

레드 블랙 트리란?

레드 블랙 트리는 밸런스 트리(균형 이진 트리) 중 하나로 
탐색, 삽입, 삭제 모두 시간 복잡도가 O(logn)이다.

각 노드는 빨간색 또는 검은색의 색상을 나타내는 추가 비트를 저장하며, 
삽입 및 삭제 중에 트리가 균형을 유지하도록 하는 데 사용한다.

※ "모든 리프 노드와 루트 노드는 블랙이고,
어떤 노드가 레드이면 그 노드의 자식은 반드시 블랙이다." 등의 규칙을 기반으로
균형을 잡는 트리이다.

 

 

 

 

힙 (Heap)

- 완전 이진 트리의 일종.
- 우선순위 큐를 위해 만들어진 자료구조이다.
- 데이터의 최댓값, 최솟값을 빠르게 찾기 위해 고안된 자료구조
- 반정렬 상태
- 힙 트리는 중복된 값 허용 (이진 탐색 트리는 중복값 허용X)

힙을 이용하여 우선순위 큐를 구현하면, 
데이터의 삽입, 삭제를 하는 데 logN의 시간이 걸린다.
※ 우선순위 큐 : 우선순위 개념을 큐에 도입한 자료구조.
데이터들이 우선순위를 가지고 있다. 
우선순위가 높은 데이터가 먼저 나간다.
(스택은 LIFO, 큐는 FIFO)

언제 사용? : 시뮬레이션 시스템, 작업 스케줄링, 수치해석 계산.
우선순위 큐는 배열, 연결리스트, 힙으로 구현 (힙이 가장 효율적)
힙 → 삽입 : O(logn) , 삭제 : O(logn)

 

 

 

 

힙의 종류

 

 

최대 힙 (max heap)

부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리

 

 

최소 힙 (min heap)

부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리

 

 

 

 

힙 vs 이진탐색트리

공통점

둘다 이진트리로 이루어짐.

 

 

차이점

  • 힙
    • 최댓값 or 최솟값 검색을 위한 구조
    • 중복된 값 허용 O
    • 최대 힙일 경우에는 부모 노드의 값이 항상 자식 노드의 값보다 같거나 크고, 최소 힙일 경우에는 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같다.
    • 왼쪽 자식 노드와 오른쪽 자식 노드 사이에는 대소 관계가 없다.
    • → 느슨한 정렬 상태 유지

 

  • 이진 탐색 트리
    • 탐색을 위한 구조
    • 중복된 값 허용 X
    • 왼쪽 자식의 노드의 값이 제일 작고, 그 다음이 부모 노드, 그리고 오른쪽 자식 노드의 값이 제일 크다.
    • → 트리의 모든 노드가 정렬되어 있다.

 

 

 

 

 

출처

 

 

 

저작자표시 비영리 변경금지

'CS > 자료구조' 카테고리의 다른 글

[자료구조] 해시(Hash)  (0) 2023.01.24
[자료구조] 스택(Stack) & 큐(Queue)  (2) 2023.01.09
[자료구조] Array vs ArrayList vs LinkedList  (0) 2023.01.07

'CS/자료구조'의 다른글

  • 현재글[자료구조] 트리(Tree)와 힙(Heap)

관련글

댓글

티스토리툴바