Introduction
Terminology (용어)
- 트리 구조 : 계층구조로 데이터가 구성된 것
** 트리 tree :
finite set of one or more nodes such that
(1) There is a specially designated node called the root
(2) The remaining nodes are partitioned into n>=0 disjoint sets T1,... Tn, where each of these sets is a tree. T1,...,Tn are called the subtrees of the root.
(하나 이상의 노드로 이루어진 유한 집합,
(1) 특별이 지정된 루트가 존재
(2) 나머지 노드는 n개의 분리 집합으로 분할 할 수 있고, 분리 집합들은 각각 트리이자, 루트의 서브트리이다)
- tree의 정의는 순환적(recursive)하다.
** 노드 node :
the items of information plus the branches to other nodes
(하나의 정보 아이템에다, 다른 노르도 뻗어진 가지를 합한 것)
** 차수 degree :
The number of subtrees of a node (한 노드의 서브트리의 수)
** 트리의 차수 degree of a tree :
트리에 있는 노드의 최대 차수
* 리프 leaf : 차수가 0 인 노드 ( terminal node라고도 함)
* 형제 sibling : 부모가 같은 자식들
* 조상 ancestor : 루트에서부터 그 노드에 이르는 경로 상에 있는 모든 노드
** 노드의 레벨 level of node :
루트의 레벨을 1이라 정한 뒤 정의. 한 노드의 레벨이 i이면, 그 자식의 레벨은 i+1
** 트리의 높이 height : 트리에 속한 노드의 최대 레벨Representation of Tree
(1) List
(2) Left child-Right Sibling
(3) as Degree-Two Tree (차수가 2인 트리)Binary Trees
** binary trees :
finite set of nodes that either is empty or consists of a root and two disjoint binary trees called the left subtree and right subtree.
( 공백이거나, 루트와 왼쪽 서브트리,오른쪽 서브트리라고하는 두개의 분리된 이진 트리로 구성된 노드의 유한 집합)
**Binary search tree
Average
Worst case
Space
O(n)
O(n)
Search
O(log n)
O(n)
Insert
O(log n)
O(n)
Delete
O(log n)
O(n)
- 특성
: 한 노드가 최대 두개의 가지만 갖는다. (최대 차수 2)
: 왼쪽 서브트리와 오른쪽 서브트리를 구분
: 0개의 노드를 가질 수 있다
- 특별한 binary tree
skewed (편향) tree / complete (완전) binary tree / full(포화) binary tree이진트리 성질
- 이진트리의 레벨 i 에서의 최대 노드 수는 2i-1 (i1)이다
- 깊이가 k인 이진 트리의 최대 노드 수는 2k-1 (k1)이다
* full binary tree : 깊이가 k이고 노드 수가 2k-1(k0)이진 트리의 표현
(1) 배열 표현
: 노드 i 의 부모는 i/2, i가 1인 경우는 루트이므로 부모 존재 안함.
: 완전 이진 트리(순서대로 채움)의 경우 낭비 되는 공간이 없으므로 이상적
: 편향 트리는 배열 절반도 안 쓰게되기도 함. 최악의 경우 깊이 k의 편향트리2k-1개의 공간에서 k 개만을 사용
(2) 연결 표현
: 기존에 배열로 표현할 때는 트리 중간에 삽입/삭제 할 때, 노드 레벨의 변경에 따라 많은 노드의 위치가 변해야 하는 불편함이 있음. 그러나 연결 표현에서는 이러한 문제를 해결 가능.
: 각 노드는 leftChild, data, rightChild 필드를 갖는다.
( 부모를 알기 어려움 ---> parent 필드를 추가하여 개선 가능)
: 트리에 노드를 삽입/제거시 노드 레벨의 변경에 따라서 노드 위치 변경이 잦을 수 있는데,
이 때 배열 표현보다 연결 표현이 효율적이다.
: 노드의 부모를 알기 어렵다는 단점이 있음. 구현에서 개선 가능.Binary Tree Traversal and Tree Iteration
Intro
Inorder / Preorder / Postorder
- Preorder : + A B
- Inorder : A + B
- Postorder : A B +Iterative Inorder traversal (반복적 중위 순회)
Level-Order traversal ( 레벨 순서 순회) - 일반적인 순화
Traversal without a Stack ( 스택없이 순회)
(1) 부모 정보를 추가
(2) 매번 루트를 들린다(루트왔다갔다)
(3) 쓰레드 이진 트리Additional Binary Tree Operation (이진트리 추가연산)
(1) 트리 복사
(2) 트리 동일성 검사
- 동일성 : 두 이진 트리가 같은 구조, 대응되는 노드들의 정보가 동일
(3) 만족성Threaded Binary Trees (스레드 이진 트리)
(참고) 이진트리... 2n개의 링크중에서 n+1 개의 0 링크가 존재(NILL)
→ 0링크를 이용하여, 0링크는 다른 노드를 가리키는 포인터로 대치
(스레드 규칙)
(1) 노드 p의 rightChild가 0 링크
→ p 다음 방문 노드에 대한 포인터로 rightChild를 대치
⇒ 0 링크를 p의 중위 후속자에 대한 포인터로 대치
(2) 노드 p의 leftChild가 0 링크
→ p 방문 직전 노드에 대한 포인터로 leftChild를 대치
⇒ 0 링크를 p의 중위 선행자에 대한 포인터로 대치Heaps ( 힙 )
- 완전 이진 트리!
- 우선순위 큐 표현할 때 자주 이용우선순위 큐
- 우선순위가 가장 높거나 가장 낮은 노드를 우선 삭제
- 언제든지 임의의 우선순위를 가진 원소를 우선순위 큐에 삽입 가능
- 표현 방법 … 간단하게 ~ 무순서 선형 리스트“최대 힙”의 정의
- 최대(최소) 트리 : 각 노드의 키 값이 (자식이 존재할 때) 그 자식의 키 값보다 작지(크지) 않는 트리
- 최대 힙 = 최대 트리 && 완전 이진 트리
- 최소 힙 = 최소 트리 && 완전 이진 트리
- “루트 노드” - 힙을 정의하는 것에 따라 그 트리에서의 최소 값 또는 최대 값최대힙 삽입
- 추가 시 제일 마지막 노드로 위치
- 새 노드에서 시작해서 필요에 따라 루트 쪽으로 올라가는 bubbling up 방식 사용
ex) 5 추가
ex) 21 추가최대 힙 삭제
- 루트에서부터 삭제 (tickle down)
ex) 최대 힙 삭제 1
- 6개의 원소
- 루트 삭제
→ 원소 총 5개
→ 6번째 (마지막) 노드를 지우고 루트로 올린 후 tickle down
ex) 최대 힙 삭제 2
- 5개의 원소
- 루트 삭제 후
→ 원소 총 4개
→ 5번째 (마지막) 노드를 지우고 루트로 올린 후 tickle down
Binary Search Trees (이진탐색트리, BST)
Binary Search Tree
- 사전(dictionary) : 쌍의 집합. 키-원소로 구성. 같은 키를 가진 두 개의 쌍은 없다고 가정
(one key- one element)
- BST : 좋은성능 - 연산들은 키 값이나 rank(순위)에 따라 수행
- Binary search tree 성질
(1) 이진트리로서 공백일 수 있음
(2) 만약 공백이 아니라면 다음 성질 만족
ㄱ. 모든 원소는 서로 다른 유일한 키를 가짐
ㄴ. 왼쪽 서브트리의 키 값들은 루트보다 작다
ㄷ. 오른쪽 서브트리의 키 값들은 루트보다 크다
ㄹ. 서브트리 역시 이진 탐색 트리이다
⇒ O(logn)의 성능BST 탐색
- 이진 탐색과 동일한 원리
(참고) 이진 탐색search_binary(list, low, high)
while(low<=high) :
middle ← low와 high의 중간 위치
if 탐색값 == middle
return TRUE
else if 탐색값 < list[middle]
return binary_search( list[low], list[middle -1] )
else if 탐색값 > list[middle]
return binary_search( list[middle+1], list[high] )
return FALSEBST 삽입
- 탐색 이용 → 추가하려는 원소값 존재 여부 검사
- 이미 존재 → 추가 실패
- 존재 안함 → 탐색 시 제일 마지막으로 방문한 노드의 자식 노드로 추가
ex) BST 노드 추가 (30, 21)BST 삭제
노드 차수가,0 (단말노드) → 단순 삭제
1 (자식 1개) → 자식노드를 자식의 부모 노드에 연결
2 (자식 2개) → 왼쪽 서브트리의 제일 큰 원소 또는 오른쪽 서브트리의 제일 작은 원소 중 하나를 삭제된 노드로 대치
ex) 노드 차수가 0
ex) 노드 차수가 1
ex) 노드 차수가 2
(ㄱ) 왼쪽 서브트리의 가장 큰 원소
(ㄴ) 오른쪽 서브트리의 가장 작은 원소
BST 분할 (PASS)
BST 높이
- BST 평균 높이 log n, 최대 높이 n
- 최소의 높이 → 노드가 양쪽에 골고르 분포되어 있음 ⇒ 전체적 균형
- BST 삽입, 삭제시 균형을 이루도록 하면 수행시간 O(log n)
- 최악의 경우에도 높이가 log n인 탐색 트리
⇒ 균형 탐색 트리(Balanced Search Tree)
(참고. O(h)만에 가능한 것도 존재)
균형 탐색 트리 (예) AVL, 2-3, 2-3-4, Red-Black, B, B+ 등(!참고!) Binary Search와 Binary Search Tree의 차이점 (+ Heap Tree와의 차이점)
- Binary search와 Binary search Tree 는 근본적으로 같은 원리
- Binary Search .. 자료들이 배열에 저장 --- 삽입/삭제 어려움
⇒ 원소이동 빈번
- Binary Search Tree … 비교적 빠른 시간 안에 삽입/삭제 가능
⇒ 빈번한 경우 반드시 BST 사용
- BST 시간 복잡도
균형트리 ~ O(log n) , 불균형 트리 ~ O(n)Selection Trees (선택 트리)
선택트리
- K개의 런에 나뉘어져 있는 n개의 원소들을 하나의 순서순차(ordered sequence) 집합으로 합병하는 과정을 표현한 트리
- 런(run) : 원소들이 오름차순으로 정렬되어있는 순서순차(ordered sequence) 집합
- k개의 런 중에서 가장 작은 키값을 가진 원소를 순차적으로 출력
- k개의 원소 중에서 가장 작은 키값을 가진 원소를 선택 : k-1번 비교
- 선택 트리(selection tree) 자료 구조 이용 시 : 비교횟수 줄임
- 선택 트리의 종류 : 승자 트리, 패자 트리승자트리 : 각 노드가 두 개의 자식노드 중 더 작은 노드를 나타내는 완전 이진 트리
- 가장 작은 키 값을 가지는 원소가 승자로 올라가는 토너먼트 경기로 표현
- 트리의 각 내부 노드 : 두 자식 노드 원소의 토너먼트 승자
- 루트 노드 : 전체 토너먼트 승자, 즉 트리에서 가장 작은 키 값을 가진 원소
- 루트가 결정되는 대로 순서순차 집합에 출력하고 트리에서 삭제
- 삭제된 런의 다음 원소를 승자트리에 삽입하고 승자트리 재 구성
- 트리의 level... 레코드당 log (k+1)이 되기 때문에 재구성 시간은 O(log k)
⇒ n 개의 레코드를 모두 합병하는 데에는 O(n log k) 만큼 걸림
step1.
step2.
step3. 루트노드 … 순차순서 집합에 출력 → 트리에서 삭제
step 4.
step5.패자 트리 : 각 노드가 두 개의 자식노드 중 더 큰 노드를 나타내는 완전 이진 트리
- 루트 위에 0 번 노드가 추가된 완전 이진 트리
- 단말 노드는 각 런의 최소 키 값을 가진 원소
- 내부 노드는 토너먼트의 패자 원소
- 루트 (1번 노드)는 결승 토너먼트의 패자 원소
- 0 번 노드는 전체 승자 원소패자트리 구축 과정
- 두 자식 노드들이 부모노드에서 토너먼트 경기를 수행
- 패자는 부모노드에 남음
- 승자는 그 위 부모노드로 올라가서 다시 토너먼트 경기를 진행
- 루트노드의 토너먼트의 승자를 0번 노드로 올라가 순서순차 집합에 출력하고 트리에서 삭제
- 삭제된 런의 다음 원소를 패자트리에 삽입하고, 패자트리 재 구성예
step1.
step2.Forest
- 정의 : n (0)개의 분리(disjoint) 트리의 집합
- 트리에서 루트를 제거하면 forestforest → binary tree 변환
- T1,T2,...Tn이 트리로 구성된 포레스트 라면, 이 포레스트에 대응되는
이진 트리 B(T1,T2,...Tn)는
(1) n=0 이면 공백
(2) 0이 아니면, T1의 루트와 같은 루트를 가지며,
왼쪽 서브트리로 B(T11,T12,...T1n)을 가지는데 여기서 T11,T12,...T1n은
T1의 루트의 서브트리이다. 그리고 오른쪽 서브트리로 B(T2,...Tn)를 갖는다.forest traversal
- forest의 레벨 순서 순회 결과가 반드시 이진트리의 결과와 같지는 않다.Representation of Disjoint Sets (분리 집합의 표현)
- 분리
- 분리 합집합
- 탐색Counting Binary Trees ( 이진 트리의 개수 계산)
'Computers > Data Structure' 카테고리의 다른 글
| Chapter 7. Sorting (0) | 2013.10.10 |
|---|---|
| Chapter 6. Graphs (0) | 2013.10.10 |
| Chapter 4. Linked Lists (0) | 2013.10.10 |
| Chapter 3. Stack and Queue (0) | 2013.10.10 |
| Chapter 2. Arrays (0) | 2013.10.10 |