1. Tree 기본 개념들
2. Binary Tree
3. Binray Tree 의 표현
4. Binary Tree Traversal
5. Binary Search Trees (우리말로 이진 탐색 트리)
6. Insert x
7. Delete x(요건 쪼금 복잡함)
8. Tree에 관련된 연산 몇가지(Cross Reference 할때 했던거 약간 변형시켰음. C++식으로는 나중에-.-)

1. Tree 기본 개념들 ¶

Node : 노드
Root : 맨 꼭대기 노드
Edge : 노드와 노드를 이어주는 선
Degree : 노드에 딸려있는 Edge의 수
Parent : 부모 노드
Child : 자식 노드
Level : 몇층?
Sibling : 형제(같은 레벨의) 노드
Height : Maximum Level

2. Binary Tree ¶

자식은 0 - 2개
왼쪽 자식, 오른쪽 자식 구별
깊이 k의 최대 노드수 = 2^k - 1
레벨 i의 최대 노드수 = 2^(i-1)
n0을 잎사귀 노드의 갯수, n2를 Degree가 2인 노드의 갯수라고 하면 n0 = n2 + 1 이라는 공식이 성립한다.

3. Binray Tree 의 표현 ¶

배열
- 그냥 차례대로 집어넣는다. 루트, 왼쪽 자식, 오른쪽 자식의 순으로.. 비어있는건 쌩깐다.
- 인덱스 접근할때는
  - Left Child : 인덱스 * 2
  - Right Child : 인덱스 * 2 + 1
  - Parent : 인덱스/2 -> 내림
Linked List
- 노드에는 데이터와 왼쪽 자식을 가리키는 링크, 오른쪽 자식을 가리키는 링크로 구성된다.

4. Binary Tree Traversal ¶

PreOrder : Root -> Left Child -> Right Child : 컴파일러가 가장 좋아하는 방식

~cpp 
PreOrder(a) 
{
    if(a)
    {
        visit a
        Preorder(a->left)
        Preorder(a->right)
    }
}

InOrder : Left Child -> Root -> Right Child : 우리에게 가장 익숙한 방식

~cpp 
InOrder(a) 
{
    if(a)
    {
        InOrder(a->left)
        visit a
        InOrder(a->right)
    }
}

PostOrder : Left Child -> Right Child -> Root

~cpp 
PostOrder(a) 
{
    if(a)
    {
        PostOrder(a->left)
        PostOrder(a->right)
        visit a
    }
}

LevelOrder : 레벨 순으로 방문

~cpp 
AddQ(Root)
while(1)
{
    a = DeleteQ();
    Visit a;
    if(!a) break;
    if(a->left) AddQ(a->left)
    if(a->right) AddQ(a->right)
}

5. Binary Search Trees (우리말로 이진 탐색 트리) ¶

일반적으로 정렬되어 있는 배열에서 가장 빠른 탐색을 자랑하는 알고리즘으로 알려져 있답니다.(맞나?--;)
- 일반 탐색 : θ(n)
- 이진 탐색 : θ(log2 n) - 2는 밑입니다. 첨자 표현하는법 아시는분?--;
- n이 한 2048정도 된다고 하면 일반 탐색은 2048이 걸리는 반면 이진 탐색은 11밖에 안걸린다는 말이져
- but, 정렬되어 있지 않으면 이진 탐색 나무든 뭐든 안됩니다. 안나온단 말입니다. 중간에 꼬이는데 무슨..--;
조건
- Binray Search Tree 니까 당연히 Binary Tree 여야 한다.
- Keys in Left Subtree < Keys of Node
- Keys in Right Subtree > Keys of Node(고로 순서대로 정렬되어 있어야 한단 말입니다.)
알고리즘
- Search x => Compare with Root
  - if x = Root's Key then 찾았으니까 알고리즘 끝
  - else if x > Root's Key Root를 Right Subtree의 Root로 셋팅. 거기서부터 검색 다시 시작
  - else if x < Root's Key Root를 Left Subtree의 Root로 셋팅. 거기서부터 검색 다시 시작

6. Insert x ¶

루트로부터 크기에 맞춰 왼쪽 또는 오른쪽으로 돌아댕기다가 맞는 부분에 추가시켜주면 된다.

7. Delete x(요건 쪼금 복잡함) ¶

Search x
- 만약 x가 leaf(맨 끝 노드) - 그냥 지우면 되지 뭐..--;
- x의 Child가 1개 있을 경우 - 그 노드 지우고 그 자식들을 다 위로 올린다. 고로 할아버지의 자식이 된다는 것이다.(뭔가 좀 이상?--;)
- x의 Child가 2개 있을 경우 - 그 노드의 Left Subtree에서 가장 큰 값을 찾는다. 이값을 y라고 하면 y는 오른쪽 Child가 없다. y를 x자리에 갖다 놓고 여기서 다시
  - y가 Child 없으면 - 그냥 지운다.
  - y가 Child 있으면 - 그 밑의 노드들을 한단계 위로.. 고로 할아버지의 자식

8. Tree에 관련된 연산 몇가지(Cross Reference 할때 했던거 약간 변형시켰음. C++식으로는 나중에-.-) ¶

~cpp 
// 트리에 관한 함수들

void init(Node** node,char* ch)			// 초기화
{
	(*node)->pLeft = (*node)->pRight = NULL;	// 왼쪽 오른쪽 자식 NULL로
	(*node)->Data = new char[strlen(ch) + 1];	// 문자열 길이만큼 할당
	strcpy((*node)->Data,ch);			// 노드에 문자열 복사
}

void PrintandDelete(Node* root)			// 맨 왼쪽부터 순회(Preorder인가?)
{
    if( root->pLeft )		
        Print( root->pLeft );

    cout << root->Data << endl;

    if( root->pRight )
        Print( root->pRight );

    delete root;					// 할당된 노드 제거
}

int Add(Node** root,char* ch)
{
    if(!(*root))					// 아무것도 없을때
    {
        *root = new Node;				// 할당
        init(root,ch);		   	         // 초기화
        return 1;
    }
	
    else if(strcmp((*root)->Data,ch)>0)		// 부모가 자식보다 크면 왼쪽에 추가
	return add(&((*root)->pLeft),ch);
    else if(strcmp((*root)->Data,ch)<0)		// 부모가 자식보다 작으면 오른쪽에 추가
	return add(&((*root)->pRight),ch);
    else if(strcmp((*root)->Data,ch)==0)		// 같으면 카운터 증가
	return 1;
}

DataStructure

Contents

1. Tree 기본 개념들 ¶

2. Binary Tree ¶

3. Binray Tree 의 표현 ¶

4. Binary Tree Traversal ¶

5. Binary Search Trees (우리말로 이진 탐색 트리) ¶

6. Insert x ¶

7. Delete x(요건 쪼금 복잡함) ¶

8. Tree에 관련된 연산 몇가지(Cross Reference 할때 했던거 약간 변형시켰음. C++식으로는 나중에-.-) ¶