[자료구조] Trees
Trees
Array, LinkedList, Stack, Queue 와 달리 일직선 구조가 아니라 부모 자식 관계를 가지는 구조
Tree 의 종류
Binary Tree (이진 트리)
부모가 두 개의 자식 node 를 갖는 tree
Binary Search Tree (이진 검색 트리)
- “왼쪽 자식 < 부모 < 오른쪽 자식” 의 관계를 가지는 이진 트리
- 검색에 특화됨
- search 의 시간복잡도 : O(log N)
Tries (트라이)
- 어떠한 텍스트에서 문자열이 존재하는지 검색하는데에 최적화된 트리
- 기존 BST 에서는 각각의 node 에서 문자열을 또 하나씩 검색해야함
BST 에서 문자열 search 시간복잡도 : O (M log N)
(M : 문자열의 최대 길이) - Tries 에서 문자열 search 시간복잡도 : O (M)
첫 글자를 반복 저장할 필요가 없어 공간 효율도 좋다.
Balance
root node 를 기준으로 왼쪽과 오른쪽 자식들의 균형이 어느정도 맞는 tree
대표적인 Balanced Binary Tree : - red-black tree - AVL tree
Complete Binary Tree (완전 이진 트리)
root node 를 기준으로 leaf level (마지막 레벨) 을 제외한 왼쪽과 오른쪽 자식들의 level 수가 동일해야하고
leaf level 은 왼쪽부터 차례대로 채워져 있는 이진 트리
Full Binary Tree
하나의 자식 node 만 가지고 있는 부모 node 가 없는 이진 트리 (자식 0 또는 2 개)
Perfect Binary Tree
모든 부모 node 가 모두 두개의 자식 node 를 가지고 있고 level 도 동일 (완벽한 피라미드 형태)
Binary Tree 의 순회 방법 3가지
-
Inorder 중위
- left -> root -> right 순서 (left 의 최 하단 leaf node 부터 시작한다.)
-
Preorder 전위
- root -> left -> right 순서 (root node 부터 시작)
-
Postorder 후위
- left -> right -> root 순서 (left 의 최 하단 leaf node 부터 시작한다.)
class Node {
constructor(data, left, right) {
this.data = data;
this.left = left;
this.right = right;
return this;
}
}
class BinarySearchTree {
constructor() {
this.root = null;
}
setRoot(data) {
this.root = new Node(data, null, null);
return this.root;
}
getRoot() {
return this.root;
}
insert(data) {
const newNode = new Node(data, null, null);
if (this.root === null) {
this.root = newNode;
} else {
let currentNode = this.root;
while (true) {
if (data < currentNode.data) {
// Left
if (!currentNode.left) {
// leaf 까지 내려감
currentNode.left = newNode;
return this;
}
currentNode = currentNode.left;
}
if (data > currentNode.data) {
// Right
if (!currentNode.right) {
// leaf 까지 내려감
currentNode.right = newNode;
return this;
}
currentNode = currentNode.right;
}
}
}
}
/* inorder 순회 left -> root -> right */
inorder(node = this.root) {
if (!this.root) return "Tree 가 비어있습니다.";
if (node !== null) {
this.inorder(node.left);
console.log(node.data);
this.inorder(node.right);
}
}
/* preorder 순회 root -> left -> right */
preorder(node = this.root) {
if (!this.root) return "Tree 가 비어있습니다.";
if (node !== null) {
console.log(node.data);
this.preorder(node.left);
this.preorder(node.right);
}
}
/* postorder 순회 left -> right -> root */
postorder(node = this.root) {
if (!this.root) return "Tree 가 비어있습니다.";
if (node !== null) {
this.postorder(node.left);
this.postorder(node.right);
console.log(node.data);
}
}
/* look up (특정 값 찾기) */
lookup(data) {
if (!this.root) return false;
let currentNode = this.root;
while (currentNode) {
if (data < currentNode.data) {
currentNode = currentNode.left;
} else if (data > currentNode.data) {
currentNode = currentNode.right;
} else if (currentNode.data === data) {
return currentNode;
}
}
return null;
}
remove(data) {
if (!this.root) {
return false;
}
let currentNode = this.root;
let parentNode = null;
while (currentNode) {
if (data < currentNode.data) {
parentNode = currentNode;
currentNode = currentNode.left;
} else if (data > currentNode.data) {
parentNode = currentNode;
currentNode = currentNode.right;
} else if (currentNode.data === data) {
//We have a match, get to work!
//Option 1: No right child:
if (currentNode.right === null) {
if (parentNode === null) {
this.root = currentNode.left;
} else {
//if parent > current data, make current left child a child of parent
if (currentNode.data < parentNode.data) {
parentNode.left = currentNode.left;
//if parent < current data, make left child a right child of parent
} else if (currentNode.data > parentNode.data) {
parentNode.right = currentNode.left;
}
}
//Option 2: Right child which doesnt have a left child
} else if (currentNode.right.left === null) {
currentNode.right.left = currentNode.left;
if (parentNode === null) {
this.root = currentNode.right;
} else {
//if parent > current, make right child of the left the parent
if (currentNode.data < parentNode.data) {
parentNode.left = currentNode.right;
//if parent < current, make right child a right child of the parent
} else if (currentNode.data > parentNode.data) {
parentNode.right = currentNode.right;
}
}
//Option 3: Right child that has a left child
} else {
//find the Right child's left most child
let leftmost = currentNode.right.left;
let leftmostParent = currentNode.right;
while (leftmost.left !== null) {
leftmostParent = leftmost;
leftmost = leftmost.left;
}
//Parent's left subtree is now leftmost's right subtree
leftmostParent.left = leftmost.right;
leftmost.left = currentNode.left;
leftmost.right = currentNode.right;
if (parentNode === null) {
this.root = leftmost;
} else {
if (currentNode.data < parentNode.data) {
parentNode.left = leftmost;
} else if (currentNode.data > parentNode.data) {
parentNode.right = leftmost;
}
}
}
return true;
}
}
}
}
const myTree = new BinarySearchTree();
console.log(myTree.setRoot(10));
console.log(myTree.getRoot());
console.log(myTree.insert(5));
console.log(myTree.insert(15));
console.log(myTree.insert(8));
console.log(myTree.insert(3));
console.log(myTree.insert(12));
console.log(myTree.insert(17));
// console.log(JSON.stringify(myTree.insert(17)));
console.log(myTree.lookup(5));
// console.log(myTree.inorder());
// console.log(myTree.preorder());
// console.log(myTree.postorder());
Subscribe via RSS
