[자료구조] 트리, 힙, 시간복잡도

FrameCreator

10 min readOct 10, 2021

*** 아래의 내용은 패스트 캠퍼스 자료구조 강의 자료(이준희 강사님 저)를 강의를 들으면서 정리한 내용입니다. ***

1. 트리

트리 (Tree) 구조

트리: Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조
실제로 어디에 많이 사용되나?
트리 중 이진 트리 (Binary Tree) 형태의 구조로, 탐색(검색) 알고리즘 구현을 위해 많이 사용됨

알아둘 용어

Node: 트리에서 데이터를 저장하는 기본 요소 (데이터와 다른 연결된 노드에 대한 Branch 정보 포함)
Root Node: 트리 맨 위에 있는 노드
Level: 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄
Parent Node: 어떤 노드의 다음 레벨에 연결된 노드
Child Node: 어떤 노드의 상위 레벨에 연결된 노드
Leaf Node (Terminal Node): Child Node가 하나도 없는 노드
Sibling (Brother Node): 동일한 Parent Node를 가진 노드
Depth: 트리에서 Node가 가질 수 있는 최대 Level

이진 트리와 이진 탐색 트리 (Binary Search Tree)

이진 트리: 노드의 최대 Branch가 2인 트리
이진 탐색 트리 (Binary Search Tree, BST): 이진 트리에 다음과 같은 추가적인 조건이 있는 트리
왼쪽 노드는 해당 노드보다 작은 값, 오른쪽 노드는 해당 노드보다 큰 값을 가지고 있음!
주요 용도: 데이터 검색(탐색)
장점: 탐색 속도를 개선할 수 있음

출처: https://www.mathwarehouse.com/programming/gifs/binary-search-tree.php#binary-search-tree-insertion-node)

이진트리와 정렬된 배열간의 탐색 비교

이진 탐색 트리 삭제

1. Leaf Node 삭제

Leaf Node: Child Node 가 없는 Node
삭제할 Node의 Parent Node가 삭제할 Node를 가리키지 않도록 한다.

2. Child Node 가 하나인 Node 삭제

삭제할 Node의 Parent Node가 삭제할 Node의 Child Node를 가리키도록 한다.

3. Child Node 가 두 개인 Node 삭제

삭제할 Node의 오른쪽 자식 중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키도록 한다.
삭제할 Node의 왼쪽 자식 중, 가장 큰 값을 삭제할 Node의 Parent Node가 가리키도록 한다.

3. 삭제할 Node의 오른쪽 자식중, 가장 작은 값을 삭제할 Node의 Parent Node가 가리키게 할 경우

삭제할 Node의 오른쪽 자식 선택
오른쪽 자식의 가장 왼쪽에 있는 Node를 선택
해당 Node를 삭제할 Node의 Parent Node의 왼쪽 Branch가 가리키게 함
해당 Node의 왼쪽 Branch가 삭제할 Node의 왼쪽 Child Node를 가리키게 함
해당 Node의 오른쪽 Branch가 삭제할 Node의 오른쪽 Child Node를 가리키게 함
만약 해당 Node가 오른쪽 Child Node를 가지고 있었을 경우에는, 해당 Node의 본래 Parent Node의 왼쪽 Branch가 해당 오른쪽 Child Node를 가리키게 함

이진 탐색 트리의 시간 복잡도와 단점

1. 시간 복잡도 (탐색시)

depth (트리의 높이) 를 h라고 표기한다면, O(h)
n개의 노드를 가진다면, ℎ=𝑙𝑜𝑔2𝑛 h=log2n 에 가까우므로, 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛)O(logn)
참고: 빅오 표기법에서 𝑙𝑜𝑔𝑛logn 에서의 log의 밑은 10이 아니라, 2입니다.
한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

이진 탐색 트리 단점

평균 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛)O(logn) 이지만,
이는 트리가 균형잡혀 있을 때의 평균 시간복잡도이며,
다음 예와 같이 구성되어 있을 경우, 최악의 경우는 링크드 리스트등과 동일한 성능을 보여줌 ( 𝑂(𝑛)O(n) )

2. 힙(Heap)

1. 힙 (Heap) 이란?

힙: 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree)
완전 이진 트리: 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

힙을 사용하는 이유
배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림
이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛)O(logn) 이 걸림
우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

2.힙 (Heap) 구조

힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음
힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임

각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)

최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음

2. 완전 이진 트리 형태를 가짐

힙과 이진 탐색 트리의 공통점과 차이점

공통점: 힙과 이진 탐색 트리는 모두 이진 트리임

2. 차이점:

힙은 각 노드의 값이 자식 노드보다 크거나 같음(Max Heap의 경우)
이진 탐색 트리는 왼쪽 자식 노드의 값이 가장 작고, 그 다음 부모 노드, 그 다음 오른쪽 자식 노드 값이 가장 큼
힙은 이진 탐색 트리의 조건인 자식 노드에서 작은 값은 왼쪽, 큰 값은 오른쪽이라는 조건은 없음
힙의 왼쪽 및 오른쪽 자식 노드의 값은 오른쪽이 클 수도 있고, 왼쪽이 클 수도 있음
이진 탐색 트리는 탐색을 위한 구조, 힙은 최대/최소값 검색을 위한 구조 중 하나로 이해하면 됨

