10/22/2016

Tree (data structure)

1. Tree의 일반적인개념

  • Tree 구성 
Tree의 기본구성은 Parent node에 child node로 연결된 추상적인 자료구조로
Tree의 element는 Node이며 Tree의 선을 branch라고 말한다.
그리고, 마지막 Node , 즉 Child node가 없는 leaf node , end-node 라고 부른다.

좀 더 자세히 설명을 하게되면, Graph와 동일하게 표시도 가능하겠지만,
Tree는 방향성과 계층의 속성을 가지고 있기에 이를 분리하여 표시한다.

  • Tree의 종류 
Tree는 종류 다중 Tree와 2진 Tree로 구분 할 수 있겠다.
일반적으로 2진 트리, Binary Tree를 많이 사용한다.

  • Tree의 재귀(Recursion)
Tree에서 Recursion (재귀)는 자주 사용이되며, 이는 탐색 (Traversal) 에 용이하다.

  https://en.wikipedia.org/wiki/Tree_(data_structure)
  https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0


1.1 Trie 트라이, MultiTree (다중 트리) 소개

  쉽게 생각하면 탐색기에서 사용하고 있는 디렉토리가 다중 트리이며,
  데이타베이스에서 주로 사용이 된다.
  이 곳에서는 다루지는 않겠다.

  트라이 (Trie)
  https://en.wikipedia.org/wiki/Trie

  https://en.wikipedia.org/wiki/Multitree

  B Tree or B+ Tree
  https://en.wikipedia.org/wiki/B%2B_tree
  https://ko.wikipedia.org/wiki/B_%ED%8A%B8%EB%A6%AC
  https://ko.wikipedia.org/wiki/B%2B_%ED%8A%B8%EB%A6%AC


1.2 Binary Tree 소개
Child Node를 2개로 한정지어 Tree를 구성하도록 하는 트리를 말하며, 일반적으로
많이 사용이 되어진다.

Node 기준 left child 와 right child 존재하며, 상위 처음 Node 를 Root라고 말한다.

구현방법은 Tree 구조체를 이용하는 방법도 있겠지만, Array로도 구현이 가능하다.


2. Binary Tree 구현방법


2.1 Tree 구조체 사용하여 동적구현  

장점: 유지보수 및 삭제의 용이성 , 동적으로 추가 ,삭제가 쉽다.
단점: 구현이 새로운 구조체와 여러 함수를 필요하다보니 좀 복잡하다.


struct Node {
    int data ; // void * data;
    ....          //  다른 Data
    struct Node  *left;
    struct Node  *right;
}

struct Tree {
    int size;
    struct Node *root;        // 전체 root
    struct Node *prenode;  //searching 할때, 현재 node의 root
    ....   // 이밖에 필요한 정보 및 함수 포인터도 삽입가능
}


2.2 Data Array 정적 구현 
이 부분  추후 Heap sort 와 우선 순위 Queue에서 다시 사용하겠다.
  • 장점:  Data Array 가장 쉽게 구현이 가능하다. 
  • 단점:  Node의 삭제가 어렵고, Array Size로 인하여 이미 지속적인 유지보수가 힘들다.  

0은 Root 이며,                 Level 0
1,2  Root의 left , right       Level 1
3,4  1의 left, right             Level 2
5,6  2의 left, right             Level 2

그래서 총 3층의 2진트리로 구성이 가능하며, 이는 구성이 Breath-First Search 개념 유사하다.
다만,


아래 그림은 Array 0부터 시작을 했고, Level도 0부터 시작을 했다


Node 의 수가 Data 존재여부가 아닌 계층(Level)이 많아 질 수록 더 많은 Array를 요구되어진다.

전체 Node 갯수를 구하는 방법은 다음과 같다.

Level       0   1   2    3    4   5
Num       1  , 2 , 4,   8 , 16,  32  

이곳에 간단한 규칙이 존재하고 있으며, 예를 Level 4의 Node는 16 이고, 그 이전 Node 합은 (1+2+4+8)=15,
즉 현재 Node -1 은 이전 Node의 합과 동일하다. 그러므로 다음 Node -1하게 되면 된다.

i = Node의 Level      

  • Number of Node = 2^(i+1) -1 ,   N 은 Tree의  Level의 수 
  • Left Node          = 2i+1
  • Right Node        = 2i+2
  • Parent Node       = (i-1)/2 

  https://en.wikipedia.org/wiki/Binary_tree
  https://en.wikipedia.org/wiki/Binary_search_algorithm


