AndroidTeacher

해시 테이블​

해시 테이블이란 연관배열 구조를 이용하여 (Key, Value)로 데이터를 저장하는 자료구조로,

빠르게 데이터를 검색할 수 있는 자료구조이다.

기본 연산으로는 탐색, 삽입, 삭제가 있다.

해시 테이블 연산​

① 삽입​

해시 테이블에서 자료를 저장하기 위해서는 해시 함수(Hash Function)를 통하여

키(Key)를 -> 해시(Hash)로 변경해야 한다.

위 사진의 해시 함수는 input key를 7로 나눈 나머지이므로

첫 번째 데이터의 키는 76, 해시는 6이 된다.

미리 준비해놓은 0 ~ 6의 저장소 중에 맞는 해시값을 찾아 해당 값을 저장한다.

해시 함수로 해시를 얻어내는 과정에서 서로 다른 key 값이 같은 hash로 변환되는 문제가 발생할 수 있는데

이를 해시 충돌이라고 하며 이 문제를 해결해야 한다.

(해결 방법은 아래에서 소개한다.)

해시테이블 삽입단계의 시간복잡도는 O(1)이다.

유일한 키를 해시함수의 결과로 해시와 키를 저장소에 넣으면 되기 때문이다.

하지만 모든 bucket에서 충돌이 일어날 경우, 최악의 경우 O(n)이 될 수 있다.

② 삭제​

저장되어 있는 값을 삭제할 때는 해당 key와 매칭되는 값을 찾아서 삭제하면 된다.

삭제도 마찬가지로 시간복잡도는 O(1)이다.

유일한 키 값을 해시함수의 결과로 나온 해시에 매칭되는 값을 삭제하면 되기 때문이다.

하지만 모든 bucket에서 충돌이 일어날 경우, 최악의 경우로 O(n)이 될 수 있다.

③ 탐색​

키로 값을 찾아내는 과정으로, 삭제 연산과 과정이 비슷하다.

1. 키로 hash를 구한다.
2. hash로 키를 구한다.

저장단계의 시간복잡도도 마찬가지로 O(1)이다.

유일한 키 값을 해시함수의 결과로 나온 해시에 매칭되는 값을 찾으면 되기 때문이다.

하지만 모든 bucket에서 충돌이 일어날 경우, 최악의 경우로 O(n)이 될 수 있다.

해시 충돌​

해시테이블은 세가지 연산 과정에서 모두 평균적으로 O(1)의 시간복잡도를 가지기 때문에

자료구조의 효율성 측면에서 좋은 자료구조라고 볼 수 있다.

하지만 발생할 수 있는 문제는 바로 해시 충돌이다.

해시 충돌을 해결하기 위한 방법은 크게 2가지가 있다.

① 체이닝(Chaining)​

위에 사진에서 Sandra Dee가 삽입하는데, John Smith과 충돌이 일어나게 된다.

그럴때 John Smith의 뒤에 Sandra Dee를 연결시키는 방법이 바로 체이닝 기법이다.

※ 체이닝의 장점

1. 한정된 저장소를 효율적으로 사용 가능하다.
2. 해시 함수를 선택하는 중요성이 상대적으로 적다.
3. 상대적으로 적은 메모리를 사용한다. (미리 공간 잡을 필요X)

※ 체이닝의 단점

1. 한 Hash에 자료들이 계속 연결된다면(쏠림현상) 검색 효율이 낮아진다.
2. 외부 저장 공간을 사용한다.
3. 외부 저장 공간 작업을 추가로 해야한다.

체이닝의 시간복잡도

테이블의 저장소 길이를 n, 키의 수를 m이라고 했을 때,

평균적으로 저장소에서 1개의 hash당 m/n개의 키가 들어있다. 이를 α라고 하자.

삽입연산​

충돌이 일어났을 때, 해시가 가진 연결리스트의 Head에 자료를 저장할 경우, O(1)의 시간복잡도를 가진다.

하지만 Tail에 자료를 저장할 경우, O(α)의 시간 복잡도를 가진다.

한개의 해시에 모든 자료가 연결되어있는 최악의 경우, O(n)의 시간복잡도를 가진다.

삭제연산 & 탐색연산​

산출된 Hash의 연결리스트를 차례대로 살펴보아야 하므로 O(α)의 시간 복잡도를 가진다.

