Trees
비순환 그래프의 한 종류.
Root Node → Parent Node → Child Node 등으로 로 구성된 계층적인 자료구조.
ex. 컴퓨터 디렉토리, 폴더
abstract syntax tree here, well, this is how programs or code is usually being run. Nodes can contain any type of information that we want.
Binary Trees
Perfect Binary Tree
완전이진트리 completely filled. 모든노드가 2개씩 자식을 가짐 (2갈래)
-
n단계 레벨에선 2^(n-1) 만큼 노드를 가짐.
-
마지막 레벨 노드 sum = 이전 모든 노드의 합 + 1
마지막 레벨에 전체 노드의 1/2가 있다는 말이다.
즉, 모-든 노드를 방문하지 않고 기준을 정해서 조회할 수 있다는 것.
ex. 4레벨에 있는 노드 수 = 이전노드 다 합친거 + 1
2⁴ = (1 + 2 + 2² + 2³) + 1Full Binary Tree
포화이진트리 zero or two children, but never one child. 완전이진트리에 포함된다.
O(log N)
Devide and Conquer !
Traversing and figuring out using O(log N) again where we should place the item.
Binary tree를 순회하는 최단 루트를 찾는 시간복잡도.
요소 전체를 순회하지 않고, 값의 크기를 기준으로 특정 위치에서부터 최소한의 탐색을 할 수 있다.
- lookup : O(log N)
- insert : O(log N)
- delete : O(log N)
BST: Binary Search Tree
Hash Table도 시간복잡도가 O(1)이었지만(collision이 있기야 하지만), Binary Search Tree가 훨씬 베리굳이다.
왜냐하면 Hash Table은 데이터간의 연결고리 없이 단순히 key, value쌍으로 이루어진 자료구조였지만, Binary Search Tree는 pointer의 기능을 가진 .right, left 속성으로 노드간의 계층 관계를 확인할 수 있기 때문에 검색이 굉장히 매우 효율적이고 빠르다!
(Big O그래프에서 O(log N)은 O(1)과 비슷한 기울기를 가진다.)
그리고 BinarySearch Tree에는 몇가지 규칙이 존재한다.
BSearch Regulations
B1. Node기준으로 오른쪽에 있는 노드값이 더 커야 한다.
전체적으로 보면 왼쪽라인은 값이 감소하고, 오른쪽라인은 값이 증가한다.
크기를 기준으로 오/왼 중에 택1하며 찾기 때문에, 값을 조회하는 것이 빠르다!
B2. 각 노드는 최대 2개의 자식노드를 가질 수 있다.
Balanced VS Unbalanced BST
keep getting added to the right, to the right
Unbalancd한 트리구조를 만들면, loop를 도는 O(n)의 Singly Linked List와 다름없게 되고, 짱 빠르고 좋은 O(log N)을 사용할 수 없게 된다.
그래서 우리는 Balanced BST를 만들어야 한다.
이 파트가 복잡하고 설명하긴 시간길어져서 면접엔 잘 안나온다 함. 😗
💡 BST Class
# remove 돌았나?! # else... # difficult # 🤮 🤮 🤮 
class Node {
constructor(value) {
this.left = null;
this.right = null;
this.value = value;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return this;
}
let currentNode = this.root;
while (true) {
if (value < currentNode.value) {
if (!currentNode.left) { //있을때가지 반복.
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left; // 업뎃은여기서
}
if (value > currentNode.value) {
if (!currentNode.right) { //있을때가지 반복.
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right; // 업뎃은여기서
}
}
}
lookup(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
while (currentNode) {
if (value === currentNode.value) {
return currentNode;
}
if (value < currentNode.value) {
currentNode = currentNode.left
} else {
currentNode = currentNode.right;
}
}
return false;
}
remove(value) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while (currentNode) {
if (value < currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (value > currentNode.value) {
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.value === value) {
// 드디어 타겟노드 찾음.
// 하지만 옵션이 여러가지 있다....!
// (1) No right child Node
if (currentNode.right === null) {
if (parentNode === null) { // target이 root일때
this.root = currentNode.left; // 타겟(루트)왼쪽이 루트가 됨
} else {
// 45
// 16 63
// 10 58
if (currentNode.value < parentNode.value) {
// 타겟노드가 부모노드 기준 왼쪽일 때
parentNode.left = currentNode.left;
} else if (currentNode.value > parentNode.value) {
// 타겟노드가 부모노드 기준 오른쪽일 때
parentNode.right = currentNode.left;
}
}
// (2) Right Child which dosent have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if (parentNode === null) { // target이 root일때
this.root = currentNode.right;
} else {
// ?
if (currentNode.value < parentNode.value) {
// 타겟노드가 부모노드 기준 왼쪽일 때
parentNode.left = currentNode.right;
} else if (currentNode.value > parentNode.value) {
// 타겟노드가 부모노드 기준 오른쪽일 때
parentNode.right = currentNode.right;
}
}
// (3) Right Child has a left child
} else {
//find this Right Child's left most child
let leftmost = currentNode.right.left;
let leftmostParent currentNode.right;
while (leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if (parentNode === null) {
this.root = leftmost;
} else {
if (currentNode.value < parentNode.value) {
parentNode.left = leftmost;
} else if (currentNode.value > parentNode.value) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
const tree = new BinarySearchTree();
tree.insert(9);
tree.insert(4);
tree.insert(20);
tree.insert(6);
tree.insert(15);
tree.insert(1);
tree.insert(170);
// console.log(tree.lookup(4))
console.log(tree.remove(20));
console.log(JSON.stringify(traverse(tree.root)));
// 9
// 4 20
// 1 6 15 170
function traverse(node) {
const tree = { value: node.value };
tree.left = node.left === null
? null
: traverse(node.left);
tree.right = node.right === null
? null
: traverse(node.right);
return tree;
}
Binary Heap
왼쪽노드 보다 오른쪽노드 값이 커야 했던 BST와 달리 그저 왼쪽에 먼저 노드가 삽입되고, 그다음 비어있는 오른쪽에 노드가 삽입되는 구조의 트리.
그래서 unbalance하지 않는, 비어있는 노드 없이 꽉찬 Binary Tree 구조를 보여준다. => 메모리를 굉장히 효율적이고 컴팩트하게 사용할 수 있다.
top level has a greater value than every note on the next level down
하위레벨로 내려갈수록 값이 작아진다. 그래서 max / min 값을 찾기에 유용하다.
😗 자바스크립트 엔진의 메모리힙과는 다른 거임!! 이름에만 힙이 들어갈 뿐 !! binary heaps are really, really great at doing comparative operations.
Heaps are actually used a lot in data storage, priority queues, sorting algorithms.
- lookup : O(n)
- insert : O(1)
greatO(log N)wost - delete : O(1)
greatO(log N)wost
부모노드보다 큰 값을 삽입 / 삭제 하면 레벨간에 switch가 일어난다.
Priority Queues
Priority Queues는 Binary Heap트리 구조로 구현된다.
엘리먼트 마다 우선순위를 가지고 있어서 우선순위가 높을수록 더 큰 value를 가질 수 있고 먼저 out된다. value가 클수록 상위로 갈 수 때문에, 우선순위가 높은 vip노드가 상위레벨에 있게 된다.
그래서 우선순위 높은애가 들어오면 우선순위 낮은 애가 자리를 비켜줘야 한다.
ex. 롯데월드 매직패스 가진 사람들 우선순위가 높아서 먼저 입장하는 것처럼.
BST vs Binary heaps in Priority
Although searching through a binary heap is a lot slower than a binary search tree
바이너리힙자체는 BST에 비해 lookup이 느리지만,
binary heaps in Priority에서는 우선순위 특성상 insert와 min / max 값을 찾는비교연산이 굉장히 빠르다.
또한 메모리도 빈 곳 없이 flexible하게 사용할 수 있다.
Trie
Trie is a specialized tree used in searching most often with text
문자열을에 특화된 트리구조로써, root노드는 비어있고, 그 아래에 특정 prefix를 가진 노드들이 있다.
prefix노드 아래에 prefix로 시작하는 문자열들이 단어의 length만큼 연결되어 있다.
검색할 때 단어의 길이만큼 시간이 걸리기 때문에 시간복잡도는 O(length of word) 이 된다.
=> BST, HashTable을 능가하는 검색능력을 가진다.
모든 단어를 개별적으로 저장하는 것이 아니라, 하나의 prefix노드 아래에 연관된 노드가 있기 때문에 메모리도 효율적으로 사용할 수 있다.
ex. 사전검색, 검색어 자동완성 알고리즘, IP Routing
- lookup : O(length of word)
Graph
노드들이 서로서로 연결된 자료구조. 노드를 꼭지점 vertex 라고도 부른다.
Graphs are built on top of other data structures.
Tree, Linked List등도 Graph에 속한다.
ex. 네트워크, 구글맵, World Wide Web
데이터간의 관계를 다루기엔 그래프만한게 없다. 😁
하지만 확장하기엔 매우 어렵다. 하지만 우리에겐 라이브러리가 있다!
그래프 자료구조 표현 방법
1. Directed vs. Undirected
Edge(Link)
-
한 방향으로만 이동 가능 : Directed Graphs.
이웃추가 -
쌍방향 이동 가능 : Undirected Graphs
서이추
2. Weighted vs Unweighted
Edge에도 데이터가 있는 형태의 그래프.
-
weighted : edge도 데이터 있음. 최적의 경로를 찾을 떄 사용.
ex. 구글맵 : 최단거리 찾기 -
unweighted : edge에 데이터 없음.
3. Cyclic vs. Acyclic
- Cyclic 노드가 연결되어서 다시 원래 위치로 돌아올 수 있는 순환구조
connected in a circular fashion.
You can go from one node to another to another and then back to that original node.
Cycle graphs are really common in especially weighted graphs such as Google Maps, because most of the time there is a way to get back.
- 비순환은 Acyclic
4. Directed Acyclic Graphs(DAG)
Directed + Acyclic + Unweighted
ex. 블록체인
💡 Graphs Class
Data expression
array object
Edge List Adjacent List Adjacent Matrix
// 2 ㅡ 0
// / \
// 1 ㅡ 3
**/* Edge List */**
const graph = [[0, 2], [2, 1], [1, 3], [3, 2]];
// [ [0<->2], [2<->1], ...[3<->2] ]
**/* Adjacent List */**
// 그래프[노드] = [이웃노드, 이웃노드...]
// 노드가 string이라면 객체로 만들면 됨. key: value
const graph = [[2], [2, 3], [0, 1, 3], [1, 2]];
// graph[0] = [2] // 노드 0과 연결된 노드 2가 값이 된다.
// graph[1] = [2, 3] // 노드 1과 연결된 노드 2, 3이 값이 된다.
// graph[2] = [0, 1, 3] // 노드 2과 연결된 노드 0, 1, 3이 값이 된다.
// graph[3] = [1, 2] // 노드 3과 연결된 노드 1, 2이 값이 된다.
**/* Adjacent Matrix */**
// only 0, 1
// connected ? 1 : 0
//=> array
const graph = [
[0, 0, 1, 0], //노드0: 노드 2와 연결됐으니 인덱스 2는 1
[0, 0, 1, 1], //노드1: 노드 2, 3이랑 연결됐으니 인덱스 2,3은 1
[1, 1, 0, 1], //노드2: 노드 1, 2, 3연결됐으니 인덱스 1,2,3은 1
[0, 1, 1, 0] //노드3: 노드 1, 2랑 연결됐으니 인덱스 1, 2는 1
];
//=> object
const graph = {
0: [0, 0, 1, 0],
1: [0, 0, 1, 1],
2: [1, 1, 0, 1],
3: [0, 1, 1, 0]
};
Class Implement
<// 3 -- 4 ---- 5
// | | |
// 1 -- 2 6
// \ /
// 0
class Graph {
constructor() {
this.numberOfNodes = 0; // NodeLength
this.adjacentList = {
};
}
addVertex(node) {
this.adjacentList[node] = [];
this.numberOfNodes++;
}
addEdge(node1, node2) {
//undirected Graph : point eachother
this.adjacentList[node1].push(node2);
this.adjacentList[node2].push(node1);
}
showConnections() { //check edge connection
const allNodes = Object.keys(this.adjacentList);
for (let node of allNodes) {
let nodeConnections = this.adjacentList[node];
let connections = "";
let vertex;
for (vertex of nodeConnections) {
connections += vertex + " ";
}
console.log(node + "-->" + connections);
}
}
}
const myGraph = new Graph();
// 3 -- 4 ---- 5
// | | |
// 1 -- 2 6
// \ /
// 0
myGraph.addVertex('0');
myGraph.addVertex('1');
myGraph.addVertex('2');
myGraph.addVertex('3');
myGraph.addVertex('4');
myGraph.addVertex('5');
myGraph.addVertex('6');
myGraph.addEdge('3', '1');
myGraph.addEdge('3', '4');
myGraph.addEdge('4', '2');
myGraph.addEdge('4', '5');
myGraph.addEdge('1', '2');
myGraph.addEdge('1', '0');
myGraph.addEdge('0', '2');
myGraph.addEdge('6', '5');
myGraph.showConnections();
//Answer:
// 0-->1 2
// 1-->3 2 0
// 2-->4 1 0
// 3-->1 4
// 4-->3 2 5
// 5-->4 6
// 6-->5
