자료구조 Tree

트리(Tree)의 개념

: 트리란 비선형 구조(계층적 or 망)로 노드와 가지로 연결된 그래프의 특수현 형태로 계층 구조를 가진다.

중요한건 사이클이 존재해서는 안된다는 것

트리의 기본 용어

-루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.

-단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.

-내부(internal) 노드: 단말 노드가 아닌 노드

-간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)

-형제(sibling): 같은 부모를 가지는 노드

-노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수

-노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

-노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합

-노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수

-트리의 차수(degree of tree): 트리의 최대 차수

-트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

이진트리Binary tree 

각 노드가 최대 두개로 이루어진 트리

(1) 완전이진트리complete binary tree

-마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있는 트리

-노드는 왼쪽 자식부터 채워진다

(2) 전이진트리full binary tree

-모든 노드가 0개 또는 2개의 자식을 갖는 트리

(3) 포화이진트리 perfect binary tree

-전이진트리이면서 완전이진트리인 경우

-모든 말단 노드가 같은 높이에 있음

-노드의 개수는 2^(n-1)

기타 다른 트리

사향이진트리skewed binary tree

-자식의 노드가 하나뿐인 트리

-검색에서 가장 효율이 안좋음 O(n)

-이를 방지하고자 나타난게 균형트리이다.

이진 검색 트리 Binary Search Tree

정의: node n을 기준으로 다음의 식이 성립되는 트리

왼쪽자식 <= n <= 오른쪽 자식

C++ STL #include<algorithm>안에 binary_search함수가 내장되어 있다.

binary_search(startaddress, endaddress, valuetofind)

startaddress: the address of the first element of the array.
endaddress: the address of the last element of the array.
valuetofind: the target value which we have to search for.

#include <algorithm>

#include <iostream>

  

using namespace std;

  

void show(int a[], int arraysize)

{

    for (int i = 0; i < arraysize; ++i)

        cout << a[i] << " ";

}

  

int main()

{

    int a[] = { 1, 5, 8, 9, 6, 7, 3, 4, 2, 0 };

    int asize = sizeof(a) / sizeof(a[0]);

    cout << "\n The array is : ";

    show(a, asize);

  

    cout << "\n\nLet's say we want to search for 2 in the array";

    cout << "\n So, we first sort the array";

    sort(a, a + asize);

    cout << "\n\n The array after sorting is : ";

    show(a, asize);

    cout << "\n\nNow, we do the binary search";

    if (binary_search(a, a + 10, 2))

        cout << "\nElement found in the array";

    else

        cout << "\nElement not found in the array";

  

    cout << "\n\nNow, say we want to search for 10";

    if (binary_search(a, a + 10, 10))

        cout << "\nElement found in the array";

    else

        cout << "\nElement not found in the array";

  

    return 0;

}

위 소스코드의 결과

The array is : 1 5 8 9 0 6 7 3 4 2 0

Let's say we want to search for 2 in the array
 So, we first sort the array

The array after sorting is : 0 1 2 3 4 5 6 7 8 9

Now, we do the binary search
Element found in the array

Now, say we want to search for 10
Element not found in the array

트리의 구현 방법

인접 배열 이용

1. 1차원 배열에 자신의 부모 노드만 저장하는 방법

2. 이진 트리의 경우 2차원 배열에 자식 노드를 저장하는 방법

인접 리스트 이용

균형 나무

O(logN)시간에 insert와 find를 할 수 있는 균형이 잘 잡혀있는 트리

(1)AVL나무

기본적으로 이진 탐색 트리와 비슷한 구조를 띄고 있지만 AVL나무는 BF(Balance Factor)를 더 가지고 있다.

여기서 BF란 한 노드를 기점으로  (왼쪽편 자식에 속하는 노드들의 갯수) - (오른쪽 자식에 속하는 노드들의 갯수) 

BF = hL - hR 를 의미한다. 이때 BF의 값이 -1, 0, 1 중 하나여야 한다.

삽입연산시 BF값이 범위를 초과한 경우 다음 수행을 통해 균형을 유 지한다.

- LL : N이 A의 왼쪽 서브트리의 왼쪽에 삽입되는 경우