한 개의 해시에 모든 자료가 연결되어 있는 최악의 경우 O(n)의 시간복잡도를 가진다.

② 개방주소법(Open Addressing)​

개방주소법은 비어있는 해시를 찾아 해시를 변경하여 데이터를 저장하는 기법이다.

위 사진에서 Sandra Dee가 삽입될 때 해시가 John Smith로 이미 채워져 있다.

그렇게 되면 바로 다음 빈 Hash에 Sandra를 저장한다.

그 다음 Ted Baker의 해시도 Sandra Dee가 저장되어 있기 때문에

그 다음 빈 해시에 Ted를 저장한다.

바로 다음 빈 해시에 저장하는 것은 한 예시이며,

비어있는 해시를 찾는 규칙은 총 3가지가 존재한다.

1. 선형 탐색(Linear Probing): 다음 해시나 n개를 건너뛰어 비어있는 해시 에 데이터를 저장
2. ​제곱 탐색(Quadratic Probing): 충돌이 일어난 해시의 제곱을 한 해시 에 데이터를 저장
3. 이중 해시(Double Hashing): 다른 해시함수를 한번 더 적용한 해시 에 데이터를 저장

​​※ 개방주소법의 장점

1. 또 다른 저장공간 없이 해시테이블 내에 데이터 저장 및 처리 가능
2. 또 다른 저장공간에서의 추가적인 작업 없음

​​※ 개방주소법의 단점

1. 해시 함수의 성능에 전체 해시테이블의 성능이 갈림
2. 데이터의 길이가 늘어나면 그에 해당하는 저장소를 마련해야함

개방주소법의 시간복잡도​

삽입, 삭제, 검색 모두 해시함수를 통해 얻은 Hash가 비어있지 않으면 다음 버킷을 찾아가야 한다.

그러므로 찾아가는 횟수가 많아질수록, 시간 복잡도가 증가하게 된다.

따라서, 최상의 경우 O(1)이며 최악의 경우 O(n)이다.

결국, 개방주소법에서는 비어있는 공간을 확보하는 것이 필요하다.

(저장소가 어느 정도 채워지면 저장소의 사이즈를 늘려주어야 한다.)

해시 테이블의 단점​

• 순서가 있는 배열에 어울리지 않음
• 공간 효율성이 떨어짐
• Hash Function(해시 함수)의 의존도가 높음

레드-블랙 트리 (Red-black tree) 란 ?​

레드-블랙 트리는 자가 균형 이진 탐색 트리의 한 종류이며,

앞서 살펴본 이진 탐색 트리가 탐색 시 최악의 경우 시간복잡도가 O(n)인 부분을

몇 가지 조건을 통해 균형 잡힌 트리로 만들어

최악의 경우에도 탐색 시 O(logn) 을 보장하는 자료 구조이다.

레드-블랙 트리의 조건​

이진 탐색 트리가 가진 조건에서 다음 조건을 만족해야 레드-블랙 트리라고 할 수 있다.

1. 모든 노드는 Red이거나 Black이다.
2. 루트 노드는 Black이다.
3. 모든 리프노드(단말노드)는 Black이다.
4. 노드가 Red이면 그 자식은 Black이다. No Double Red => Red 노드가 연속으로 나올 수 없음
5. 루트노드에서 모든 리프노드까지의 경로에서 만나는 Black노드의 수는 같다.

레드-블랙 트리 삽입 연산​

삽입 연산을 통한 레드-블랙 트리를 만들기 전에 알아야 할 사항들이 있다.

• 새로 삽입되는 노드의 색은 무조건 Red 이다.
• Double Red가 발생하지 않기 위해 다음 2가지 전략을 통해 해결한다.
  • Recoloring
    • 새로 삽입된 노드의 삼촌 노드(부모 노드와 형제인 노드) 가 Red인 경우 수행
      • 새로 삽입된 노드의 부모 노드, 삼촌 노드를 Black으로 하고 조부모 노드를 Red로 한다.
      • 조부모 노드가 루트 노드가 아니라면 Double Red가 다시 발생할 수 있다.
      • 위와 같은 상황이 발생하면 그때 다시 Recoloring 또는 Rotation 연산을 수행한다.
  • Rotation
    • 새로 삽입된 노드의 삼촌 노드(부모 노드와 형제인 노드) 가 Black이거나 null인 경우 수행
      • 새로 삽입된 노드, 부모 노드, 조부모 노드를 오름차순으로 정렬한다.
      • 이후, 중간에 위치한 노드를 부모 노드로 하고 나머지 두 노드를 자식 노드로 만든다.
      • 부모 노드를 Black으로 하고, 두 자식들을 Red로 한다.

