[ DS ] 트리 & 이진트리

[ DS ] 트리 & 이진트리

1. 트리(Tree)란?

- 이전에 다뤄왔던 것들과는 다르게 "비선형" 구조인 계층 구졸르 가진 자료구조입니다.

- 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타날 때 사용됩니다.

2. 용어정리(트리)

- 루트(Root) : 가장 상위에 있는 노드를 뜻합니다.

- 노드(Node) ; 트리 안에 들어있는 각 항목을 말합니다.

- 리프(Leaf) : 자식이 없는 가장 끝에 있는 노드를 의미합니다.

3. 트리의 특징

left = index * 2

right = index * 2 + 1

parent = floor(index / 2)

4. 트리의 종류

- 이진트리

정점이 최대 2개의 자식을 가지는 트리를 의미한다.

- 완전 이진트리

리프 노드를 제외하고 모든 정점이 채워져있다.

- 포화 이진트리

완전 이진트리 + 마지막도 채워져있다면, 포화 이진 트리라고 한다.

- 이진트리의 특징

- N개의 정점을 가진 편향 트리가 될 수 있다.

- 정점이 N개인 포화 또는 완전 이진 트리의 높이는 로그 N이다.

- 높이가 h인 포화 이진 트리는 2^h -1 개의 정점을 가진다.

- 이진 탐색 트리와 다르게 좌/우에 따른 값의 차이는 없다.

5. 기본 트리 구현

class Node { constructor(value) { this.value = value; this.children = []; } add(data) { this.children.push(new Node(data)); } remove(data) { this.children = this.children.filter((child) => child.data === data ? false : true ); } } class Tree { constructor() { this.root = null; } } const t = new Tree(); t.root = new Node("a"); t.root.add("b"); t.root.add("c"); t.root.children[0].add("d");

\

6. 트리의 순회 [ 전위, 중위, 후위 ]

class Tree { constructor(val) { this.val = val; this.leftNode = null; this.rightNode = null; } setLeftNode(node) { this.leftNode = node; } setRightNode(node) { this.rightNode = node; } // 중위순회 [ left -> root -> right] inOrderTree(node) { if (!node) { return; } return [ ...this.inOrderTree(node.leftNode), node.val, ...this.inOrderTree(node.rightNode), ]; } // 전위순회 [ root -> left -> right] preOrderTree(node) { if (!node) { return; } return [ node.val, ...this.inOrderTree(node.leftNode), ...this.inOrderTree(node.rightNode), ]; } // 후위순회 [ left -> right -> root ] postOrderTree(node) { if (!node) { return; } return [ ...this.inOrderTree(node.leftNode), ...this.inOrderTree(node.rightNode), node.val, ]; } } const root = new Tree("A"); let node = new Tree("B"); root.setLeftNode(node); node = new Tree("C"); root.setRightNode(node); node = new Tree("D"); root.leftNode.setLeftNode(node); node = new Tree("E"); root.leftNode.setRightNode(node); node = new Tree("F"); root.rightNode.setLeftNode(node); node = new Tree("G"); root.rightNode.setRightNode(node); // 중위 순회 left -> root -> right root.inOrderTree(root); console.log(); // 전위 순회 root -> left sub -> right sub root.preOrderTree(root); console.log(); // 후위 순회 왼쪽 -> 오른쪽 -> root root.postOrderTree(root);

7. 이진 탐색 트리 구현

- 특징

1) 왼쪽 자식은 부모보다 작은 값을 가지고 있습니다.

2) 오른쪽 자식은 부모보다 큰 값을 가지고 있습니다.

- 부작용

작은 값 또는 큰 값만 들어오는 경우 한 쪽으로 치우친 트리가 나올수 있습니다.

class Node { constructor(value) { this.value = value; this.left = null; this.right = null; } } class BST { constructor() { this.root = null; } insert(value) { const newNode = new Node(value); if ( this.root === null ) { this.root = newNode; return; } let currentNode = this.root; while ( currentNode !== null ) { if ( currentNode.value > value ) { if ( currentNode.left === null ) { currentNode.left = newNode; break; } currentNode = currentNode.left; } else { if ( currentNode.right === null ) { currentNode.right = newNode; break; } currentNode = currentNode.right; } } } has(value) { let currentNode = this.root; while ( currentNode !== null ) { if ( currentNode.value === value ) { return true; } if ( currentNode.value < value ) { currentNode = currentNode.right; } else{ currentNode = currentNode.left; } } return false; } }

from http://kimbangg.tistory.com/297 by ccl(A) rewrite - 2021-08-10 21:26:19