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
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;
}
