자료구조 10 : 트리 ADT

LeeWonjin·2022년 6월 15일
자료구조학부
0

[학부]자료구조/알고리즘

목록 보기
10/18

개요

계층적으로 저장된 데이터 원소를 모델링

루트 원소는 0개의 부모, 0개 이상의 자식을 갖는다.
루트가 아닌 원소는 1개의 부모, 0개 이상의 자식을 갖는다.

용어

  • 노드
    • 루트 : 부모가 없는 노드
    • 내부 노드 : 1개 이상의 자식이 있는 노드
    • 외부 노드(리프 노드) 자식이 없는 노드
    • 형제(siblings) : 부모가 같은 노드들
    • 조상 : 부모~루트 사이의 노드들
    • 자손 : 하위의 모든 노드들
    • 부트리 : 자신과 자손
    • 레벨 d : 깊이=d인 노드들
  • 그 외
    • 경로 : 조상 또는 자손을 따라 이어진 노드 시퀀스
    • 경로길이 : 경로 내 간선의 수
    • 깊이 : 루트로부터 어떤 노드에 이르는 유일한 경로길이 (루트노드 0)
      • 루트 노드의 깊이 = 0
      • 그 외 노드의 깊이 = 부모 노드의 깊이 + 1
    • 높이 : 외부노드에 이르는 가장 긴 경로길이 (외부노드 0)
      • 외부 노드의 높이 = 0
      • 그 외 노드의 깊이 = 자식들 중 가장 큰 높이 + 1

메소드

  • integer size()
  • node root()
  • node parent(v)
  • node children(v)
  • element element(v)
  • bool isEmpty()
  • bool isInternal(v)
  • bool ixExternal(v)
  • bool isRoot(v)
  • swapElements(v, w) : v노드값과 w노드값 교체
  • element setElement(v, e) : v노드의 값을 e로 설정

트리 구현

프로퍼티

Alg depth(v)
  input node v
  output depth of v
1. if(isRoot(v))
     return 0
   else
     return 1 + depth(parent(v))
     
Alg height(v)
  input node v
  output height of v
1. if(isExternal(v))
     return 0
   else
     h ← 0
     for each c ∈ children(v)
       h ← max(h, height(c))
     reutrn 1 + h

순회

     A
  ┌──────┐
  B      C
┌─┬─┐    │
D E F    G

위 트리에 대해서

  • 선위순회 : A - B - D - E - F - C - G
  • 후위순회 : D - E - F - B - G - C - A
  • 레벨순회 : A - B - C - D - E - F - G
Alg preorder()
1. visit(v)
2. for each child ∈ children(v)
     preorder(child)

Alg postorder()
1. for each child ∈ children(v)
     postorder(child)
2. visit(v)

Alg levelorder()
1. Q.enqueue(v)
2. while(!Q.isEmpty)
     v ← Q.dequeue()
     visit(v)
     for each child ∈ children(v)
       Q.enqueue(child)
3. return

연결 트리 (연결리스트 기반 트리)

  • 노드 저장내용 방안 1
    • 원소
    • 부모노드
    • 자식노드 리스트
  • 노드 저장내용 방안 2
    • 원소
    • 부모노드
    • 첫째 자식노드
    • 동생 노드

*** 방안2를 택할 경우 children(v) 처리시간은 자식개수만큼 소요

이진트리

트리ADT의 확장

메소드

  • node leftChild(v)
  • node rightChild(v)
  • node sibling(v)

순회

Alg preorder(v)
1. visit(v)
2. if(isInternal(v))
     preorder(leftChild(v))
     preorder(rightChild(v))

Alg inorder()
1. if(isInternal(v))
     inorder(leftChild(v))
2. visit(v)
3. if(isInternal(v))
     inorder(rightChild(v))

Alg postorder()
1. if(isInternal(v))
     postorder(leftChild(v))
     postorder(rightChild(v))
2. visit(v)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Node {
	struct _Node* left;
	struct _Node* right;
	int elem;
} Node;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->left = NULL;
	p->right = NULL;

	return p;
}

Node* findNodeByElem(Node* p, int elem) {
	if (p->elem == elem)
		return p;

	if (p->left != NULL) {
		Node* left = findNodeByElem(p->left, elem);
		if (left != NULL)
			return left;
	}

	if (p->right != NULL) {
		Node* right = findNodeByElem(p->right, elem);
		if (right != NULL)
			return right;
	}

	return NULL;
}

void addLeftNode(Node* root, int parentElem, int elem) {
	Node* newNode = getNode();
	newNode->elem = elem;

	Node* parent = findNodeByElem(root, parentElem);
	parent->left = newNode;
}

void addRightNode(Node* root, int parentElem, int elem) {
	Node* newNode = getNode();
	newNode->elem = elem;

	Node* parent = findNodeByElem(root, parentElem);
	parent->right = newNode;
}

