🖇️ 트리 구조
1. 트리 구조란?
트리 구조는 위에 사진과 같이 하나의 뿌리로부터 시작되어서 가지가 여러 갈래로 뻗어있는 자료 구조를 말한다. 예를 들면 토너먼트 대진표라고 생각하면된다. 아래에서부터 차례로 올라가서 가장 꼭대기까지 가는것이 토너먼트이다. 트리구조는 반대로 위의 뿌리 노드 부터 시작해서 아래로 내려가는 구조이다.
2. 트리 용어 정리
-
노드(Node) : 트리 구조를 이루는 모든 개별 데이터
-
루트 노드 : 부모가 없는 최상위 노드
-
단말 노드 : 자식이 없는 노드
트리 에서는 부모와 자식 관계가 성립한다.
-
깊이 : 루트 노드에서의 길이
-
레벨: 트리 구조에서 같은 깊이를 가진 노드를 묶은 것
-
높이 : 리프 노드를 기준으로 해당 노드까지 떨어진 정도
깊이의 길이란 출발 노드에서 목적지 노드까지 거쳐야하는 간선의 수를 의미하며 높이는 루트 노드에서 가장 깊은 노드까지의 길이를 의미한다. 따라서 예를 들면 2번과 3번은 깊이와 레벨,높이는 각각 1,2,2 이다.
🖇️ 트리 종류
1. 이진탐색트리
- 각 노드에 값 존재
- 값들의 전순서 존재
- 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져있음
- 노드의 오른쪽 서브트리에는 그노드의 값보다 큰 값들을 지닌 노드들로 이루어져있음
2. 이진트리 종류
-
정 이진트리 - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
-
완전 이진트리 - 왼쪽 자식 노드부터 채워지며 마지막 레벨을 제외하고는 모든 자식노드가 채워져있는 트리
-
포화 이진트리 - 모든 노드가 0개 혹은 2개의 자식노드를 가지며 모든 리프노드가 똑같은 레벨에 있는 경우의 트리
-
균형 이진트리 - 모든 노드의 왼쪽과 오른쪽의 하위 트리와의 높이가 1이상 차이가 나지 않는 이진 트리 구조
🖇️ 이진 탐색 트리 구현
// treeNode 클래스를 만들어 노드의 뼈대를 만들어준다.
class insertNode {
constructor() {
this.root = null;
}
// insertNode 클래스를 만들어 root를 설정해준다.
insert(data) {
let node = new treeNode(data);
// 루드가 설정되어 있지 않다면 루트를 node로 만들어 준다. node는 treeNode()에서 뼈대를 받아온다.
if(!this.root) {
this.root = node;
return this;
}
// 비교를 위해 current 를 설정해 준다.
let current = this.root;
// current가 true 라면 while문을 돌면서 data와 지금 현재 data인 current data를 비교한다.
while (current) {
// 중복된 값은 어떤 결과를 리턴하지 않는다.
if(data === current.data) {
return;
}
// data가 current data(기준) 보다 작다면 왼쪽에 넣어준다.
if(data < current.data) {
if(!current.left) {
current.left = node;
break;
}
// 이제 current data(기준)는 왼쪽의 data로 준다.
current = current.left;
}
// data가 기준 data(current data) 보다 크다면 오른쪽에 넣어준다.
if(data > current.data) {
if(!current.right) {
current.right = node;
break;
}
// 이제 current data(기준)는 오른쪽 data로 준다.
current = current.right;
}
}
}
}
let nums = new insertNode();
nums.insert(10);
nums.insert(5);
nums.insert(11);
nums.insert(3);
nums.insert(6);
console.log(nums)
// insertNode {
// root: treeNode {
// data: 10,
// left: treeNode { data: 5, left: 3, right: 6 },
// right: 11
// }
// }참고
개발자가 되기 위한 1인