# TIL 40 | Tree

pca0046ยท2021๋ 7์ 31์ผ
0

## Algorithm

๋ชฉ๋ก ๋ณด๊ธฐ
3/4

### What is a tree?

A data structure that consists of nodes in a parent / child relationship

#### Binary Tree

• Every parent node has at most two children

#### Binary Search Tree

• Every node to the left of a parent node is always less than the parent
• Every node to the right of a parent node is always greater than the parent

#### Make a binary search tree

class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}

class BinarySearchTree {
constructor() {
this.root = null;
}
}

Inserting(Iteratively or Recursively)

• Create a new node
• Start at the root
• Check if there is a root, if not -the root now becomes that new node
• If there is a root, check if the value of the new node is greater than or less than the value of the root
• If it is greater
• Check to see If there is a node to the right
• If there is, move to that node and repeat these steps
• If there is not, add that node as the right property
• If it is less
• Check to see If there is a node to the left
• If there is, move to that node and repeat these steps
• If there is not, add that node as the left property
insert(value) {
let newNode = new Node(value);
if (this.root === null) {
this.root = newNode;
return this;
} else {
let current = this.root;
while (true) {
if (value === current.value) return undefined;
if (value < current.value) {
if (current.left === null) {
current.left = newNode;
return this;
} else {
current = current.left;
}
} else if (value > current.value) {
if (current.right === null) {
current.right = newNode;
return this;
} else {
current = current.right;
}
}
}
}
}

Finding a node

• Starting at the root
• Check if there is a root, if not - we're done searching
• It there is a root, check if the value of the new node is the value we are looking for. If we found it, we're done
• If not, check to see if the value is greater than or less than the value of the root
• If is greater
-Check to see if there is a node to the right
- If there is, move to that node and repeat these steps
- If there is not, we're done searching
-If is less
-Check to see if there is a node to the left
- If there is, move to that node and repeat these steps
- If there is not, we're done searching
find(value) {
if (this.root === null) return false;
let current = this.root;
let found = false;
while (current && !found) {
if (value < current.value) {
current = current.left;
} else if (value > current.vlue) {
current = current.right;
} else {
found = true;
}
}
if (!found) return undefined;
return current;
}

contains(value) {
if (this.root === null) return false;
let current = this.root;
let found = false;
while (current && !found) {
if (value < current.value) {
current = current.left;
} else if (value > current.value) {
current = current.right;
} else {
return true;
}
}
return false;
}

BFS

• Create a queue(this can e an array) and a variable to store the values of nodes visited
• Place the root node in the queue
• Loop as long as there is anything in the queue
• Dequeue a node from the queue and push the value of the node into the variable that sotres the nodes
• If there is a left property on the node dequeued - add it to the queue
• If there is a right property on the node dequeued - add it to the queue
• return the variable that stores the values
BFS() {
let node = this.root;
let data = [];
let queue = [];
queue.push(node);

while (queue.length) {
node = queue.shift();
data.push(node.value);
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
return data;
}

DFS (Depth First Search)
(1) Preorder - recursively

• Create a variable to store the values of nodes visited
• Store the root of the BST in a variable called current
• Write a helper function which accepts a node
• Push the value of the node to the variable that stores the values
• If the node has a left property, call the helper function with the left property on the node
• If the node has a right property, call the helper function with the right property on the node
DFSPreOrder() {
let data = [];
let current = this.root;
function traverse(node) {
data.push(node.value);
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
}
traverse(current);
return data;
}

(2) Postorder - recursively

• Create a variable to store the values of nodes visited
• Store the root of the BST in a variable called current
• Write a helper function which accepts a node
• If the node has a left property, call the helper function with the left property on the node
• If the node has a right property, call the helper function with the right property on the node
• Push the value of the node to the variable that stores the values
• Invoke the helper function with the current variable
DFSPostOrder() {
let data = [];
let current = this.root;
function traverse(node) {
if (node.left) traverse(node.left);
if (node.right) traverse(node.right);
data.push(node.value);
}
traverse(current);
return data;
}

(3) InOrder - recursively

• Create a variable to store the values of nodes visited
• Store the root of the BST in a variable called current
• Write a helper function which accepts a node
• If the node has a left property, call the helper function with the left property on the node
• Push the value of the node to the variable that stores the values
• If the node has a right property, call the helper function with the right property on the node
• Invoke the helper function with the current variable
DFSInOrder() {
let data = [];
let current = this.root;
function traverse(node) {
if (node.left) traverse(node.left);
data.push(node.value);
if (node.right) traverse(node.right);
}
traverse(current);
return data;
}

### Big O of BST

Not guaranteed

• Insertion - O(log n)
• Finding - O(log n)

### BFS & DFS which one is better?

์๊ฐ ๋ณต์ก๋ ์ธก๋ฉด์์ BFS ์ DFS ๋ ํฌ๊ฒ ์ฐจ์ด๊ฐ ์๋ค. ๋ค๋ค ๋ฐ์ดํฐ ์์ด ๋์ด๋ ์๋ก ์คํ ํ์๋ ์ฆ๊ฐํ๊ธฐ ๋๋ฌธ์ด๋ค. tree์ ๊น์ด๋ณด๋ค ๊ฐ๋ก ๊ธธ์ด๊ฐ ๋์ ๊ฒฝ์ฐ DFS๊ฐ ๋ ์ ์ ํ๋ค. ๊ณต๊ฐ ๋ณต์ก๋๊ฐ BFS๋ณด๋ค ์๊ธฐ ๋๋ฌธ, BFS์ ๊ฒฝ์ฐ์๋ ํ์์ด ํ์ํ ํ์  ๋ธ๋๋ฅผ ๋ชจ๋ ํ์ ์ ์ฅํด๋์ผํ๊ธฐ ๋๋ฌธ์ ํธ๋ฆฌ์ ๊ฐ๋ก ๊ธธ์ด๊ฐ ๋์ด๋  ์๋ก ์ฉ๋์ ๋ง์ด ์ฐจ์งํ๋ค. ์ด ๋ฐ๋์ ๊ฒฝ์ฐ, ์ฆ ๊ฐ๋ก๊ธธ์ด๊ฐ ์ข๊ณ  ๊น์ด๊ฐ ๊น์ ๊ฒฝ์ฐ์๋ BFS๊ฐ ๋ ์ ์ ํ๋ค. ๊น์ด๊ฐ ๊น์ด์ง์๋ก DFS์ ์ฌ๊ท๊ฐ ์๋ํ๋ฉด์ ๊ธฐ์ตํด์ผํ  ์์๋ค์ด ๋ง์์ง๊ธฐ ๋๋ฌธ์ด๋ค. BFS ๋ ํ์ ์ ์ฅํด๋๊ณ  ๋ค ๋ ๋ ค๋ฒ๋ฆฌ๋ฉด์ ์ด๋ํ๊ธฐ ๋๋ฌธ์ ์ฉ๋ ์ฐจ์ง๊ฐ ๋ํ๋ค.

### DFS inorder, preorder which one is better?

-BST ํ์ํ  ๋ inorder๋ก ํ์ํ๋ฉด ์ค๋ฆ์ฐจ์์ผ๋ก sorting๋ ๋ฐ์ดํฐ๋ฅผ ์ป์ ์ ์๋ค.
-BST ํ์ํ  ๋ preorder๋ก ํ์ํ๋ฉด ํธ๋ฆฌ ๋ชจ์์ด ๊ทธ๋๋ก ๋ด๊ธด ๋ฐ์ดํฐ๋ฅผ ์ป์ ์ ์๋ค. root data์์ ํ์์ด ์์๋๊ธฐ ๋๋ฌธ