나무(Tree)

트리는 그래프의 일종으로 계층형 자료구조 

 

트리는 데이터가 저장된 노드(Node)와 노드 간 관계를 표현하는 간선(Edge)으로 구성된다.

 

용어

트리에는 여러가지 용어가 있다. 그림을 참고하자

 

• 루트(Root) : 첫 노드
• 조상(Ancestor) 노드 : 한 노드에서 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드
• 자손(Descendant) 노드 : 조상 노드의 반대
• 차수(Degree) : 한 노드가 가지는 서브 트리의 수. 노드의 차수 중 최댓값을 트리의 차수라 한다.
• 내부(Internal) 노드 : 단말 노드를 제외한 나머지 노드 ex) A , B , C , D , E
• 포레스트(Forest) : 트리의 집합
• 레벨(Level) : 높이

순회

전위 순회

 

DFS 방식과 비슷하다

 

A - B - D - H - I  - E - J - C - F - G

 

중위 순회

 

H - D  - I - B - J - E - A - F - C - G

 

후위 순회

 

H - I - D - J - E - B - F - G - C - A

 

레벨 순회

 

A - B - C - D - F - G - H - I - J 

 

BFS 방식과 비슷함

 

B 트리

파일 시스템 , DB에서 이용됨.

 

이진 검색 트리 

 

이진 검색 트리(Binary Search Tree)는 한 노드를 기준으로 왼쪽 서브 트리는 모두 그 노드보다 작은 값을 가지고 있으며, 오른쪽 서브 트리는 모두 그 노드보다 큰 값을 가지고 있는 이진트리*(Binary tree)이다.

수식으로 표현하면 왼쪽 자식 노드의 값 <= 부모 노드의 값 <= 오른쪽

데이터 삽입순서가 중요하다.

 STL에 구현된 트리 컨테이너는 모두 이진 검색 트리다.

 

연산

 

트리가 균형잡혀 있다면 모든 연산이 O(log n)이지만,편향*되어 있다면 O(N)에 가까워진다.

 

{3 , 1 , 4 , 2 , 5}

이진검색트리를 중위 순회 시 작은 값부터 나온다.

{1 , 2 , 3 , 4 , 5 }

 

AVL 트리

 

쓰는 이유 트리가 편향적으로 삽입이 되어버리면, O(N)에 가까워 진다.

 

자가균형 이진탐색 트리

 

삽입을 할때 불균형을 막아준다.

 

힙(Heap)

완전 이진 트리에 있는 노드 중에서 키값이 가장 큰 노드나 키값이 가장 작은 노드를 찾기 위해 만든 자료구조

 

키값이 가장 큰 노드를 찾기 위한 힙을 최대 힙(max heap), 가장 작은 노드를 찾기 위한 힙을 최소 힙(min heap)이라고 한다. 루트에 최대 힙, 최소 힙이 있다.

우선순위 큐(priority queue)라고도 한다.

 

힙의 불변성

힙은 최대 / 최소 원소에 즉각적으로 접근이 가능해야한다. 그래서 최대 / 최소 원소가 항상 고정된 위치에 있어야 한다.

그래서 최대 / 최소 원소는 항상  트리의 루트에 존재한다. 부모 노드가 두자식 노드보다 항상 크거나 작아야 한다.

ㅂ

연산

• 검색 및 읽기 :  최대 /최소 원소에 대해서만 가능하여O(1)이다.
• 삽입 : 완전 이진 트리이기 때문에 O(logN)이다.
• 삭제 : 최대 / 최소 원소에 대해서만 가능하여 O(logN)이다.

 

해시 테이블

●  해싱(hashing) : 입력의 크기에 상관 없이 일정 크기의 값으로 변환하는 것. 이에 사용되는 함수를 해시 함수(hash funtion)라 한다.

    ⊙균일성 : 충돌이 적은 것을 의미한다.

        ■ 충돌(collision) : 서로 다른 값이 같은 해시 값을 생성한 것

 

    ⊙효율성 : 계산하기 쉬워야 한다.

    ⊙결정적 : 같은 입력에는 같은 값을 내놓아야 한다.

 

    ⊙Ex. 디지털 서명, 공인 인증서 등등등등

● 해시 테이블(hash table) : 해싱을 활용해 데이터를 저장하는 검색을 위한 자료구조 , 연관 배열(associative array)이라고     한다. 해시 값을 테이블의 인덱스로 활용한다.

●  충돌 처리

    ⊙ 선형 개방 주소법or 선형 조사법

        ■ 충돌이 나면 걍 빈 곳을 찾아서 넣는다.

    ⊙ 체이닝

        ■ 충돌이 나면 리스트로 여러 값을 저장하게 한다.

 

-백트래킹

     -