이진탐색트리 (Binary Search Tree)

# 개념

• 이진 트리이다.
• 각 노드에 하나의 키를 저장한다.
• 노드 n의 왼쪽 서브 트리에는 n의 값보다 같거나 작은 노드들이 있다.
• 노드 n의 오른쪽 서브 트리에는 n의 값보다 같거나 큰 노드들이 있다.

@검색
이진탐색트리에서 키 x를 가진 노드를 검색하고자 할때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL을 리턴한다.
검색하고자 하는 값을 루트노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.
불일치하고 검색하고자 하는 값이 루트노드의 값보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.
불일치하고 검색하고자 하는 값이 루트노드의 값과 같거나 큰 경우 오른쪽 서브트리에서 재귀적으로 검색한다.

@삽입
삽입을 하기 전, 검색을 수행한다.
트리를 검색한 후 키와 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크기를 비교하여서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

@삭제
삭제하려는 노드의 자식 수에 따라 구분한다.
자식노드가 없는 노드(리프 노드) 삭제 : 해당 노드를 단순히 삭제한다.
자식노드가 1개인 노드 삭제 : 해당 노드를 삭제하고 그 위치에 해당 노드의 자식노드를 대입한다.
자식노드가 2개인 노드 삭제 : 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰값으로 대체하거나, 오른쪽 서브트리에서 가장 작은 값으로 대체한 뒤, 해당 노드(왼쪽서브트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

예)

 

# 구현

// 이진탐색트리의 노드 객체
function Node (v, leftNode, rightNode) {
	this.value = v;
	this.left = leftNode;
	this.right = rightNode;
}
	
// 이진탐색트리
function BinarySearchTree () {
	this.root = null;
};

BinarySearchTree.prototype.insert = function (v) {
	// 이미 동일한 값을 가진 노드가 있다면 종료
	if( this.search(v) != null ){
		return;
	}
	
	const newNode = new Node(v, null, null);
	// 루트 노드가 없다면 루트 노드에 삽입
	if(this.root == null){
		this.root = newNode;
		return;
	}
	
	let node = this.root;
	while( true ) {
		// 기준 노드 값보다 작다면 좌측 탐색
		if( v < node.value  ){
			// 좌측 노드가 존재한다면 다음 노드로 이동 
			if( node.left != null ){
				node = node.left;

			// 좌측 노드가 없다면 노드 생성
			} else {
				node.left = newNode;
				break;
			}
			
		// 기준 노드 값보다 작다면 우측 탐색
		} else {
			// 우측 노드가 존재한다면 다음 노드로 이동
			if( node.right != null ){
				node = node.right;

				// 우측 노드가 없다면 노드 생성
			} else {
				node.right = newNode;
				break;
			}
		}
	}
};

BinarySearchTree.prototype.search = function (v) {
	// 트리가 비었다면
	if( this.root == null  ){
		return null;
	}
	
	let node = this.root;
	while( node != null && v != node.value ){
		if( v < node.value ){
			node = node.left;
		} else {
			node = node.right;
		}
	}
	return node;
};

BinarySearchTree.prototype.delete = function (v) {
	this.removeNode(this.root, v);
};

BinarySearchTree.prototype.removeNode = function (node, v) {
	// 삭제할 노드를 찾았을 때
	if( v == node.value ){
		// 자식이 없다면 해당 노드만 삭제
		if( node.left == null && node.right == null ){
			return null;
		}
		
		// 자식이 2개일 때 successor를 구한 뒤 값을 대입하고 successor 노드를 삭제한다.
		if( node.left != null && node.right != null ){
			const successorValue = this.findSuccessorNode(node).value;
			this.delete(successorValue); // 값을 대입하기 전에 삭제.
			node.value = successorValue;
            
			
		// 자식이 1개일 때 자식 노드의 값을 삭제 노드에 대입하고 자식 노드를 삭제한다.
		} else{
			if(node.left != null){
				node.value = node.left.value;
				node.left = null;
			} else {
				node.value = node.right.value;
				node.right = null;
			}
		}
		
	// 삭제할 노드를 찾을 때까지 탐색
	} else if( v < node.value ){
		node.left =  this.removeNode(node.left, v);
	} else {
		node.right = this.removeNode(node.right, v);
	}
	return node;
}

// 좌측 자식 노드가 없는 가장 좌측의 노드가 min값
BinarySearchTree.prototype.min = function (node) {
	return ( node.left != null ) ? this.min(node.left) : node;
};

// 우측 자식 노드가 없는 가장 우측의 노드가 max값
BinarySearchTree.prototype.max = function (node) {
	return ( node.right != null ) ? this.max(node.right) : node;
};

/**
* node보다 큰 노드들 중 가장 작거나 node보다 작은 노드들 중 가장 큰 노드인 successor를 찾는다.
*/
BinarySearchTree.prototype.findSuccessorNode = function (node) {
	// node의 우측 노드가 없다면 좌측 노드의 최대 노드를 반환
	if( node.left != null ){
		return this.max(node.left);
	}
    
    // node의 우측 노드가 있으면 우측 노드의 최소 노드를 반환
	if( node.right != null ){
		return this.min(node.right);
	}
	
	return node;
};