[자료구조] 이진 탐색 트리, 힙

트리는 컴퓨터 구조에서 많이 사용하는 구조 입니다. 가장 대표적인 예로 파일 시스템이 있습니다.

이진트리는 다음과 같은 구조로 되어 있습니다.

하나의 노드는 자식노드를 최대 2개까지만 가질 수 있죠.

이진 탐색 트리는 이진 트리와 형태가 같으면서 한 가지 조건이 더 붙어 있습니다. 

바로 왼쪽 자식 노드는 부모 노드의 수보다가 작은 값을 가지고

오른쪽 노드는 부모 노드의 수 보다 큰 값을 가진다는 규칙 입니다.

위노드에서 그럼 중복된 숫자가 제거가 됩니다. 왜냐 하면 크거나 작지 않고 같은 값이기 때문에 위 규칙이 어긋나기 때문입니다.

그러면 조금 수정하면 위와 같은 형태가 되겠습니다.

제가 js로 구현한 코드는 아래와 같습니다..

	function Node(value) {
	this.value = value;
	this.leftChild = null;
	this.rightChild = null;
	this.parentNode = null;
	}
	const BinarySearchTree = (function() {
	function Tree() {
	this.root = null;
	}
	function _search(node, value) {
	if (!node || value === node.value) {
	return { parentNode: {}, position: 'no', findNode: node };;
	}
	if(value > node.value) {
	if (!node.rightChild) {
	return {
	parentNode: node,
	position: 'rightChild'
	}
	}
	return _search(node.rightChild, value);
	} else {
	if(!node.leftChild) {
	return {
	parentNode: node,
	position: 'leftChild'
	}
	}
	return _search(node.leftChild, value);
	}
	}
	function remove(node) {
	function findLastLeftNode(node) {
	if (!node.leftChild) {
	return findLastLeftNode(node.leftChild);
	}
	return node;
	}
	const { leftChild, rightChild } = node.parentNode;
	const replaced = leftChild === node ? 'leftChild' : 'rightChild';
	if(node.rightChild && node.leftChild) {
	const leftEndNode = findLastLeftNode(node.rightChild);
	leftEndNode.leftChild = node.leftChild;
	node.parentNode[replaced] = node.rightChild;
	} else {
	node.parentNode[replaced] = node.leftChild || node.rightChild;
	}
	}
	Tree.prototype.insert = function(value) {
	const newNode = new Node(value);
	if(!this.root) {
	this.root = newNode;
	return;
	}
	const { parentNode, position } = _search(this.root, value);;
	parentNode[position] = newNode;
	newNode.parentNode = parentNode;
	}
	Tree.prototype.search = function(value) {
	const { findNode } = _search(this.root, value);
	return !!findNode ? true : false;
	}
	Tree.prototype.delete = function(value) {
	const { findNode } = _search(this.root, value);
	if (!!findNode) {
	remove(findNode);
	return true;
	} else {
	return false;
	}
	}
	return Tree;
	})()
	const binarySearchTree = new BinarySearchTree();
	binarySearchTree.delete(2);
	binarySearchTree.insert(4);
	binarySearchTree.insert(2);
	binarySearchTree.insert(4);
	binarySearchTree.insert(5);
	binarySearchTree.delete(5);
	binarySearchTree.insert(1);
	binarySearchTree.insert(9);
	binarySearchTree.delete(2);
	binarySearchTree.insert(2);
	console.dir(binarySearchTree);
	console.log(binarySearchTree.search(4));
	console.log(binarySearchTree.search(2));
	console.log(binarySearchTree.search(1));
	console.log(binarySearchTree.search(5));
	console.log(binarySearchTree.search(6));
	console.log(binarySearchTree.search(8));

view raw BinarySearchTree.js hosted with ❤ by GitHub

이진 트리는 insert, delete, search  모두 Log(N)의 복잡도를 갖습니다.

힙은 최대힙과 최소힙이 있습니다. 이 자료구조도 이진트리의 형태를 갖습니다. 

이 자료구조는 참 재밌는 자료구조 입니다. 특정 영역에서 두곽을 나타내거든요. 예를들면 지금 러시아 월드컵이 한창인데

