자바스크립트를 이용하여 트리
와 traverse
, searching
을 구현해 봅시다.
class TreeNode {
data
children
constructor(data) {
this.data = data
this.children = []
}
}
class BinaryTree {
data
left
right
constructor(data) {
this.data = data
this.left = null
this.right = null
}
}
왼쪽 가지 -> 현재 노드 방문-> 오른쪽 가지 순서대로 노드를 방문하고 출력
구체적으로,
1. 현재 노드의 왼쪽 가지가 있다면, 왼쪽 가지로 탐색
2. 현재 노드의 왼쪽 가지가 없다면, 현재 노드 방문
3. 현재 노드 방문 후, 오른쪽 가지가 있다면, 오른쪽 가지 탐색
4. 현재 노드에 대한 서브트리 탐색이 끝나면, 부모 노드에 대해2번
재귀적으로 실행
const inOrderTraversal = (node) => {
if (node !== null) {
if (node.left !== null) inOrderTraversal(node.left)
visit(node)
if (node.right !== null) inOrderTraversal(node.right)
}
}
현재 노드 방문 -> 왼쪽 가지 -> 오른쪽 가지
const preOrderTraversal = (node) => {
if (node !== null) {
visit(node)
if (node.left !== null) preOrderTraversal(node.left)
if (node.right !== null) preOrderTraversal(node.right)
}
}
왼쪽 가지 -> 오른쪽 가지 -> 현재 노드 방문
const postOrderTraversal = (node) => {
if (node !== null) {
if (node.left !== null) postOrderTraversal(node.left)
if (node.right !== null) postOrderTraversal(node.right)
visit(node)
}
}
왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
O(logN) 탐색시간 이점 (균형 잡힌 경우)
BST insert
함수 구현
class BST {
root
constructor(root = null) {
this.root = root
}
insert(data, currentNode) {
if (currentNode === null) currentNode = new BinaryTree(data)
else if (data < currentNode.data) {
if (currentNode.left === null) currentNode.left = new BinaryTree(data)
else this.insert(data, currentNode.left)
} else if (data > currentNode.data) {
if (currentNode.right === null) currentNode.right = new BinaryTree(data)
else this.insert(data, currentNode.right)
}
}
}
올바른 BST 인지 테스트
class BinaryTree {
data
left
right
constructor(data) {
this.data = data
this.left = null
this.right = null
}
}
const visitArr = []
const visit = (node) => {
console.log(node.data)
}
const postOrderTraversal = (node) => {
if (node !== null) {
if (node.left !== null) postOrderTraversal(node.left)
if (node.right !== null) postOrderTraversal(node.right)
visit(node)
}
}
class BST {
root
constructor(root = null) {
this.root = root
}
insert(data, currentNode) {
if (currentNode === null) currentNode = new BinaryTree(data)
else if (data < currentNode.data) {
if (currentNode.left === null) currentNode.left = new BinaryTree(data)
else this.insert(data, currentNode.left)
} else if (data > currentNode.data) {
if (currentNode.right === null) currentNode.right = new BinaryTree(data)
else this.insert(data, currentNode.right)
}
}
}
const bst = new BST(new BinaryTree(8))
bst.insert(4, bst.root)
bst.insert(10, bst.root)
bst.insert(2, bst.root)
bst.insert(6, bst.root)
bst.insert(20, bst.root)
postOrderTraversal(bst.root)
출력 (
postOrderTraversal
)
2
6
4
20
10
8
class MinHeap {
heap
constructor() {
this.heap = [null]
}
heapPush(value) {
this.heap.push(value)
let currIdx = this.heap.length
let parentIdx = Math.floor(currIdx / 2)
while (this.heap[currIdx] > this.heap[parentIdx] || currIdx === 1) {
;[this.heap[currIdx], this.heap[parentIdx]] = [this.heap[parentIdx], this.heap[currIdx]]
currIdx = parentIdx
parentIdx = Math.floor(currIdx / 2)
}
}
heapPop() {
this.heap[1] = this.heap.pop()
let currIdx = 1
let leftChildIdx = currIdx * 2,
rightChildIdx = currIdx * 2 + 1
while (leftChildIdx <= this.heap.length) {
// left, right child 존재
if (rightChildIdx <= this.heap.length) {
if (this.heap[currIdx] > this.heap[leftChildIdx]) {
;[this.heap[currIdx], this.heap[leftChildIdx]] = [this.heap[leftChildIdx], this.heap[currIdx]]
currIdx = leftChildIdx
leftChildIdx = currIdx * 2
rightChildIdx = currIdx * 2 + 1
} else if (this.heap[currIdx] > this.heap[rightChildIdx]) {
;[this.heap[currIdx], this.heap[rightChildIdx]] = [this.heap[rightChildIdx], this.heap[currIdx]]
currIdx = rightChildIdx
leftChildIdx = currIdx * 2
rightChildIdx = currIdx * 2 + 1
} else break
} else {
// left child 만 존재
if (this.heap[currIdx] > this.heap[leftChildIdx]) {
;[this.heap[currIdx], this.heap[leftChildIdx]] = [this.heap[leftChildIdx], this.heap[currIdx]]
currIdx = leftChildIdx
leftChildIdx = currIdx * 2
rightChildIdx = currIdx * 2 + 1
} else break
}
}
}
}