3. Binary Tree 일반기능 

  • Searching 
  1. key 값이 동일하면, 현재 Node ,
  2. key <  현재 node.key 작을 경우, left  진입
  3. key  > 현재 node.key 클 경우    right 진입   
  • Insertion
  1. Node가 Empty일 경우, 마지막 Node일 경우, 삽입 
  2. key <  현재 node.key 작을 경우 , left   진입 
  3. key  > 현재 node.key  클   경우 , right 진입 
    Search와 동일하지만, 삽입기능만 추가.
  • Deletion
    기본은 위의 Searching 으로 동일하게 삭제할 Node를 찾는다.
    Node를 삭제 할경우 세가지 사항을 고려한다.
    one child는 left node or right node를 말하며, sub-left-tree or sub-right-tree도 가능

    1. 삭제할 node가 단말 , no child 일 경우
        1. Searching 통하여 삭제할 Node Data 찾음
        2. 문제없이 삭제 가능

    2. 삭제할 node가 one child 일 경우
        1. Searching 통하여 삭제할 node를  data 찾음
        2. 삭제할 node의 삭제이전 node를 저장
        3. 삭제할 node는 link를 끊고 삭제
        4. 삭제이전 node에 child node 연결
               
    3. 삭제할 node가 two child 일 경우
        1. Searching 통하여 삭제할 node를 data 찾음
        2. 삭제할 node의 삭제이전 node를 저장
        3. 삭제할 node 값과 유사한 값을 찾음 (둘 중 선택 A or B)
            A. left-sub tree에서 가장 큰 값의 node 를 찾아 선택
            B. right-sub tree에서 가장 작은 값의 node 를 찾아 선택

        4.1 위의 선택된 node가 last node 일 경우 (no child)
            A. 삭제이전 node에 선택된 node 연결
            B. 선택된 node에 삭제할 node left,right 연결
            C. 삭제할 node 삭제                      .

        4.2 위의 선택된 node가 sub-tree 일 경우 (sub-tree root)
            A. 삭제이전 node에 선택된 node를 연결
            B. 삭제할 node를 삭제
            이 경우는 one child sub-tree 구조이기에 상위 2번째 방법과 동일 **
           
      **주석
      Binary Search Tree 구조상  아래의 구조밖에 될 수 밖에 없다.
        A에서 가장 큰   값은  sub-tree node일 경우  right child 없다.
        B에서 가장 작은 값은 sub-tree node 일 경우  left  child 없다.

  아래의 그림을 참조 이해하기 쉽다.
  http://www.algolist.net/Data_structures/Binary_search_tree/Removal
  http://stackoverflow.com/questions/8292661/how-to-delete-a-node-with-2-children-nodes-in-a-binary-search-tree

  • Traversal
Search와 Traversal 다르며, 기존에 존재하는 Data에 방문하는 순서를
어떻게 정하는지를 결정한다.    

     1. Depth-first Search (DFS, 깊이 우선 탐색)
    1. pre-order  : 처음에 방문하면 pre-order
    2. in-order    : 중간에 방문하면 in-order  : BST Tree에서 사용 
    3. post-order : 나중에 방문하면 post-order 

 
           A. Pre-order
    1. Visit current Node and Get Data 
    2. Traverse the left subtree by recursively 
    3. Traverse the right subtree by recursively 

           B. In-order
           일반적인 Binary Search Tree에서 많이 사용한다.
           왜냐하면, 최소값 부터 정렬이 가능하다.
    1. Traverse the left subtree by recursively 
    2. Visit current Node and Get Data 
    3. Traverse the right subtree by recursively 
           C. Post-order          
    1. Traverse the left subtree by recursively 
    2. Traverse the right subtree by recursively 
    3. Visit current Node and Get Data 


  https://en.wikipedia.org/wiki/Depth-first_search
                      
     2. Breadth-first search (BFS, 너비 우선 탐색)
    1. Level order
      1. Queue에 방문할 Node를 넣는다. 
      2. 방문할 Node를 Queue에서 얻는다. 
      3. Left 방문하고   Child Node가 있을 경우 이를 Queue에 삽입.
      4. Right 방문하고 Child Node가 있을 경우 이를 Queue에 삽입.
      5. Queue Empty가 될때까지 2번을 반복 
  https://en.wikipedia.org/wiki/Breadth-first_search

  Binary Traversal


  Binary Search Tree 
  https://en.wikipedia.org/wiki/Binary_search_tree
  http://robodream.tistory.com/181
  http://web.skhu.ac.kr/~cyberci/program/view/view_13.htm

댓글 없음 :