트리 자료구조

트리 자료구조

정의 

부모- 자식 관계를 계층적으로 표현한 보다 일반적인 자료구조

 

용어 정리

• 부모(조상)노드, 자식(자손)노드
• 루트노드 : 모든 노드의 조상노드
• 리프노드 : 자식이 없는 노드
• 레벨(level) : 루트 노드 "0레벨" 부터 시작하여 한 세대씩 내려가며 1씩 증가
• 깊이(depth) : 루트에서 다른 노드를 연결하는 에지 개수 
• 높이(height) : 노드의 높이는 자식 노드까지의 가장 큰 깊이 
• 트리 높이 : 루트 노드의 높이
• 경로 : 두 노드 사이를 연결하는 엣지의 시퀀스. 경로의 길이는 에지의 수
• 분지수(degree) : 노드의 분지수는 자신의 자식 노드 수.
  • 트리의 분지수는 가장 큰 분지수로 정의
• 부트리(subtree) : 어떤 노드와 그 노드의 자손노드들로 구성된 부분 트리

이진트리

모든 노드의 자식이 2개를 넘지 않는 트리

표현법

표현법 1. 하나의 리스트만으로 표현

• 레벨 0부터 차례로, 왼쪽부터 오른쪽으로 
• 자식노드가 없으면 None으로 표시
• A[k]에 저장된 노드의 왼쪽 자식노드는 A[2k+1], 오른쪽 자식노드는 A[2k+2]에 저장
• A[k]의 부모노드는 A[(k-1) // 2]에 저장
• 장점 : 연산 상수시간(O(1)) 내 가능
• 단점 : 빈 칸이 많을 경우 메모리 낭비가 심함

 

표현법 2. 리스트를 중복해서 표현(재귀적 표현)

표현법 3. 노드 class와 링크를 직접 제작하여 표현

순회

• 이진 트리의 노드를 빠짐없이 방문하는 일정한 규칙
• Preorder(MLR) : Middle 노드 출력 ->  Left Subtree 순회 -> Right Subtree 순회
• Inorder(LMR) : Left -> Middle -> Right
• Postorder(LRM) : Left -> Right -> Middle
• Left Subtree, Right Subtree 중에서는, 반드시 Left Subtree를 먼저 순회

힙(heap)

이진트리 중 하나

성질 

• 모양은 이진트리
  • 마지막 레벨을 제외한 각 레벨의 노드는 모두 채워져 있어야 함
  • 마지막 레벨에서는 왼쪽부터 노드가 채워져야 함
• 루트 노드를 제외한 모든 노드에 저장된 값(key)은 자신의 부모 노드보다 크면 안됨(부모 key >= 자식 key)
• 표현은 표현법 1 적용

제공 연산

• insert - O(logn)
• find_max - O(1)
• delete_max - O(logn)
  • 삭제한 후 남은 트리구조도 힙 성질을 만족해야 함

이진탐색트리(Binary Search Tree;BST)

성질

• None은 빈 BST
• BST의 노드 v의 key 값은 v.left.key보다 크거나 같고, v.right.key보다 작다.
• 즉, 왼쪽 자손 노드 key <= 부모 노드 key && 오른쪽 자손 노드 key > 부모 노드 key가 성립

제공연산

• search - O(h). h는 트리의 높이
• insert - O(h)
•  delete - O(h)

* n개의 노드를 갖는 이진트리의 높이는 최악의 경우 n-1까지 가능하므로, O(h) == O(n)이 된다.

* h를 가능한 작게 유지하는 것이 중요

 

delete 연산 방법

Merging 

삭제할 노드를 x, 왼쪽 서브트리를 L, 오른쪽 서프트리를 R이라 했을 때,

x를 제거한 후, L을 x의 위치로 이동 -> L에서 가장 큰 노드의 오른쪽 자식노드로 R 배치

 

Copying 

L에서 가장 큰 값을 갖는 노드 y 탐색 -> y의 key값을 x의 key 값으로 카피 -> y의 왼쪽 서브트리가 있다면, y의 위치로 옮김

 

균형이진탐색트리(Balanced Binary Search Tree;BBST)

n개의 노드를 갖는 이진트리의 높이를 항상 O(log n)이 되도록 유지할 수 있는 이진탐색트리

Rotation 기본연산

- 삽입과 삭제로 인해 h = O(log n)이라는 높이 조건을 만족할 수 있도록 수정이 필요한 경우, rotation 기본연산에 의해 모양 변경이 이루어진다. 

- left roataion과 right rotation이 있고, 서로 대칭적이다

- 회전 후에도 BST의 값의 순서가 그대로 유지되어야 한다

- 상수 개의 링크 수정으로 연산이 이뤄지므로 수행시간은 O(1)

AVL 트리

 정의

모든 노드에 대해서, 노드의 왼쪽 부트리와 오른쪽 부트리의 높이차가 1 이하인 이진탐색트리

 insert 연산

노드 삽입 : O(log n)

rebalance : 1회 혹은 2회 회전 = O(1)

=> total : O(log n)

 delete 연산

deleteByMerge, deleteByCopying 동일한 결과

노드 제거 : O(log n)

rebalance : 매 레벨마다 1회 혹은 2회 회전 = O(log n)

=> total : O(log n)

Red-Black 트리

 정의

다음 5가지 조건을 모두 만족하는 균형이진탐색트리

 

1. 각 노드는 red 또는 black의 색을 갖는다

2. 루트노드는 black

3. 리프노드인 NIL 노드의 색은 black으로 정의

4. 어떤 노드가 red라면, 두 자식노드는 모두 black 이다

5. 어떤 노드에서 서브트리의 리프 NIL노드까지의 모든 경로에 포함된 black 노드의 개수는 같다 (이를 black-height라고 칭함)

 insert 연산

 

 

---

위 포스팅은 신천수 교수님의 <자료구조 - Data Structures with Python 강좌>의 유튜브 내용을 기반으로 작성되었습니다.  https://youtube.com/playlist?list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK 

자료구조 - Data Structures with Python