날이 좋아서 자전거를 잠깐 타고 왔는데 저녁먹고 너무 졸려서 30분만 잔다고 알람을 맞춰놨다.
역시, 3시간을 자버렸다.
잠자리를 뒤척이며 새벽에 잠들지 못할 미래의 나에게 미안하지만
오랜만에 잠다운 잠을 자서 피곤이 풀렸다!
그래도 얼른 블로깅을 마치고 잠자러 가야겠다.
Graph
Tree
그래프의 한 종류
일방향 그래프
특징
내 생각엔 Tree 보단 Root에 가깝다.
(이게 Tree인지.. Root인지..)
부모 노드에서 시작해 자식노드로 뻗어 나가는 계층적 자료구조이기 때문이다.
그래서 싸이클이 존재할 수 없고 순서가 없기 때문에 비선형 구조이다.
첫 번째 노드에서 찾고자하는 노드까지 가는 방법은 딱 하나, 유일하다.
어디에 써?
컴퓨터 폴더, 조직도, 가계도, 대진표
내부 로직 구현
class Tree() {
constructor (value) {
this.value = value
this.children = [];
}
addChild(value) {
const childNode = new Tree(value) // Tree의 자식 노드를 먼저 만들고
this.children.push(childNode) // Tree의 자식 배열에 넣어준다
}
contains(value) {
if(this.value === value) { // 현재 value와 찾고자 하는 value가 같다면
retrun true; // true 반환
}
// 찾고자 하는 value가 현재 노드에 없다면
for(let i = 0; i < this.children.length; i++) { // 현재 노드의 자식 노드를 순회한다
let childNode = this.children[i]
if(childNode.contains(value)) { // 자식 노드에 contains메소드를 활용해 찾고자하는 value를 찾는다
return true; // 자식 노드에서 찾았다면 true를 반환한다
}
}
return false; // 전부 순회하면서 찾아도 찾고자하는 value가 없으면 false를 반환한다
}
}Binary Tree (이진 트리)
최대 2개의 자식 노드를 가진다.
출처: codestates
정 이진 트리
- 홀수개의 자식을 가질 수 없다.
- 0개 or 2개의 자식 노드를 가진다.
완전 이진 트리
- 부모 노드 -> 왼쪽 자식 노드 -> 오른쪽 자식노드 순서로 채워진다.
- 마지막 레벨을 제외하고 모든 노드가 가득 차 있어야 한다.
- 마지막 레벨은 왼쪽으로 몰려있어야 된다.
포화 이진 트리
- 정 이진트리이면서, 완전 이진 트리를 뜻 한다.
- 모든 레벨이 가득 채워져 있어야 한다. (전부 자식 2개씩)
- 모든 리프 노드의 레벨이 동등하다.
Binary Search Tree (이진 탐색 트리)
부모보다 작으면 왼쪽, 부모보다 크면 오른쪽
왜 써?
찾고자 하는 값을 굉장히 빠르게 찾을 수 있다.
up-down 게임을 생각해보자.
0~100까지 숫자를 골라 출제자가 생각하고 있는 숫자를 맞추는 게임이다.
만약 출제자가 76을 생각하고 있다고 가정해보자.
40 -> up
그럼 0~40은 생각할 필요가 없어진다.
80 -> down
80~100은 배제해도 된다.
0부터 100까지 전부 순회하면서 찾을 필요 없이
찾고자하는 값을 이분하여 보다 빠르게 찾을 수 있다.
근데 값이 부모보다 계속 작거나 크면?
노드가 한쪽으로 몰려 이진 탐색 트리의 의미가 퇴색 될 수 있다.
이러한 불균형을 막기 위해 균형 이진 탐색 트리(Balanced Binary Search Tree)가 생겨났다.
균형 이진 탐색 트리란 부모와 자식의 대소 관계를 비교해 위치를 바꿔준다고 할 수 있다. (루트 노드는 고정)
출처: https://jackpot53.tistory.com/17
