코드스테이츠 소프트웨어엔지지어링 부트캠프 +39일

오늘한것

공포의 자료구조,

 

공포의 자료구조

Stack :

먼저 들어간게 나중에 나온다. FILO, LIFO 

예를들면 뒤로가기가 있다.

사용되는 메소드는 push(), pop() 등이 있다.

 

stack에 자료가 없을 때 pop()하면 stack underflow 오류가, stack 크기 이상의 자료를 push 하면 stack overflow 오류가 생긴다.

 

Queue :

먼저 들어간게 먼저 나온다. FIFO, LILO

입력한 순서대로 처리할 때 주로 사용된다.

 

FIFO 구조이기 때문에 데이터를 추가,삭제 하다보면 앞쪽은 비어있고 뒤에 값만 남아 있을때가 있는데 이때도 꽉 찼다고 인식한다.

 

 

Tree : 

Root 라는 꼭짓점을 시작으로 여러개의 데이터를 간선(edge)로 연결한다.

데이터를 노드라고 하며 두 개의 노드가 상하 계층으로 부모/자식 관계를 가진다.

자식이 없는 노드는 나뭇잎이라는 뜻에서 leaf Node 라고 한다

코드스테이츠 자료

• 깊이 : 트리 구조에서는 root로부터 하위 계층의 특정 노드까지의 깊이를 표현할 수 있다. 위 그림에서 level1,2,3,4로 표현했다. root와 같은 층에 있는 A, level1의 깊이는 0이다.
• 레벨 : 같은 깊이에 있는 노드들을 같은 레벨이라고 표현한다. 같은 레벨에 나란히 있는 노드를 형제 노드라고 한다.
• 높이 : leaf Node 를 기준으로 root까지의 높이. leaf Node 와 직간접적으로 연결된 노드의 높이를 표현하며 leaf Node의 높이를 0으로 한다. 위 그림에서 H,I,J, F, E의 높이는 0 이고 D,J의 높이는 1이다. B,C의 높이는 2이다. 부모노드는 자식노드의 가장 높은 높이값에 +1 한 값이다.
• 서브트리 : 트리구조를 갖춘 작은 트리들을 말한다.

다음그림은 트리구조의 실사용 예제이다.

코드스테이츠 자료