트리 (Tree)
선형 데이터 구조 (Linear Data Structure)
-
items are organized one after another
- list, stack, queue
비선형 데이터 구조 (Nonlinear Data Structure)
- item have multiple immediate successor
- tree, graph
트리 (Tree)
비선형 자료구조
계층형 자료구조
확장되는 나무 모양의 구조
노드 (Node) : 트리를 구성하는 원소
간선 (Edge) : 노드를 연결하는 선
서브 트리 (Sub Tree) : 자식노드들이 독립하여 구성한 트리
노드간의 관계 용어
자식 (Child) : the node directly below node n in the tree
부모 (Parent) : the node directly above node n in the tree
형제 (Siblings) : nodes with a common parent
루트 (Root) : the only node in the tree with no parent, the name of tree
단말 (Leaf) : a node with no child
조상 (Ancestor) : a node on the path from the root to node n
자손 (Descendant) : a node on the path from node n to a leaf
높이 (Height)
노드의 높이 : 루트에서 노드에 이르는 간선의 수
트리의 높이 : 트리에 있는 노드의 높이 중에서 가장 큰 값
차수 (Degree)
노드의 차수 : 노드에 연결된 자식 노드의 수
트리의 차수 : 트리에 있는 노드의 차수 중에서 가장 큰 값
이진트리 (Binary Tree)
트리의 노드 구조를 일정하게 정의하여 트리의 구현과 연산이 쉽도록 정의한 트리
특성 1 : n개의 노드를 가진 이진 트리는 항상 (n-1)개의 간선을 가진다.
특성 2 : 높이 h 이진 트리는 최소 h+1개 최대 2^(h+1) - 1개의 노드를 가진다.
포화 이진 트리 : 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
완전 이진 트리 : 1번 부터 n번까지 빈 자리가 없는 이진 트리
편향 이진 트리 : 한쪽 방향의 자식 노드만을 가진 이진 트리
이진트리의 순회
typedef struct treeNode {
char data;
struct treeNode *left;
struct treeNode *right;
}treeNode;
전위 순회
void preorder(treeNode* root)
{
if(root)
{
printf("%c", root->data);
preorder(root->left);
preorder(root->right);
}
}
중위 순회
void inorder(treeNode* root)
{
if(root)
{
inorder(root->left);
printf("%c", root->data);
inorder(root->right);
}
}후위 순회
void postorder(treeNode* root)
{
if(root)
{
postorder(root->left);
postorder(root->right);
printf("%c", root->data);
}
}
이진 탐색 트리
이진 트리에 탐색을 위한 조건을 추가하여 정의한 자료구조
탐색 연산
searchBST(bsT, x)
p ← bsT;
if (p=null) then
return null;
if (x = p.key) then
return p;
if (x < p.key) then
return searchBST(p.left, x);
else
return searchBST(p.right, x);
end searchBST() 삽입 연산
insertBST(bsT, x)
p ← bsT;
while (p≠null) do {
if (x = p.key) return;
q ← p;
if (x < p.key) p ← p.left;
else p ← p.right;
}
new ← getNode();
new.key ← x;
new.left ← null;
new.right ← null;
if (bsT = null) bsT←new;
else if (x < q.key) q.left ← new;
else q.right ← new;
return;
end insertBST()삭제 연산
deleteBST(bsT, x)
p ← 삭제할 노드;
parent ← 삭제할 노드의 부모 노드;
if (p = null) then return;
if (p.left = null and p.right = null) then { // (1) 차수가 0인 노드(단말노드) 삭제
if (parent.left = p) then parent.left ← null;
else parent.right ← null;
}
else if (p.left = null or p.right = null) then { // (2) 차수가 1인 노드의 삭제
if (p.left ≠ null) then { // 왼쪽자식노드를 가진 경우
if (parent.left = p) then parent.left ← p.left;
else parent.right ← p.left;
}
else { // 오른쪽자식노드를 가진 경우
if (parent.left = p) then parent.left ← p.right;
else parent.right ← p.right;
}
}
else if (p.left ≠ null and p.right ≠ null) then { // (3) 차수가 2인 노드의 삭제
q ← maxNode(p.left);
p.key ← q.key;
deleteBST(p.left, p.key);
}
end deleteBST()
히프
완전 이진 트리에 있는 노드 중에서 키 값이 가장 큰 노드나 키 값이 가장 작은 노드를 찾기 위해서 만든 자료형
삽입 연산
insertHeap(heap, item)
if (n = heapSize) then heapFull();
n ← n+1; // 1
for (i ← n; ;) do {
if (i = 1) then exit;
if (item ≤ heap[ i/2 ]) then exit; // 2
heap[i] ← heap[ i/2 ]; // 3
i ← i/2 // 4
}
heap[i] ← item; // 5
end insertHeap()삭제 연산
deleteHeap(heap)
if (n = 0) then return error;
item ← heap[1]; // 1 루트노드의 원소를 item에 저장
temp ← heap[n]; // 2 마지막노드의 원소를 temp에 보관
n ← n-1; // 3 히프의 노드개수 1감소
i ← 1; // 4 i: temp원소가 저장될 노드번호 저장변수
j ← 2; // j : i의 좌측자식노드 번호
while (j ≤ n) do {
if (j < n) then
if (heap[j] < heap[j+1]) then j ← j+1; // 키값이 큰 자식노드 찾기
if (temp ≥ heap[j]) then exit; // 5 자식노드가 작으면, 자리 확정
heap[i] ← heap[j]; // 6 자식노드가 크면, 자리 교환
i ← j;
j ← j*2;
}
heap[i] ← temp; // 7
return item; // 8
end deleteHeap()