- LR : N이 A의 왼쪽 서브트리의 오른쪽에 삽입되는 경우

- RR : N이 A의 오른쪽 서브트리의 오른쪽에 삽입되는 경우

- RL : N이 A의 오른쪽 서브트리의 왼쪽에 삽입되는 경우

- LL : A부터 N까지의 경로 상의 노드들을 오른쪽으로 회전시킨다.(단순회전)

- LR : A부터 N까지의 경로 상의 노드들을 왼쪽-오른쪽으로 회전시킨다.(이중회전)

- RR : A부터 N까지의 경로 상의 노드들을 왼쪽으로 회전시킨다.(단순회전)

- RL : A부터 N까지의 경로 상의 노드들을 오른쪽-왼쪽으로 회전시킨다.(이중회전)

첫번째 LL의 경우 C를 A의 오른쪽 노드로 단순 회전시키면 된다.

두번째 LR의 경우 A와 B의 자리를 바꿔준 후 LL수행을 해주면 된다.

(2)흑적 나무

https://zeddios.tistory.com/237

이진 탐색 트리 중 가장 효율적인 자료구조이다. 운영체제의 가상 메모리 관리 등 높은 효율성이 필요한 프로그램에서 사용된다.

흑적 나무의 노드는 컬러가 블랙 또는 레드이며 다음의 조건을 만족한다.

1. 노드는 레드 혹은 블랙이다.

2. 루트 노드는 블랙이다.

3. 모든 잎 노드는 블랙이다.

4. 레드노드의 자식노드는 블랙이다. 레드노드의 부모노드 또한 블랙이다 == 빨간색 노드가 연속으로 나올 수 없다.

5. 잎 노드에서 루트노드 까지 가는 경로에서 만나는 블랙노드의 개수는 같다. depth property

삽입되는 노드의 색은 무조건 Red다.

해결방안이 두가지가 있다.

해결방안을 결정하는 기준은 삼촌노드(w)

1. w가 검정일 떄는 restructuring

2.w가 빨강일 때는 recoloring

1.Restructuring

-나와 내 부모, 내 부모의 부모를 오름차순으로 정렬

-가운데 값을 부모로 만들고 나머지 둘을 자식으로 만든다.

-가운데 값을 검정 그 자식들을 빨강으로 만든다.

2. Recoloring

-현재 insert된 노드의 부모와 그 형제를 검정으로 하고 조부모를 빨강으로 한다.

-조부모가 루트노드가 아닌 경우 다시 더블레드가 발생할 수 있다.

C++ STL의 map에 사용된다.

최소신장나무

그래프 G의 모든 정점들을 사이클이 생기지 않게 연결하면서 간선에 부여된 가중치의 합이 가장 적게 구성된 나무이다.

최소 신장 나무를 만드는 방법에는 kruskal과 prim이 제안한 알고리즘이 있다.

(1)크루스칼의 알고리즘

욕심쟁이 방법이 적용된 것으로 사이클을 만들지 않는 최단 간선을 하나씩 추가해 나감으로써 최소 신장 나무를 구하는 방식이다.

1. 가중치가 주어진 그래프에서 최소 가중치를 갖는 간선부터 하나씩 선택

2. 사이클이 형성되지 않으며 신장 나무 T에 포함

3. 이 과정을 간선의 수가 n-1이 될 때 까지 반복

(2)프림의 알고리즘

임의의 정점을 선택하고 이 정점에 연결된 간선들 중 가중치가 가장 작은 간선을 선택하여 최소 비용 신장 나무에 포함시킨다.

그 이후 부터는 최소 비용 신장 나무에 인접한 정점들에 연결된 간선들에 대해 가중치가 제일 작은 간선을 선택하여 사이클이 생성되지

않으면 포함시킨다.

1. 시작 정점을 임의로 선택

2. 선택된 정점들에 부속된 간선들 중 가중치가 가장 작은 간선을 선태갛여 최소 비용 신장 나무에 포함

3. 사이클이 발생하면 선택한 간선을 제거하고 그 다음 가중치가 작은 간선이 있으면 선택

4. 모든 정점이 연결되면 종료