void preOrder(Node* p) {
	printf("%d ", p->elem);
	if (p->left != NULL)
		preOrder(p->left);
	if (p->right != NULL)
		preOrder(p->right);
}

void inOrder(Node* p) {
	if (p->left != NULL)
		inOrder(p->left);

	printf("%d ", p->elem);

	if (p->right != NULL)
		inOrder(p->right);
}

void postOrder(Node* p) {
	if (p->left != NULL)
		postOrder(p->left);
	if (p->right != NULL)
		postOrder(p->right);

	printf("%d ", p->elem);
}
int main() {
	Node* root = getNode(); 
	root->elem = 1;

	addLeftNode(root, 1, 2);
	addLeftNode(root, 2, 3);
	addRightNode(root, 2, 4);

	addRightNode(root, 1, 5);
	addLeftNode(root, 5, 6);
	addRightNode(root, 5, 7);

	addLeftNode(root, 6, 8);
	addRightNode(root, 6, 9);

	addRightNode(root, 9, 10);
	/*
			1
	  2				5
	3  4		6      7
			  8  9
				  10
	*/
	preOrder(root); printf("\n"); // 1 2 3 4 5 6 8 9 10 7
	inOrder(root); printf("\n"); // 3 2 4 1 8 6 9 10 5 7
	postOrder(root); printf("\n"); // 3 4 2 8 10 9 6 7 5 1
	
	return 0;
}

오일러 투어

루트에서 왼쪽 자식노드 방향으로 출발. 트리의 간선을 항상 왼쪽에 두고 트리를 돌며 순회.

각 노드별로 세 번씩 방문

  • 왼쪽 L : 전위순회
  • 아래 B : 중위순회
  • 오른쪽 R : 후위순회
Alg eulerTour(v)
1. visitLeft(v)
2. if(isInternal(v))
     eulerTour(leftChild(v))
3. visitBelow(v)
4. if(isInternal(v))
     eulerTour(rightChild(v))
5. visitRight(v)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct _Node {
	struct _Node* left;
	struct _Node* right;
	int elem;
} Node;

Node* getNode() {
	Node* p = (Node*)malloc(sizeof(Node));
	p->left = NULL;
	p->right = NULL;

	return p;
}

Node* findNodeByElem(Node* p, int elem) {
	if (p->elem == elem)
		return p;

	if (p->left != NULL) {
		Node* left = findNodeByElem(p->left, elem);
		if (left != NULL)
			return left;
	}

	if (p->right != NULL) {
		Node* right = findNodeByElem(p->right, elem);
		if (right != NULL)
			return right;
	}

	return NULL;
}

void addLeftNode(Node* root, int parentElem, int elem) {
	Node* newNode = getNode();
	newNode->elem = elem;

	Node* parent = findNodeByElem(root, parentElem);
	parent->left = newNode;
}

void addRightNode(Node* root, int parentElem, int elem) {
	Node* newNode = getNode();
	newNode->elem = elem;

	Node* parent = findNodeByElem(root, parentElem);
	parent->right = newNode;
}

void preOrder(Node* p) {
	printf("%d ", p->elem);
	if (p->left != NULL)
		preOrder(p->left);
	if (p->right != NULL)
		preOrder(p->right);
}

void inOrder(Node* p) {
	if (p->left != NULL)
		inOrder(p->left);

	printf("%d ", p->elem);

	if (p->right != NULL)
		inOrder(p->right);
}

void postOrder(Node* p) {
	if (p->left != NULL)
		postOrder(p->left);
	if (p->right != NULL)
		postOrder(p->right);

	printf("%d ", p->elem);
}

void eulerTour(Node* p) {
	// visit left
	printf("%d(L) ", p->elem);

	if (p->left != NULL) // ( is internal )
		eulerTour(p->left);

	// visit below
	printf("%d(B) ", p->elem);

	if (p->right != NULL) // ( is internal )
		eulerTour(p->right);

	// visit right
	printf("%d(R) ", p->elem);
}
int main() {
	Node* root = getNode(); 
	root->elem = 1;

	addLeftNode(root, 1, 2);
	addLeftNode(root, 2, 3);
	addRightNode(root, 2, 4);

	addRightNode(root, 1, 5);
	addLeftNode(root, 5, 6);
	addRightNode(root, 5, 7);

	addLeftNode(root, 6, 8);
	addRightNode(root, 6, 9);

	addRightNode(root, 9, 10);
	/*
			1
	  2				5
	3  4		6      7
			  8  9
				  10
	*/
	
	eulerTour(root); 
	// 1(L) 2(L) 3(L) 3(B) 3(R) 2(B) 4(L) 4(B) 4(R) 2(R) 1(B) 5(L) 6(L) 8(L) 8(B) 8(R) 
	// 6(B) 9(L) 9(B) 10(L) 10(B) 10(R) 9(R) 6(R) 5(B) 7(L) 7(B) 7(R) 5(R) 1(R)
	
	return 0;
}