우리나라 선수를 최대 힙에 다 넣고, 수비에서 5명 꺼내오고, 공격에서 5명 꺼내오고, 미드필더에서 5명 꺼내오고 이러면

각 포지션에서 가장 잘하는 선수 5명씩 꺼내온 겁니다. 항상 가장 큰 값을 갖는 녀석을 루트로 두기 때문에 가능하죠.

힙은 다음과 같은 규칙을 따릅니다.

• 힙의 자료는 배열로 저장하며, 첫 번째 인데스(0인 인덱스)는 사용하지 않는다.
• leftChildNode index = parentNode inex * 2
• rightChildNode index = parentNode inex * 2 + 1
• parentNode index = childNode / 2 (나머지는 버림)

저는 js로 구현했고 최대힙과 최소힙을 생성하는 객체를 리턴하도록 구현했습니다.

	let Heap = (function() {
	function Heap(compare) {
	this.arr = [];
	this.size = 0;
	this.compare = compare;
	}
	Heap.prototype.insert = function(value) {
	const that = this;
	let swapUp = function swapUp(arr, childIdx) {
	if(childIdx === 1) {
	return true;
	}
	const parentIdx = Math.floor(childIdx / 2);
	if(that.compare(arr[parentIdx], arr[childIdx])) {
	return true;
	} else if(arr[childIdx] === arr[parentIdx]) {
	return false;
	} else {
	let tmp = arr[childIdx];
	arr[childIdx] = arr[parentIdx];
	arr[parentIdx] = tmp;
	return swapUp(arr, parentIdx);
	}
	};
	if(!Number.isInteger(value)) {
	console.log("input only number format");
	return;
	}
	let tmpArr = [...this.arr];
	tmpArr[this.size + 1] = value;
	const result = swapUp(tmpArr, this.size + 1);
	if(result) {
	this.size++;
	this.arr = tmpArr;
	}
	}
	Heap.prototype.delete = function() {
	const that = this;
	function swapDown(arr, parentIdx) {
	const leftChild = {
	value: arr[parentIdx * 2],
	idx: parentIdx * 2
	}
	const rightChild = {
	value: arr[parentIdx * 2 + 1],
	idx: parentIdx * 2 + 1
	}
	let next;
	const size = arr.length - 1;
	if(size < leftChild.idx) {
	return true;
	} else if(size == leftChild.idx || that.compare(leftChild.value, rightChild.value)) {
	next = leftChild
	} else {
	next = rightChild;
	}
	if (that.compare(arr[parentIdx], next.value)) {
	return true;
	} else {
	let tmp = arr[parentIdx];
	arr[parentIdx] = next.value;
	arr[ next.idx] = tmp;
	return swapDown(arr, next.idx);
	}
	}
	const top = this.arr[1];
	if(!top) {
	return;
	}
	this.arr[1] = this.arr[this.size];
	this.arr.length = this.size--;
	swapDown(this.arr, 1);
	return top;
	}
	return {
	createMaxHaep: () => new Heap(function(a, b) { return a > b}),
	createMinHeap: () => new Heap(function(a, b) { return a < b})
	};
	})()
	// console.log(Heap);
	let maxHeap = Heap.createMaxHaep();
	let minHeap = Heap.createMinHeap();
	console.log(maxHeap.delete());
	console.dir(maxHeap.arr);
	console.dir(maxHeap.size);
	maxHeap.insert("sdsd");
	maxHeap.insert(1);
	maxHeap.insert(22);
	maxHeap.insert(5);
	maxHeap.insert(13);
	maxHeap.insert(17);
	maxHeap.insert(10);
	maxHeap.insert(19);
	maxHeap.insert(14);
	maxHeap.insert(2);
	maxHeap.insert(4);
	maxHeap.insert(15);
	maxHeap.insert(18);
	maxHeap.insert(7);
	maxHeap.insert(9);
	maxHeap.insert(11);
	maxHeap.insert(13);
	console.log(maxHeap.delete());
	console.dir(maxHeap.arr);

view raw Heap.js hosted with ❤ by GitHub

class를 안쓰고 prototype을 연습하려고 만들었습니다. 코드가 좀 정리할 필요가 있겠지만,, 일단은 ㅎㅎ