데이터 구조 12 (힙 추가 연산 , Binary Search Tree)

            Sum

알고리즘 (Recursive 로 구현)

Overall : root 를 입력받아 그 이하 n개의 원소의 값을 합함.

 

1) 입력받은 root 가 empty면 (=원소 개수(n)보다 root가 크면)

   return 0;

 

2) empty가 아니면,

     return(root 값 + 왼쪽 subtree합 + 오른쪽 subtree합)

 

---

 

Delete_node_by_name

우선

1. 힙 노드의 개수를 맞추는 함수

2. 찾아서 삭제하는 함수

3. 다시 tree의 구조를 조정하는 함수

 

 

1. 힙 노드의 개수를 맞추는 함수 (입력은 tname을 받음)

 

    1) 노드가 없으면 => csize==0 이면 return 0;

   

     2)하나를 삭제하면 노드 개수 하나 -1   

            if(  찾아서 삭제하는 함수 ==1) csize --; return 1;

                                                     ==0 이면 return 0;

 

2. 찾아서 삭제하는 함수(입력은 배열,troot,tname,n(인덱싱 용)

1)입력받은 troot 가 n보다 크면 ( 노드 갯수보다 입력받은 root 인덱스 값이 크면) return 0;

2)입력받은 troot 가 찾는 node(tname의 node)면

     2-1) 현재 위치 원소와 끝 원소를 교환 ( complete 구조 맞추기 위해서 )

     2-2) n값 1 감소

     2-3) 현위치에서 parent 방향으로 root까지 해당 원소를 기준으로 adjust연산 수행

 3) root가 찾는 원소가 아니면

    left subtree에서 작업 수행 -> 결과가 1이면 return 1

    left에서도 안 끝났으면 right subtree에서 동일 작업 수행하고

   그 결과를 return

 

 

---

Binary Search Trees

 

원소 찾기(탐색)에 최적화 되어있음

→ 한 번 수행할 때마다 검색 대상이 절반이 됨 = O(log n ) << 최상의 상태일 때 / 아니면 O(n)

 

구조 (조건) : parent의 왼쪽 key값 < parent의 key값  => left subtree에 속한 모든 node의 값은 root의 값보다 작다.

                     parent의 오른쪽 key값 > parent의 key값  => right subtree에 속한 모든 node의 값은 root의 값보다 크다.

 

 알고리즘 

1) 주어진 tree(root)가 empty면 검색 실패 처리

2) root의 key값이 k면, root의 data값 return

3) root의 key값보다 k가 작으면(root>k), left subtree 에서 찾은 결과를 return

4) root의 key값이 k보다 크면 (root<k) , right subtree 에서 찾은 결과를 return

 

---

Insert_node

 

이건 지우개 없이 할 수 있는 거임

해당 parent 보다 크면 오른쪽, 아니면 왼쪽인 걸 잘 생각하면서 넣기

이거 시험에 잘 내는데 많이 틀린다고 함

 

skewed tree일 때, O(n) 나옴

 

---

Delete_node

 

알고리즘

※ 삭제 할 노드의 조건에 따라 다름

1) Treminal node이면 ( leaf면)

그 노드 parent의 해당 노드에 대한 link 를 NULL로 변경

 

2) Degree가 1인 node이면 

해당 노드의 parent -> 해당 노드의 child 로 링크 변경

 

3) Degree가 2인 node이면

해당 노드를,

해당 노드의 왼쪽 subtree의 가장 오른쪽 가장 아래 노드 

                or 오른쪽 subtree의 가장 왼쪽 가장 아래 노드를 그 자리에 갖다 놓는다.

우선 예를 다 들어보자

1) treminal node 일 때로 예를 들어보면

8을 지운다고 할 때, 11(parent)의 node의 (left)link를 NULL로 바꾼다.

 

2) degree 1일 때,

11을 지운다고 하면, 15(parent) 의 link를 8(child)로 연결

 

3) degree 2일 때,

15를 지운다고 하면, left subtree에서 가장 큰 놈인 11을 15자리로 데려와도 됨

혹은 right에서 가장 작은 17을 15자리로 데려와도 된다.

 

Binary Search Tree의 inorder traversal은 sorted배열이기 때문에

삭제할 땐 inorder에서 인접한 것들끼리 대체해준다.

 

ppt29번에 13페이지) 혹은 주로 나오는 constructor 처음 콜할 땐, 그 construtor 멤버 변수들을 초기화 해줌

ex) bst_tree(); => csize=0; / root->NULL

 

---

Search

알고리즘 : 찾는 값 k

1) 주어진 tree(root)가 empty면 실패.

2) Root의 key값이 k이면 , root의 data값 retrurn

3) Root의 key값보다 k가 작으면 , left subtree에서 찾은 결과 return

4) Root의 key값보다 k가 크면 , right subtree에서 찾은 결과 return

 

구현:   끝나는 조건은 찾았을 때 혹은 NULL을 만났을 때

노드타입 검색 함수 (t_id)

   노드타입 *p;

    p = root; 

   root가 NULL이면{

          노드 하나 만들어서 거기에 값 없다고 적은 뒤에 그거 return

}

                               (이러는 이유: 노드타입이 리턴되어야 해서)

 

while(1){

       if(p->id ==t_id) 

       return (*p);

       if(p->id <t_id)                      // t_id 가 더 커서 오른쪽으로 가려고 하는데

               if(p->right ==NULL)        // 오른쪽이 NULL이면

                  노드 하나 만들어서 거기에 값 없다고 적은 뒤에 그거 return

               else  p=p->right              // NULL이 아니면 오른쪽으로 전진

      

       else  // t_id가 더 작을 때,

               if(p->left ==NULL)        // 왼쪽이 NULL이면

                  노드 하나 만들어서 거기에 값 없다고 적은 뒤에 그거 return

               else  p=p->left              // NULL이 아니면 왼쪽으로 전진

 

 

---

Insert

 

알고리즘

1) 주어진 key값이 될 위치를 찾는다

2) node를 만들어서 값을 넣고, 그 위치에 연결

 

 

구현 : 구현할 때 조심해야하는 건 NULL까지 가는 게 아니라 노드 -> NULL 일 때를 찾아서 넣어야 함

void 노드 삽입(node t)

노드 타입 *p      //위치 찾는 용도

노드 타입 *tmp  //데이터 담아두는 용도

 

tmp = new 노드;

*tmp = t;

tmp -> left = NULL;

tmp -> right = NULL;

 

if(root==NULL) //원소가 없으면

root = tmp ; //root는 tmp가 됨

return

}

 

p=root //루트부터 자리 검색 한다.

while(1){

 

if(p->id ==t.id) //  현재 p가 가리키는 노드의 id = 입력받은 id 일 때,

       " 이미 있음. 실패 " 출력  //binary search tree는 같은 게 없다는 조건이니까

 

if(p->id < t.id) // 현재 p가 가리키는 노드의 id < 입력받은 id 일 때, 오른쪽을 봐야함

    if(p->right ==NULL) //오른쪽이 비었다?

          p->right = tmp;

    else //안 비었다?

        p=p->right;

 

else //   현재 p가 가리키는 노드의 id > 입력받은 id 일 때, 왼쪽을 봐야함

      if(p->left ==NULL)

           p->left =temp 

              return;

       else

            p=p->left;

 

 

 

 

 

한동대학교 김호준교수님- 데이터구조 ppt