오일러 투어를 통해 어떤 노드 v의 부트리의 크기를 구할 수 있다.
카운터 변수 cnt를 두고 진행한다.

  1. 어떤 노드 v에 대해 visitLeft
    1-1. cnt = cnt + 1
    1-2. 노드v에 현재 cnt값을 저장 (leftCnt)
  2. 다른 노드들에 대해 오일러 투어 진행
  3. 어떤 노드 v로 돌아와 visitRight
    3-1. 노드v에 현재 cnt값을 저장 (rightCnt)
    3-2. 노드v의 부트리의 크기는 rightCnt - leftCnt + 1
int cnt = 0;

void eulerTour(Node* p) {
	// visit left
	cnt++;
	p->leftCnt = cnt;

	if (p->left != NULL) // ( is internal )
		eulerTour(p->left);

	// visit below
	// (no action)

	if (p->right != NULL) // ( is internal )
		eulerTour(p->right);

	// visit right
	printf("%d's subtree size : %d\n", p->elem, cnt - (p->leftCnt) + 1);
}

int main() {
	Node* root = getNode(); 
	root->elem = 1;

	addLeftNode(root, 1, 2);
	addLeftNode(root, 2, 3);
	addRightNode(root, 2, 4);

	addRightNode(root, 1, 5);
	addLeftNode(root, 5, 6);
	addRightNode(root, 5, 7);

	addLeftNode(root, 6, 8);
	addRightNode(root, 6, 9);

	addRightNode(root, 9, 10);
	/*
			1
	  2				5
	3  4		6      7
			  8  9
				  10
	*/
	
	eulerTour(root); 
	/*
	3's subtree size : 1
	4's subtree size : 1
	2's subtree size : 3
	8's subtree size : 1
	10's subtree size : 1
	9's subtree size : 2
	6's subtree size : 4
	7's subtree size : 1
	5's subtree size : 6
	1's subtree size : 10
	*/
	
	return 0;
}

일차원배열 기반 이진트리 구현

n개 노드가 있는 크기 N의 일차원배열로 이진트리를 구현한다.

랭크(인덱스) i>0인 노드에 관해

  • left child의 랭크 = 2*i
  • right child의 랭크 = 2*i + 1
  • parent의 랭크 = ⌊ i/2 ⌋
  • 루트의 랭크 = 1

효율적인 공간사용에 대해

  • 최선의 경우 N = n 이다. (완전이진트리)
  • 최악의 경우 N = 2^n - 1이다. (편향트리)
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>
#define N 20

int tree[N] = { 0 };

void addNode(int parent, int leftElem, int rightElem) {
	// parent인덱스 찾기
	int parentIdx = 0;
	for (int i = 0; i < N; i++) {
		if (tree[i] == parent) {
			parentIdx = i;
			break;
		}
	}

	// 좌우 자식노드 추가
	tree[2 * parentIdx] = leftElem;
	tree[2 * parentIdx + 1] = rightElem;
}

void printTree() {
	for (int i = 0; i < N; i++) {
		printf("%d ", tree[i]);
	}
	printf("\n");
}

void inorderVisit(int idx) {
	if (tree[2 * idx] != 0)
		inorderVisit(2 * idx);

	printf("%d ", tree[idx]);

	if (tree[2 * idx + 1] != 0)
		inorderVisit(2 * idx + 1);
}

int main() {
	tree[1] = 1; // root
	addNode(1, 2, 5);
	addNode(2, 3, 4);
	addNode(5, 6, 7);
	addNode(6, 8, 9);
	/*
			1
	  2				5
	3  4		6      7
			  8  9
	*/

	printTree(); 
	// 0 1 2 5 3 4 6 7 0 0 0 0 8 9 0 0 0 0 0 0
	
	inorderVisit(1);
	// 3 2 4 1 8 6 9 5 7

	return 0;
}

연결 이진트리 (연결리스트 기반 이진트리)

노드 저장내용

  • 원소
  • 부모노드
  • 왼쪽 자식노드
  • 오른쪽 자식노드

계승자

  • 계승자 : 이진트리를 순회할 때, 어떤 노드 직후에 방문하는 노드

아래 코드는 내부노드가 좌우자식을 모두 가진다고 가정한다.

Alg preorderSucc()
1. if(isInternal(v))
     return leftChild(v)
2. p ← parent(v)
3. while(leftChild(p) != v)
     if(isRoot(v)) {이 조건에 걸리려면, v가 마지막 순회순서의 노드여야한다.}
       invalidNodeException()	
     v ← p
     p ← parent(p)
4. return rightChild(p)