위 사항들을 숙지하고 레드-블랙 트리 삽입 연산을 진행하면 다음과 같다.

레드-블랙 트리 삭제 연산​

• Red 노드를 삭제할 때는 그냥 삭제 연산을 수행하면 된다.
  • Double Red만 아니면 되기 때문이다.
• Black 노드를 삭제할 때는 레드-블랙 트리 조건을 유지하여야 한다.
  • 삽입 연산때 처럼 Rotation을 통해 해결이 가능하다.

레드-블랙 트리 시간복잡도​

정의에서 언급한 것 처럼, 레드-블랙 트리는 이진 탐색 트리가 편향되는 모습을 개선한 구조인

자가 균형 이진 트리의 한 종류이다.

그러므로 최악의 경우에도 레드-블랙 트리는의 시간 복잡도는 O(logn)이다.

레드-블랙 트리의 장단점​

• 장점
  • 최악의 경우에도 일정한 실행 시간을 보장한다.
  • 위와 같은 성능적 장점으로 인해, 실시간 처리와 같은 실행시간이 중요한 경우 유용하게 쓰이며,
    일정한 실행 시간을 보장하는 다른 자료구조를 만드는 데에도 유용하다고 한다.
• 단점
  • 이해하기 어려우며 구현이 복잡하다.

참고​

• 레드-블랙 트리 - 위키피디아
• 알고리즘 ) Red-Black Tree - Zedd0202님 블로그
• RedBlack Tree에 대해 - Nesoy님 블로그
• RB tree - Ratsgo님 블로그
• Red - Black Tree Datastructure - btechsmartclass

1. B-Tree란?​

B-Tree는 자식 노드의 개수가 2개 이상인 트리를 말한다.

이진트리가 자식 노드가 최대 2개인 트리를 말하는 것인데,

이 이진트리를 확장해서 더 많은 수의 자식을 가질 수 있게 일반화 시킨 것이 B-Tree이다.

2. B-Tree의 구조​

그림의 네모 칸 하나 하나를 '노드' 라고 하며, 가장 상단의 노드를 '루트 노드(Root Node)',

중간 노드를 '브랜치 노드(Branch Node)',

가장 하단의 노드를 '리프 노드(Leaf Node)' 라고 한다.

안의 구조를 자세히 살펴보면 다음과 같다.

위 그림에서 보듯이, 노드당 데이터를 2개 이상 가질 수 있으며

자식 노드를 자신의 데이터 수 이상으로 가질 수 있다.

즉, 노드의 데이터가 N개이면, 자식 수는 N+1개가 된다.

여기서 노드당 최대 M개의 자식노드를 가질 때, M차 B트리 라고 한다.

3. B-Tree의 규칙​

• 노드의 자료수가 N이면, 자식 수는 N+1이어야 함
• 각 노드의 자료는 정렬된 상태여야함 ( 1, 3, 5 처럼 )
• 루트 노드는 적어도 2개 이상의 자식을 가져야함
• 루트 노드를 제외한 모든 노드는 적어도 M/2개의 자료를 가지고 있어야함
• 외부 노드(Leaf Node)로 가는 경로의 길이는 모두 같음.
• 입력 자료는 중복 될 수 없음
• 이진트리와 같이 노드 데이터보다 작은값은 왼쪽에, 큰 값은 오른쪽에 위치

4. B-Tree의 삽입, 삭제​

① B-Tree의 삽입 연산

1. 데이터를 탐색해 해당하는 Leaf 노드에 데이터 삽입
2. Leaf 노드 데이터가 가득 차 있으면 노드를 분리하여 서브트리 구성 ( 위의 insert 7 참고 )
3. 분리한 서브트리가 B-Tree 규칙에 맞지 않는다면 부모 노드로 올라가 merge
   
   (insert 12에서 [9, 7, 12] 를 서브트리로 분리하였지만 B-Tree의 조건인 "Leaf노드가 모두 같은 레벨에 존재" 를 만족시키지 못했으므로 root로 merge)

② B-Tree의 삭제 연산

전체적인 과정은 다음과 같다.

