Tree 구조
트리는 노드로 이루어진 비선형 자료 구조
데이터의 요소들은 단순히 나열하는게 아닌 부모와 자식의 관계로 계층적인 구조이다
그래프의 한 종류이며 사이클이 없다
- node : 트리를 구성하는 요소
- Edge : 간선으로 트리를 구성하는 노드와 노드를 연결하는 선
- Root Node : 최상의 계층에 노드로 부모노드가 없다 그림에서 A라고 볼 수 있다
- level : 트리의 특정 깊이를 가지는 노드의 집합
- degree : 하위 트리의 갯수 / 간선의 수 각 노드 가 가진 가지 수
- leaf Node: 단말 노드로 자식이 없는 노드
- internal Node : 단말노드를 제외한 모든 노드 즉 루트노드 또한 포함
Tree의 종류
이진트리 : 트리를 구성 하는 노드의 최대 차수(degree)가 갯수가 2개인 노드들로 구성된 트리
- 이진트리 level n 에서 가질 수 있는 최대 노드의 갯수는 2^n
이진트리 안에서도 3종류로 나뉘는데
1. 완전 이진 트리 Complete
2. 포화 이진 트리 PerFact
3. 전 이진 트리 Full
완전 이진 트리(complete)
- 트리의 모든 높이에 노드가 꽉 차있고 이진트리 마지막 레벨을 제외하고 모든 레벨이 채워져 있다
- 마지막 레벨은 꽉 차있지 않아도 되지만 노드가 왼쪽에서 오른쪽으로 채워져야함
- 마지막 레벨 n에서 1~ 2n-1개의 노드를 가질 수있다
- 완전 이진트리는 배열을 사용해 효율적으로 표현 가능함
전 이진 트리(Full)
- 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
포화 이진 트리(Perfact)
- 전 이진트리면서 완전 이진트리이다
- 모든 말단 노드는 같은 높이 이며 마지막 단계에서 노드 갯수는 최대가 되야함
- 모든 내부 노드는 두개의 자식노드를 가진다
- 모든 말단 노드는 동일한 깊이 또는 레벨을 갖는다
이진트리 순회
1.중위 순회
왼쪽트리 -> 루트노드 -> 오른쪽트리
4-2-5-1-3
루트 노드 가운데
2.후위 순회
왼쪽트리 -> 오른쪽트리 -> 루트노드
4-5-2-3-1
루트노드가 마지막
3.전위 순회
루트노드 -> 왼쪽트리 -> 오른쪽트리
1-2-4-5-3
루트 노드가 첫번째
Heap
힙은 완전이진트리를 기본으로 한 자료구조
1. 일반적으로 배열을 사용하여 구현함
2. 완전이진트리 최댓값 및 최솟값을 찾아내는 연산
3. A가 B의 부모노드 이면 A의 키값과 B의 키값 사이에는 대소관계가 성립함
Heap의 종류
- 최대 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 큰 힙
- 최소 힙 : 부모노드의 키값이 자식노드의 키값보다 항상 작은 힙
- 키값은 대소관께는 오로지 부모노드와 자식노드 간에만 성립하며 특히 형제사이에는 대소관계가 필요없음
마지막으로 Tree를 코드를 만들기
const TreeNode = function(value){
this.value = value
this.children = []
}
TreeNode.prototype.insert = function(value){
let node = new TreeNode(value)
this.children.push(node)
}
TreeNode.prototype.contain = function(value){
if(this.value === value){
return true
}
for(let el of this.children){
if(el.contains(value)){
return true
}
}
return false
}