Alg inorderSucc()
1. if(isInternal(v)) { 오른쪽 부트리의 왼쪽끝 노드 반환 }
     v ← rightChild()
     while(isInternal(v))
       v ← leftChild()
     return v
2. p ← parent
3. while(leftChild(p) != v) { 다음에 출력할 내부노드 찾기 }
     if(isRoot(v))
       invalidNodeException()
     v ← p
     p ← parent(p)
4. return p

Alg postorderSucc()
1. if(isRoot(v))
     invalidNodeException() { 후위순회에서 루트 다음 방문할 노드는 없다 }
2. p ← parent(p)
3. if(rightChild(p) = v)
     return p
4. v ← rightChild(p)
5. while(isInternal(v)) { 오른쪽 부트리의 왼쪽끝 노드 반환 }
     v ← leftChild(v)
6. return v
Node* preOrderSuccessor(Node* root, Node* v) {
	// 내부노드면 그냥 left 반환
	if (v->left != NULL || v->right != NULL)
		return v->left;

	// 1. 이 노드가 부모 노드의 left였으면 그냥 부모의 right 반환
	// 2. 이 노드가 부모 노드의 right였으면, 아직 출력안한 가장 가까운 right반환
	Node* p = v->parent;
	while (p->left != v) { 
		if (v == root)
			return NULL; // invalid exception
		v = p;
		p = p->parent;
	}

	return p->right;
}

Node* inOrderSuccessor(Node* root, Node* v) {
	// 내부노드면 오른쪽 부트리의 왼쪽 끝 노드 반환
	if (v->left != NULL && v->right != NULL) {
		v = v->right;
		while (v->left != NULL && v->right != NULL)
			v = v->left;
		return v;
	}

	// 외부노드일 때
	// 1. 이 노드가 부모노드의 left였으면, 부모노드 반환
	// 2. 이 노드가 부모노드의 right였으면, 아직 출력안한 가장 가까운 right반환
	Node* p = v->parent;
	while (p->left != v) {
		if (v == root)
			return NULL; // invalid exception
		v = p;
		p = p->parent;
	}

	return p;
}

Node* postOrderSuccessor(Node* root, Node* v) {
	if (v == root)
		return NULL; // invalid exception

	Node* p = v->parent;

	// 1. 이 노드가 외부노드이고 + 부모노드의 right였으면 ---> 부모노드 반환
	// 2. 이 노드가 내부노드이고 + 부모노드의 right였으면 ---> 부모노드 반환
	if (p->right == v)
		return p;

	// 2-1. 이 노드가 외부노드이고 + 부모노드의 left였으면 ---> 부모노드 오른쪽 부트리의 왼쪽 끝 노드 반환
	// 2-2. 이 노드가 내부노드이면 + 부모노드의 left였으면 ---> 부모노드 오른쪽 부트리의 왼쪽 끝 노드 반환
	v = p->right;
	while (v->left != NULL && v->right != NULL)
		v = v->left;
	return v;
}

int main() {
	Node* root = getNode(); 
	root->elem = 1;

	addLeftNode(root, 1, 2);
	addLeftNode(root, 2, 3);
	addRightNode(root, 2, 4);

	addRightNode(root, 1, 5);
	addLeftNode(root, 5, 6);
	addRightNode(root, 5, 7);

	addLeftNode(root, 4, 8);
	addRightNode(root, 4, 9);
	/*
			1
	  2				5
	3  4		6      7
      8  9
	*/
	
	Node* v1 = findNodeByElem(root, 2);
	Node* v2 = findNodeByElem(root, 4);
	Node* v3 = findNodeByElem(root, 6);
	printf("\t\tv1(%d)\tv2(%d)\tv3(%d)\n", v1->elem, v2->elem, v3->elem);
	printf("pre suc\t\t%d\t%d\t%d\n", preOrderSuccessor(root, v1)->elem, preOrderSuccessor(root, v2)->elem, preOrderSuccessor(root, v3)->elem);
	printf("in suc\t\t%d\t%d\t%d\n", inOrderSuccessor(root, v1)->elem, inOrderSuccessor(root, v2)->elem, inOrderSuccessor(root, v3)->elem);
	printf("post suc\t%d\t%d\t%d\n", postOrderSuccessor(root, v1)->elem, postOrderSuccessor(root, v2)->elem, postOrderSuccessor(root, v3)->elem);
	/*
					v1(2)		v2(4)		v3(6)
	pre suc			3			8			7
	in suc			8			9			5
	post suc		6			2			7
	*/

	return 0;
}

결정트리

의사결정 과정을 묘사한 이진트리

  • 내부노드 : 질문(yes/no 응답에 따라 하위질문 또는 결정으로 연결)
  • 외부노드 : 결정
profile
LeeWonjin
노는게 제일 좋습니다.
이전 포스트

자료구조 09 : 큐

다음 포스트

자료구조 11 : 분리집합

0개의 댓글