1. 삭제할 키가 있는 노드 검색
2. 키 삭제
3. 필요한 경우, 트리 균형을 위한 조정

자세한 과정을 예시로 설명하면 다음과 같다. ( 리프노드인 1 삭제 과정 )

1. 1을 찾아 루트부터 탐색한다
2. 1을 삭제한다
3. 트리의 균형이 깨져 조정 작업을 진행한다
   3-1) 1의 부모노드(5)를 가져온다
   3-2) 형제 노드(7)와 merge한다
   3-3) 한 단계 더 올라가 부모노드중 한 값을(9) 자식 노드로 값을 가져온다
   3-4) 형제 노드(12)와 merge한다.
4. 3-3,4 과정을 root노드까지 올라가며 균형이 맞을 때 까지 반복한다.

리프노드가 아닌 노드를 삭제할 때의 과정은 다음과 같다 (이너 노드인 18 삭제 과정 )

1. 18을 찾아 루트부터 탐색한다
2. 18을 삭제한다
3. 트리의 균형이 깨져 조정 작업을 진행한다
   3-1) 왼쪽 서브트리의 최댓값인 17을 가져온다
   3-2) 부모노드(17, 22)중 적절한 값(17)을 자식노드로 가져온다
   3-3) 형제노드(20)와 merge 한다.
4. 3-2, 3) 과정을 root노드까지 올라가며 균형이 맞을 때 까지 반복한다.

5. B+Tree란?​

B-Tree의 확장개념으로, 데이터의 빠른 접근을 위해 인덱스 역할만 하는 비단말 노드(Not Leaf)가 추가로 존재한다.

브랜치 노드에는 노드를 찾아갈 수 있는 Key만 담아두고

리프 노드에 Key와 Data가 존재한다.

그리고 리프 노드끼리는 연결리스트(LinkedList)로 연결되어 있다.

6. B+Tree의 구조​

위의 그림처럼 InnerNode는 LeafNode의 데이터를 찾아가는 데에만 쓰이며,

LeafNode끼리는 LinkedList로 연결되어 있다.

7. B+Tree와 B-Tree의 차이점​

• B-Tree는 모든 노드에 데이터가 저장됨
• B+Tree는 Leaf에만 데이터 저장. 나머지 노드에는 Key만 저장됨 ( 메모리 활용에 효율적 )

• B-Tree는 탐색시, 최상의 경우엔 루트에서 끝날 수 있지만,
• B+Tree는 최상의 경우에도 일단 Leaf로 내려가야 함

• B-Tree는 순차 탐색시에도 매번 루트에서 탐색을 시작하지만,
• B+Tree는 순차탐색 시 LinkedList를 통해 빠르게 이어나갈 수 있음 (범위 탐색과 풀스캔에 유리)

1. 이진탐색트리란?​

이진탐색트리란 이진탐색(Binary Search)와 연결리스트(Linked List)를 결합한 자료구조의 일종이다.

위와 같은 이진 탐색과 연결리스트의 장점을 고안하기 위해 만들어졌으며, 

이진 탐색의 효율적인 탐색 능력을 유지하면서도

빈번한 자료 입력과 삭제가 가능하기 위해 사용된다.

2. 이진탐색트리 특징​

이진탐색트리는 이진트리의 일종으로 다음과 같은 규칙으로 구성한다.

• 모든 노드는 유일한 키를 갖음. (중복된 노드 X)
• 각 노드의 왼쪽 서브 트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어짐.
• 각 노드의 오른쪽 서브 트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어짐.
• 각 노드의 왼쪽, 오른쪽 서브트리 또한 이진탐색트리로 구성.

다음은 이진탐색트리가 가진 특징이다.

탐색의 시간 복잡도는 트리의 높이를 h라고 할 때 O(h) 이다.

위와 같은 편향 트리의 경우 탐색에 O(N)의 시간이 소요된다.

• 이진탐색 트리의 순회는 중위 순회 (in order) 방식이다. (왼쪽 - 루트 - 오른쪽)
  
  
  중위 순회: 4, 7, 16, 20, 37, 38, 43 (중위 순회 방식으로 정렬된 순서를 얻을 수 있다)

• 이진탐색트리의 삽입 연산은 루트노드에서 탐색을 시작해 서브트리가 없는 리프 노드에서 이루어진다.
  
  

