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++ì‹�으로는 나중ì—�-.-)
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 -> 내림
- Left Child : ��스 * 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, ì •ë ¬ë�˜ì–´ 있지 않으면 ì�´ì§„ íƒ�색 ë‚˜ë¬´ë“ ë�ë“ ì•ˆë�©ë‹ˆë‹¤. 안나온단 ë§�입니다. 중간ì—� 꼬ì�´ëŠ”ë�° 무슨..--;
- �반 �색 : θ(n)
- ì¡°ê±´
- Binray Search Tree 니까 당연히 Binary Tree 여야 한다.
- Keys in Left Subtree < Keys of Node
- Keys in Right Subtree > Keys of Node(ê³ ë¡œ 순서대로 ì •ë ¬ë�˜ì–´ 있어야 한단 ë§�입니다.)
- Binray Search Tree 니까 당연히 Binary Tree 여야 한다.
- ì•Œê³ ë¦¬ì¦˜
- 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로 셋팅. 거기서부터 검색 다시 시작
- if x = Root's Key then 찾았으니까 ì•Œê³ ë¦¬ì¦˜ ë��
- Search x => Compare with 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 있으면 - ê·¸ ë°‘ì�˜ 노드들ì�„ 한단계 위로.. ê³ ë¡œ í• ì•„ë²„ì§€ì�˜ ìž�ì‹�
- y가 Child 없으면 - 그냥 지운다.
- 만약 xê°€ leaf(맨 ë�� 노드) - 그냥 지우면 ë�˜ì§€ ë�..--;
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;
}










