U E D R , A S I H C RSS

Data Structure/Tree


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



Valid XHTML 1.0! Valid CSS! powered by MoniWiki
last modified 2021-02-07 05:23:05
Processing time 0.0120 sec