이진탐색트리의 삭제 연산은 세가지 케이스로 나누어 연산한다.

• 자식 노드가 없는 경우 -> 삭제할 노드를 그냥 없앤다.
• 자식 노드가 하나 있는 경우 -> 삭제할 노드의 자식을 올린다.
• 자식 노드가 두 개 있는 경우 -> 오른쪽 서브 트리에서 가장 작은 값 or 왼쪽 서브 트리에서 가장 큰 값을 올린다.

3. 시간복잡도

Q: 이진탐색트리의 시간복잡도는?

A. 트리의 높이를 h라고 할 때 O(h)이다.
노드의 개수 N이 주어졌을 때 균등 트리 일 경우, O(logN) 이며
편향 트리일 경우 최악의 경우, O(N) 이다.

Q. 이진탐색트리의 삽입,삭제 연산 시간복잡도는?

A. 이진탐색트리의 삽입과 삭제 연산은 탐색이후 이루어지기 때문에
탐색에 필요한 O(h)이 소요되며 연결리스트를 사용하므로
입력과 삭제에는 O(1)이 사용된다.

따라서 총 소요되는 시간 복잡도는 O(h)이며
최악의 경우 탐색과 동일하게 O(N)이 소요된다.

※ 따라서, 이진 탐색 트리는 한쪽 방향으로 노드가 집중된 편향트리에서는 효율적이지 않다.

힙이란?​

힙(Heap)이란, 완전 이진 트리에 있는 노드 중에서

키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해서 만든 자료구조이다.

키 값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(Max Heap)이라 하고,

키 값이 가장 작은 노드를 찾기 위한 힙을 최소 힙(Min Heap)이라고 한다.

아래 그림은 최대 힙과 최소 힙의 예시이다.

힙의 연산​

힙에는 새로운 원소를 추가하는 삽입 연산,

루트 노드에 있는 원소를 삭제하는 삭제 연산 두가지가 존재한다.

다만, 힙은 항상 부모노드를 최대 힙일 경우 최대, 최소 힙일 경우 최소로 유지해주어야 하는 특성이 있다.

• 최대 힙 : 부모노드의 키 값 >= 자식노드의 키 값
• 최소 힙 : 부모노드의 키 값 <= 자식노드의 키 값

이제 각각의 연산의 과정과 시간복잡도에 대해 알아보자.

힙의 삽입 연산​

간단하게 먼저 말로 순서를 설명해 보자면 다음과 같다.

1. 새로운 노드를 힙의 마지막 노드에 삽입한다.
2. 새로운 노드를 부모 노드들과 교환해 힙의 성질을 만족시킨다.

그림으로 보면 아래와 같은 과정을 거친다. (최대 힙의 삽입 과정)

힙의 삭제 연산​

힙의 삭제 연산은 언제나 루트 노드에 있는 원소를 삭제하여 반환한다.

따라서 루트 노드를 삭제하고 다시 트리를 힙의 조건으로 유지시켜주어야 한다.

과정은 다음과 같다.

1. 힙의 루트 노드를 삭제 후 반환
2. 마지막 노드를 루트 노드로 이동
3. 힙의 조건에 맞게 트리를 재 조정

그림으로 보면 아래와 같은 과정을 거친다. (최대 힙의 삭제 과정)

힙 연산의 시간복잡도​

삽입과 삭제 모두 힙의 높이(이진 트리의 높이)만큼 연산하는 경우가 최악의 경우 이므로,

힙의 높이가 무엇인지 안다면 그 시간복잡도를 알 수 있다.

완전 이진 트리의 모든 노드가 존재한다고 했을 때 높이를 h라고 하고 노드의 개수를 n이라고 하면 다음이 성립한다.

이는 등비수열의 합 공식에 의하여 다음과 같다.

즉,

위의 식에 양변에 로그를 취하면 다음과 같다.

따라서, 시간 복잡도는

O(h) = O(log2(n+1)-1) = O(log2n) 이다.

힙 사용 예시​

앞서 살펴본 바와 같이 힙은 최댓 값이나 최솟 값을 찾는데 사용된다.

또한 우선순위 큐를 구현할 때 가장 효율적인 자료구조가 heap이기도 하다.

마지막으로 힙 정렬을 만들 때 힙을 쓰기도하고, 무손실 압축 알고리즘인 허프만 코드도 힙의 구조를 기반으로 하고 있다.

