Data Structures2(Tree, B-Tree, Graph, Hash Table)

Tree

선형자료구조방식이아니라 계층형태(Ex. Dom Tree, 가계도, 월드컵 토너먼트 대진표)

트리는 엣지로 연결된 노드들(개별요소들의 집합) 각 노드들은 value를 가지고 있고 차일드 노드 또한 가질 수 있다.

트리의 첫번째 노드를 root라 한다. 이 노드가 다른 노드와 연결되 있을경우 root는 부모 노드 이고 연결된 노드는 자식노드이다.

트리의 노드들은 모두 엣지라 불리는 링크들로 연결 되있다. 우리가 노드 관계를 어떻게 다룰지에있어서 매우 중요한 요소이다.

'leafs'는 트리의 마지막 노드이다. 혹은 자식이 없는 노드들이다. 

'Height' : 마지막 노드까지의 가장 긴 길이 

'Depth' : root까지의 노드의 깊이

 

B-Tree

B-Tree vs BINARY Tree

B-Tree는 자식노드를 두개만 가질수 있는 이진 트리를 확장하여 더 많은 자식 노드를 갖게함

대용량 데이터를 위한 구조

스스로 균형을 맞추는 트리(일부공간을 낭비할 가능성 있음)

노드 자료수가 N이면, 자식의 수는 N+1이다

각 노드의 자료는 정렬된 상태

노드의 자료의 왼쪽 서브트리는 부모자료보다 작은 값, 오른쪽 서브트리는 부모자료보다 큰 값

아래부분에서 증가되는게 아니라 위의 부분에서 높이가 증가한다

삽입을 하는 경우 중간의 키를 기준으로 두가지 노드가 나뉘어 지게 된다.(가운데 키를 부모로 올림)

 

 

root노드는 적어도 2개이상의 자식

각 내부노드의 자식노드는 M/2 이상 M이하이다 (M: 치수)

외부노드로 가는 경로의 길이는 모두 같다.(모두 같은 레벨)

입력자료는 중복될 수 없다.

 

 

 

<psuedo code>

 

 

Graph

인간의 뇌 중추신경

 

부모를 하나이상 가진 트리는 그래프가 가능하다.

연결되어 있는 객체 간의 관계를 표현 할수 있는 자료 구조

개체들의 집합인 V(vertex), 그리고 V를 서로 연결해주는 E(edge)로 구성되어 있다.

무방향그래프, 방향그래프

그래프는 루프가 가능, root 존재하지 않음, Edge의 수는 Vertex에 영향을 받지 않는다.