11월17일 TIL

임덤덤·2022년 11월 17일

TIL

🔥 목차 🔥

1. 자료구조에 대한정리 ( Stack, Queue )
2. Tree

🧐 그렇다면 꼬! 🧐

💡 자료구조에 대한 정리 ( Stack, Queue )

이전에 Stack과 Queue에 대해서는 정리한적이 있으니 간단하게 리마인드로 정리하고 넘어가려고 한다
- 우선 자료구조에 대해서 먼저 정리 해보도록 하겠다
자료구조
- 대부분의 자료구조는 특정한 상황에 놓인 문제를 해결하는데 특화되어 있다
- 그말은 많은 자료구조를 알아두면 어떤 상황이 닥쳤을때 적합한 자료구조를 빠르고 정확하게 적용해서 문제해결을 할 수 있다는 말이된다

Steak

First In Last Out
스택 구조는 조회가 필요하지 않고 해당 자료구조를 사용해서 데이터 저장,검색이 빠르고 최상위 블록에서 데이터를 저장하고 검색하면 된다는 장점이 있음
데이터는 하나씩 넣고 뺄수있음
하나의 입출력 방향을 가지고 있음
저장되는 데이터는 유한하고 정적이여야 함

Queue

First In First Out
데이터는 하나씩 넣고 뺄수 있음
두개의 입출력 방향을 가지고 있음(추가,제거)
대부분 데이터를 주고받을때 장치 사이에서 존재하는 속도차이, 시간차이를 극복하기 위해 임시기억장치의 자료구조로 Queue를 사용함
이걸 통틀어서 버퍼라고함(버퍼링의 버퍼)

💡 Tree

노드들이 나무가지처럼 연결된 비선형 계층적 자료구조라고 한다
말로봐서는 잘 이해가 안 갈 수있으니 사진을 첨부하려고 한다
위 사진처럼 나무를 뒤집어 놓은 모양과 유사하다
트리는 다른 하위트리가 있고 그 하위 트리 안에는 또 하위 트리가 있는 재귀적 자료구조의 형태도 띄고있다

🎄 트리 구조에서 사용되는 기본 용어

노드(Node)
- 트리를 구성하는 기본요소
  - 위 그림에서는 숫자가 써져있는 원형 하나하나가 노드다
- 노드는 키 또는 값과 하위 노드에 대한 포인터를 가지고있다
간선(Edge)
- 노드와 노드간의 연결선
루트 노드(Root Node)
- 트리 구조에서 부모가 없는 최상위 노드
  - 위 사진으로 봤을때 1번 루트노드임
부모 노드(Parent Node)
- 자식 노드를 가진 노드
  - 위 사진에서는 2,3,6이 부모노드임
자식 노드(Child node)
- 부모 노드의 하위 노드
형제 노드(Sibling node)
- 같은 부모를 가지는 노드
  - 위 사진에서는 4,6 / 10,7
외부노드(external node, outer node) , 단말노드 (Terminal node), 리프노드(leaf node)
- 자식이 없는 노드
  - 위 사진에서는 4, 7 , 10, 15
내부노드(internal node, inner node), 비 단말 노드(non-terminal node), 가지노드(branch node)
- 자식 노드 하나 이상 가진 노드
  - 위 사진에서는 1, 2, 3, 6
깊이(depth)
- 루트에서 어떤 노드까지의 간선(Edge)수
- 루트의 노드 깊이: 0
- 4의 노드깊이: 2
높이(height)
- 어떤 노드에서 리프 노드 까지의 가장 긴 경로의 간선(Edge) 수
- 리프 노드의 높이: 0
- 1의 노드의 높이: 3
Level
- 루트에서 어떤 노드까지의 간선(Edge)수
Degree
- 노드의 자식의 수
Path
- 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
Path Length
- 해당 경로에 있는 총 노드의 수
Size
- 자신을 포함한 자손 노드의 수
Width
- 레벨에 있는 노드의 수
Breadth
- 리프 노드의 수
Distance
- 두 노드 사이의 최단 경로에 있는 간선(Edge)의 수
Order
- 부모 노드가 가질 수 있는 최대 자식의 수

🎄Tree 구조의 특징

하나의 루트 노드와 0개 이상의 하위 트리로 구성 되어있음
데이터를 순차적으로 저장하지 않기 때문에 비선형 자료구조임
트리 내에 또 다른 트리가 있는 재귀적 자료구조임
단순 순환(Loop)를 가지지 않고 연결된 무방향 그래프 구조임
노드간의 부모자식 관계를 가지고 있는 계층형 자료구조이고 모든 자식 노드는 하나의 부모노드만을 가짐
노드가 n개인 트리는 항상 n-1개의 간선(Edge)를 가짐

🎄Tree 구조의 종류

편향트리(skew tree)
- 모든 노드들이 자식을 하나만 가진 트리
- 왼쪽 방향으로 자식을 하나씩만 가질때 left skew tree
- 오른쪽 방향으로 하나만 가질때 right skew tree라고 함
이진트리(Binary Tree)
- 각 노드의 차수(자식 노드)가 2 이하인 트리
이진 탐색 트리Binary Search Tree, BST)
- 순서화 되어있는 이진트리
- 노드의 왼쪽 자식은 부모의 값보다 작은 값을 가져야 하고
- 노드의 오른쪽 자식은 부모의 값보다 큰값을 가져야함
m원 탐색 트리(m-way search tree)
- 최대 m개의 서브 트리를 갖는 탐색 트리
- 이진 탐색 트리의 확장된 형태로 높이를 줄이기 위해 사용함
균형 트리(Balanced Tree, B-Tree)
- m원 탐색 트리에서 높이 균형을 유지하는 트리
- Height-Balanced M-Way Tree라고도 함