힙 간략 코드​

C언어로 구현한 코드는 위키백과 수도코드와 C언어 코드를 참고하면 좋을 것 같다.

여기서는 python의 heapq 모듈 사용법을 설명해보려고 한다.

# heapq 모듈 선언
import heapq

# heap 배열 생성
heap = []

# 힙에 원소 추가
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

# 힙에 원소 삭제
heapq.heappop(heap) # 가장 작은 1이 삭제됨 ( 기본적으로 최소힙 )

Stack의 정의​

Stack이란, Stack이란 단어의 의미처럼 쌓아 올린다는 뜻이다.

한쪽에서만 원소를 삽입하고 삭제가 가능한 자료구조이다.

한쪽에서만 원소를 쌓아 올리고 꺼내고 하기 때문에

LIFO(Last In First Out) 구조로 되어있다.

Stack의 기술 내용​

Stack에는 두가지 중요한 기술인 Push와 Pop이 있다.

위 그림과 같이 입구와 출구가 동일한 바구니가 있다.

Push를 하게 되면 바구니에 원소를 집어넣게 되며,

또 한번 Push를 하게 되면 첫 원소 위에 두번째 원소가 위치하게 된다.

여기서 첫번째 원소를 꺼내고 싶다면 Pop을 두번해야 한다.

결국 삽입을 할 때에도 맨 위(Top)에 삽입을 하게 되고 꺼낼때에도 맨 위에 있는 원소를 꺼내게 된다.

주로

• 문자열의 역순을 만들 때,
• 괄호 검사를 할 때,
• DFS
• 재귀함수
• 웹 브라우저에서의 뒤로가기 방식 등
  에 사용된다.

그래서, Stack의 시간복잡도는 Stack 안의 원소의 총 개수가 n일 때, O(n)이다.

Queue의 정의​

Queue란, 일렬로 서서 들어온 순서대로 나가는 방식이다.

한쪽에서 원소를 삽입하고, 반대쪽에서 삭제가 가능한 자료구조이다.

즉, 입구와 출구가 각각 존재하기 때문에 들어온 순서대로 나갈 수 있다.

그래서 FIFO(First In First Out)구조로 되어있다.

Queue의 기술 내용​

Queue에는 두가지 중요한 기능인 Enqueue와 Dequeue가 있다.

Enqueue를 하여 데이터를 삽입할 수 있고

Dequeue를 사용하여 데이터를 제거할 수 있다.

데이터를 삽입할 때에 삽입되는 원소의 위치는 Queue의 맨 뒷부분(Back)이고,

데이터를 제거할 때에 제거되는 원소의 위치는 Queue의 맨 앞부분(Front)이다.

Queue의 시간복잡도는 Queue 안의 원소의 총 개수가 n일 때, O(n)이다.

큐는 주로,

• 프로세스 관리
• 대기순서 관리
• 너비우선탐색(BFS) 등

에 쓰인다.

트리(Tree) 란?​

• 트리는 노드로 이루어진 자료 구조
  • 트리는 하나의 루트 노드를 갖음
  • 루트 노드는 0개 이상의 자식 노드를 갖고 있음.
  • 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있음.
• 노드와 노드는 서로를 연결하는 간선들로 구성.
  • 트리에는 사이클(cycle)이 존재할 수 없음.
  • 노드들은 특정 순서로 나열될 수도, 아닐 수도 있음.
  • 각 노드는 부모 노드로의 연결이 있을 수도 있고 없을 수도 있음.
  • 각 노드는 어떤 자료형으로도 표현 가능함.
• 비선형 자료구조로 계층적 관계를 표현함.
• 그래프의 한 종류
  • 사이클(cycle)이 없는 하나의 연결 그래프(Connected Graph)
  • DAG(Directed Acyclic Graph, 방향성이 있는 비순환 그래프)의 한 종류.

트리의 특징​

• 그래프의 한 종류로,  '최소 연결 트리' 라고도 불림.
• 계층 모델
• DAG(방향성이 있는 비순환 그래프)의 한 종류
  • loop나 circuit이 없다.
  • 즉, 사이클이 없다
• 노드가 N개인 트리는 항상 N-1개의 간선(edge)를 가짐.
  • 즉, 간선은 항상 (정점의 개수 -1)만큼을 가짐.