3. 힙 (Heap) 동작

데이터를 힙 구조에 추가, 삭제하는 과정을 그림을 통해 선명하게 이해하기

1) 힙에 데이터 추가하기 — 기본 동작

힙은 완전 이진 트리이므로, 추가할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워지는 형태로 추가

2) 힙에 데이터 추가하기 — 추가할 데이터가 힙의 데이터보다 클 경우 (Max Heap 의 예)

먼저 추가된 데이터는 완전 이진 트리 구조에 맞추어, 최하단부 왼쪽 노드부터 채워짐
채워진 노드 위치에서, 부모 노드보다 값이 클 경우, 부모 노드와 위치를 바꿔주는 작업을 반복함 (swap)

3) 힙의 데이터 삭제하기 (Max Heap 의 예)

보통 삭제는 최상단 노드 (root 노드)를 삭제하는 것이 일반적임
힙의 용도는 최대값 또는 최소값을 root 노드에 놓아서, 최대값과 최소값을 바로 꺼내 쓸 수 있도록 하는 것임
상단의 데이터 삭제시, 가장 최하단부 왼쪽에 위치한 노드 (일반적으로 가장 마지막에 추가한 노드) 를 root 노드로 이동
root 노드의 값이 child node 보다 작을 경우, root 노드의 child node 중 가장 큰 값을 가진 노드와 root 노드 위치를 바꿔주는 작업을 반복함 (swap)

4. 힙 구현

힙과 배열

일반적으로 힙 구현시 배열 자료구조를 활용함
배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함
부모 노드 인덱스 번호 (parent node’s index) = 자식 노드 인덱스 번호 (child node’s index) // 2
왼쪽 자식 노드 인덱스 번호 (left child node’s index) = 부모 노드 인덱스 번호 (parent node’s index) * 2
오른쪽 자식 노드 인덱스 번호 (right child node’s index) = 부모 노드 인덱스 번호 (parent node’s index) * 2 + 1

5. 힙 (Heap) 시간 복잡도

depth (트리의 높이) 를 h라고 표기한다면,
n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 ℎ=log2n 에 가까우므로, 시간 복잡도는 O(logn)
참고: 빅오 표기법에서logn 에서의 log의 밑은 10이 아니라, 2입니다.
한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함

3. 시간복잡도

알고리즘 복잡도 계산 항목

시간 복잡도: 알고리즘 실행 속도
공간 복잡도: 알고리즘이 사용하는 메모리 사이즈

프로그래밍에서 시간 복잡도에 가장 영향을 많이 미치는 요소는 반복문

입력의 크기가 커지면 커질수록 반복문이 알고리즘 수행 시간을 지배함

알고리즘 성능 표기법

Big O (빅-오) 표기법: O(N)

알고리즘 최악의 실행 시간을 표기
가장 많이/일반적으로 사용함
아무리 최악의 상황이라도, 이정도의 성능은 보장한다는 의미이기 때문

2) Ω (오메가) 표기법: Ω(N)

오메가 표기법은 알고리즘 최상의 실행 시간을 표기

3) Θ (세타) 표기법: Θ(N)

오메가 표기법은 알고리즘 평균 실행 시간을 표기

시간 복잡도 계산은 반복문이 핵심 요소임을 인지하고, 계산 표기는 최상, 평균, 최악 중, 최악의 시간인 Big-O 표기법을 중심으로 익히면 됨

대문자 O 표기법

빅 오 표기법, Big-O 표기법 이라고도 부름
O(입력)
입력 n 에 따라 결정되는 시간 복잡도 함수
O(1), O(logn), O(n), O(𝑛logn), O(𝑛의2제곱), O(2의𝑛제곱), O(n!)등으로 표기함
입력 n 의 크기에 따라 기하급수적으로 시간 복잡도가 늘어날 수 있음
O(1) < O(logn) < O(n) < O(𝑛logn) < O(𝑛의2제곱) < O(2의𝑛제곱) < O(n!)
참고: log n 의 베이스는 2-log2n
단순하게 입력 n에 따라, 몇번 실행이 되는지를 계산하면 됩니다.
표현식에 가장 큰 영향을 미치는 n 의 단위로 표기합니다.
n이 1이든 100이든, 1000이든, 10000이든 실행을
무조건 2회(상수회) 실행한다: O(1) n에 따라, n번, n + 10 번, 또는 3n + 10 번등 실행한다: O(n)
n에 따라 n의2제곱번, 𝑛의2제곱 + 1000 번, 100𝑛의2제곱–100, 또는 300𝑛의2제곱 + 1번등 실행한다: O(𝑛의2제곱)

** 위의 내용은 패스트 캠퍼스 자료구조 강의 자료(이준희 강사님 저)를 강의를 들으면서 정리한 내용입니다. ***