대엉코딩

1. 트리[Tree] 란?

- computer science에서 계층구조(hierarchical structure)를 가진 추상자료형

- 트리는 노드로 구성되어 있는데, 노드들은 부모-자식 (parent-child)관계를 가진다.

- 직장에서 부장-과장(1,2,3)-(대리1,2,3,4,5,6) 이 업무연관성에 따라 그려진 조직도를 떠올려보면 좋다.

- File System, Programming enviroment 등에서 사용된다.

2. 용어(Terminology)

- Root (node) : parent가 없는 노드

- Internal node : 적어도(at least) 자식을 하나이상 가지는 노드

- External node : 자식이 없는 노드

- Ancestors of a node(a) : node(a)의 parent,grand parent, grand-grandparent........etc

- Depth of a node(a) : number of ancestors (조상노드의 수)

- Height of a tree(a) : maximum depth of any node (가장 큰 깊이를 가진 노드의 깊이가 트리의 높이)

- Descendant of a node : child, grandchild, ..... etc

3. Method

-기본적인 methods 

-(1) Generic methods

     - int size()

     - bool empty()

-(2) Accessor methods

     - position root()

     - listh<position> positions()

-(3) Position-based methods

     - position parent()

     - list<position> children

-(4) Query methods

     - bool isRoot()

     - bool isExternal()

4. 탐색(순회)

- 트리 자료구조를 탐색하는 방법은 많지만 여기서는 기본적인 2개만 다루겠다.

-(1) 전위순회

     - descendants들을 방문하기 전에 자신의 노드부터 방문처리 하는 것이다.

-(2) 후위순회

     - descendants를 먼저 방문하고 자신을 마지막에 방문처리하는 것이다.

* 이진 탐색 트리?

 - 검색에 많이 사용이 되는 형태입니다.

 - 중위 순회 (Inordered traversal)를 할 경우 key값에 따라 sorting된 결과를 얻을 수 있습니다.

    # 구조 조건

     - 각 노드들은 자식노드를 기껏해야 두 개만을 가질 수 있습니다.

    # 순서 조건

     - 각 노드들의 왼쪽 서브트리에 있는 노드들은 각 노드보다 작은 값을 가집니다.(key)

     - 각 노드들의 오른쪽 서브트리에 있는 노드들은 각 노드보다 큰 값을 가집니다.(key)

    # 중위 순회

구조 조건과 순서 조건을 만족하는 이진탐색트리를 구성(construct) 하였다면

위와 같이 inordered traversal을 하면 key값을 기준으로 정렬이 됩니다.

(30,40,50,55,60,70)

 * 탐색연산(search)

 - root 노드 부터 시작하여 탐색하고자 하는 값 n 과 비교를 하며

   비교하는 노드보다 n값이 작다면 왼쪽 서브트리로 가서 왼쪽 서브트리의 루트노드와 다시 비교.

   비교하는 노드보다 n값이 크다면 오른쪽 서브트리로 가서 오른쪽 서브트리의 루트노드와 다시비교를 하면 됩니다.

* 삽입연산(insert)

 - 삽입연산은 탐색연산과 같이 내려가다가 자기 자리를 찾아서 들어가면 됩니다

 - 위의 저의 예시는 나름 예쁜? 모양이지만 이진탐색트리의 구조 조건과 순서 조건만 만족 하면서 구성해 나가면됩니다.

 - 같은 노드들의 값과 수 여도 다양한 모양의 이진탐색트리가 나올 수 있습니다.

 - 역시나 이와 같은 경우에도 순서와 구조 조건이 모두 맞습니다 --> 중위순회를 하여도 결과가 그대로 나옵니다.

 * 삭제연산(delete)

 - 이진탐색트리는 어떠한 노드를 삭제연산을 수행하여 제거 하여도 그 결과의 트리 역시 이진탐색트리여야 합니다.

    (당연하죠? ㅎ)

 - 두 경우로 나누어서 보겠습니다.

    1.) 삭제하려는 노드의 두 자식노드가 leaf노드인 경우입니다. --->그냥 삭제해버리면 됩니다.

    2.) 삭제하려는 노드의 자식이 하나는 leaf노드이고 한쪽은 서브트리(노드)를 가지는 경우

       - 삭제하려는 노드의 자리에 한쪽 서브트리를 연결 해주면 됩니다.

    3.) 두 자식이 모두 leaf노드가 아닌 값을 가진 노드 들( 즉, 두개의 서브트리를 가지는) 일 경우

        -- 본 예에서 60을 삭제 하고자 한다고 가정 하겠습니다. delete(40)

        -- 위의 예에서 보고 이렇게 하면되지 , 쉽게 보일 수 있지만 아래의 예를 보면 약간은 생각보다 복잡합니다.

        -- 두가지 방법이 있습니다(succesor를 삭제노드위치에 위치, predecessor을 삭제 노드 위치에 위치)

           더 금방 찾을 수 있는 (왼쪽 서브트리의 첫번째 노드) succesor를 이용합시다.

        -- succesor를 찾아서 삭제하려는 노드의 위치에 위치 시키고 부모노드와

        -- 삭제한 노드의 subtree들과 successor를 연결 시켜 주시면 됩니다.

        -- 위와 같이 삭제 연산을 수행 한 뒤에도 이진탐색트리가 나오게 되었습니다.

 * 성능분석

 - search, insert, delete (탐색, 삽입, 삭제) 연산 모두 O(n) 입니다.

 - worst case는 편향된(즉, 한쪽으로만 쭉쭉 뻗어있는 ) 트리입니다. 

 - tree에서의 연산들은 tree의 depth와 연관이 되어있는데 이럴경우 depth가 n(n-1) 이기 때문입니다.

 - average case의 경우 O(log n) 인데 worst case도 O(log n ) 을 맞추고 싶을 경우

 - depth를 맞추어주기 위해서 어느정도 균형이 잡혀 있는(예뿌장한?) 트리를 만들어 주어야 합니다.

 - 대표적인 균형이진트리들은 AVL TREE, RED-BLACK TREE 등이 있습니다.

https://www.acmicpc.net/problem/1316

- 문자열을 탐색 하는 문제입니다.

- 딱히 어려운 문제는 아니고

- 단어를 차례대로 문자 하나씩 탐색 하던중 같은 문자를 받다가 다른 문자가 처음 나타날 경우

- 그 단어가 이전에 들어온적이 있는 단어 인지 처음 들어온 단어 인지만 체크 하면 되는 문제입니다.

- 들어왔던 단어들을 벡터에 저장해 두었다가 새로운 문자가 들어올 때 그 벡터들을 탐색하여 들어온적이 있었는지를

-확인 하였습니다.

<코드>

https://www.acmicpc.net/problem/1966

큐를 이용한 문제입니다.

문제조건은 상세하게 나와있는 편입니다.

다만 입력조건 중 말이 헷갈리는 부분이 나와서 이는 필기노트에 제가 이해하기 쉬운 말로 바꾸어 놓았습니다.

그리고 queue는 순회가 안되므로( for문을 이용하여 배열처럼 쉽게 탐색이 안됨)

어떻게 할까 생각을 하다가 중요도를 따로 담은 vector를 소팅을 시키고

현재 중요도를 가리키는 변수 n을 선언하여 가장 높은 중요도를 가진 문서가 queue에서 pop()

되어 프린트가 되면 n을 1증가시켜 두번쨰 높은 중요도를 가리키게끔 하였습니다.

필기노트를 보시면 이해가 빠르리라 생각합니다.

다른분들은 어떻게 푸셨는지 모르겠네요. 한번 찾아봐야겠네요!.

<필기>

<코드>