• 루트에서 어떤 노드로 가는 경로는 유일.
  • 임의의 두 노드 간의 경로도 유일. 즉, 두 개의 정점 사이에 반드시 1개의 경로만 존재.
• 한 개의 루트 노드만이 존재하며 모든 자식 노드는 한 개의 부모 노드만을 가짐
• 트리는 이진트리, 이진 탐색트리, 균형트리(AVL 트리, red-black 트리), 이진 힙(최대힙, 최소힙) 등이 존재.
  .
• 순회는 Pre-order, In-order, Post-order 가 있음.
  
  부모 노드를 언제 방문하는지에 따라 이름이 붙어졌다고 생각하면 쉽다.
  
  • Pre-order(전위 순회) : 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식 노드
  • In-order(중위 순회) : 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드
  • Post-order(후위 순회) : 왼쪽 자식 노드 -> 오른쪽 자식 노드 -> 부모 노드
    
    
• 예시로, 아래 그림에서 순회 순서는 다음과 같다.
  
  • Pre-order(전위 순회)는 1 -> 2 -> 4 -> 5 -> 3
  • In-order(중위 순회)는 4 -> 2 -> 5 -> 1 -> 3
  • Post-order(후위 순회)는 4 -> 5 -> 2 -> 3 -> 1

Mininum Spanning Tree(최소 신장 트리)​

Spanning Tree란 그래프 내의 모든 정점을 포함하는 트리이다.

• Spanning Tree는 그래프의 최소 연결 부분 그래프라는 특징을 가짐.
  (최소 연결 = 간선의 수가 가장 적음)
• 하나의 그래프에는 다수의 신장 트리가 존재할 수 있음.
• Spanning Tree는 트리의 특수한 형태이므로 모든 정점들이 연결되어 있어야하고 사이클을 포함해서는 안됨.
• MST(최소 신장 트리)는 간선에 가중치를 고려하여 최소 비용의 Spanning Tree를 선택하는 것을 말함.

트리의 용어​

• 노드의 차수- 한 노드가 가진 서브트리의 수
  • A의 차수: 3
  • B의 차수: 2
  • C의 차수: 0
• 리프노드(단말,터미널) - 차수가 0인 노드
  • 리프노드: E, J, K, L, H, I, C
• 자식노드- 노드에 연결된 서브트리의 루트노드들
  • A의 자식노드: B, C, D
• 부모노드- 노드에 연결된 한단계 상위 레벨 노드
  • I의 부모노드: D
• 형제 노드- 부모가 같은 노드
  • G, H, I는 형제노드
• 트리의 차수- 트리노드들의 차수중 최대 차수
  • 트리의 차수:3
• 트리의 깊이(높이)- 트리의 최대 레벨
  • 트리의 깊이: 3

트리의 종류​

이진트리(Binary tree)​

• 이진트리란 자식노드가 최대 두 개인 노드들로 구성된 트리.
• 이진트리에는 정이진트리, 완전이진트리, 균형이진트리 등이 존재.

트리의 순회(Tree Traverse)​

위에서 설명한 트리의 순회를 좀 더 복잡한 그래프를 가지고 설명하자면,

• 전위 순회(preorder traverse): 루트를 먼저 방문
• 중위 순회(inorder traverse): 왼쪽 하위 트리를 방문 후 루트를 방문
• 후위 순회(postorder traverse): 하위 트리 모두 방문 후 루트를 방문

전위순회: 0->1->3->7->8->4->9->10->2->5->11->6

중위순회: 7->3->8->1->9->4->10->0->11->5->2->6

후위순회: 7->8->3->9->10->4->1->11->5->6->2->0

위와같은 순서로 각 순회를 진행하게 된다.

이진트리의 시간복잡도​

이진트리의 시간복잡도는 순회만 했을 때 기준으로 O(N).

하지만, 탐색에 대한 기준이 있다면 이를 이진탐색트리(binary search tree)라고 하는데

이럴 경우 트리의 높이만큼의

시간이 소요되므로 탐색의 시간복잡도는 O(h)이다.

따라서 균형이 잡힌 이진트리의 경우 O(logN)의 시간복잡도를 가지게된다.

그래프와 트리의 차이​

안드로이드 개발 입문단계에서는,

View( Activity, Fragment )에서 View의 동작과, 데이터 처리까지 모두 작성하는 방법으로

안드로이드 앱을 제작했을 것이다.

하지만 이렇게 작성하게 되면 코드 작성은 쉬울 수 있지만,

여러 사람들과 협업을 했을 때, 코드 가독성이나 관리, 로직 구현이 굉장히 까다로워진다.

또한 하나의 class에 모든 처리를 위한 수많은 코드들이 들어가게 되어 스파게티 코드로 변환될 가능성이 있다.

그리고 UI에서 모든 걸 처리하기 때문에 비즈니스 로직에 따른 UI의 변화들을

직접 개발자가 바꿔줘야 하는 까다로움이 존재한다.

이로 인해 테스트 코드의 작성이 어려워지게 되며 유지보수에 굉장히 큰 어려움이 따를 수 있다.

이러한 단점을 극복하고자 나온 패턴이 바로 MVP 패턴과 MVVM 패턴이다.

MVP패턴 또한 장단점을 갖고 있으며, MVP패턴의 단점을 극복하고자 발전한 패턴이 MVVM 패턴이기 때문에

먼저 MVP 패턴부터 살펴보도록 하자.

MVP 패턴에 대해

먼저, MVP패턴은 구글에서 제공한 아키텍쳐 설계 코드를 기반으로 공부하였다.

MVC패턴과 MVP패턴의 차이점을 먼저 그림으로 보고, 정리해보고자 한다.

MVC 패턴

MVP패턴

MVC패턴에서는 Model과 Activity( View + Controller )로 구성이 되어있고

MVP 패턴은 Model과 View, Presenter로 구성되어 있다.

MVC패턴의 Activity에서 UI관련 처리부터 데이터 처리까지 모든 기능을 구현했다면

MVP패턴은 이들을 View와 Presenter로 분할한 것이다.

여기서 Presenter의 역할은 View와 Model을 분리하여,

서로간에 상호작용을 Presenter가 담당함으로써 서로간의 영향을 최소화 하는 것이다.

작동과정은 다음과 같다.

1. View에서 사용자 이벤트가 발생하게 되면 이 이벤트를 Presenter로 전달하게 되고
2. Presenter는 이 이벤트를 받아 이에 필요한 데이터를 Model로 요청하게 된다.
3. Model은 Presenter의 호출에 따라 필요한 데이터를 Presenter로 전달하게 되고
4. Presenter는 Model로부터 받은 데이터를 가공하여 View로 전달하게 된다.
5. View는 이것들을 바탕으로 UI를 갱신하게 된다.

그럼 이제, 구글에서 제공한 샘플 코드를 가지고 MVP 패턴을 살펴보자.

(아래의 링크를 통해 전체 코드와 디렉토리 구조를 보면서 아래의 설명을 보도록 하자.)

구글에서 제공한 아키텍쳐 설계 코드

먼저 각각의 Task마다 View, Presenter, Contract가 작성된 것을 확인할 수 있는데

여기서 Contract는 View와 Presenter에 대한 interface를 작성하는 부분이다.

그래서 View는 Contract.View을 상속받아서 구현하게 되고

Presenter는 Contract.Presenter을 상속받아서 구현하게 된다.

Presenter에는 필요한 데이터를 Model로 요청하는 함수와 받아온 데이터를 View로 전달하는 코드들이 구현되어 있고

View에는 UI의 갱신과, Presenter로 이벤트 전달을 하는 코드들이 구현되어 있음을 알 수 있다.

하지만 코드를 뜯어보면 알 수 있듯이, View와 Presenter 간의 의존성이 높음을 알 수 있다.

View와 Model은 분리가 되었지만, 앱의 크기가 거대해지면서 Model에서 받아온 대량의 데이터에 따라

각각의 다른 UI를 표시해야 한다면, 각각의 조건에 맞는 로직을 추가해주어야 하고,

그렇게 되면 추가된 만큼의 코드가 생겨나면서 로직이 굉장히 거대해지기 때문에

코드의 길이 또한 상당히 길어지게 된다.

그렇게 되면 위에서 설명한 것 처럼 코드의 가독성이 떨어지며 테스트 또한 어려워지게 된다.

또한, 각각의 조건에 맞게 UI가 올바르게 변경되었는지 확인작업도 필요할 것이다.

그래서 이러한 단점을 극복하기 위해 MVVM 패턴과 Usecase 등이 등장하게 되었다.

그래서 다음 포스팅으로 MVVM 패턴을 소개하려고 한다.