Binary Search Tree, BST (이진 탐색 트리)

이진 트리에서는 하나의 Node 가 1개의 key(data) 와 2개의 자식 node 를 가리키는 link(left,right) 를 가지고있습니다. BST(이진 탐색 트리)는 검색, 삽입, 삭제은 평균 O(log n) 의 시간 복잡도를 가집니다. 하지만 최악의 경우 편향이진트리(구글 이미지 검색) 생성되면 최악의 효율O(n)이 발생합니다. 이를 보완하고 좌우 균형을 맞추어 탐색 효율을 목적으로 B tree라는 것을 사용합니다.

아래의 java 소스코드는 해외 블로그를 참고하였습니다. 탐색,삽입 하는 코드는 비교적 간결하고, 트리의 node 를 삭제하는 logic 은 3가지로 분류 됩니다.

1. 삭제 node 의 자식이 없는 경우 - node 를 바로 삭제 합니다.

2. 삭제 node 의 자식이 1개 인 경우 - 자식 node 를 자신 대신에 부모 node 의 자식 pointer 에 연결합니다. 그 이후에 node 를 삭제 합니다. node 를 그 자식 node 로 대체한다고 보면 좋을 것 같습니다.

3. 삭제 node 의 자식이 2개 인 경우 - left subtree 의 최대 node 나 right subtree 의 최소 node 를 가져와서 삭제할 node 를 대체 합니다. 그런데 여기서 최대 node나 최소 node 가 하나의 자식 node 를 가질 경우 그 자식 node 를 조부모 node 와 연결하는 logic(소스코드의 getSuccessor 함수) 이 추가되어야합니다.

	public class BinarySearchTree {
	public static Node root;
	public BinarySearchTree() {
	this.root = null;
	}
	/**
	* tree 에서 key 로 node 를 탐색합니다.
	* @param id
	* @return
	*/
	public boolean find(int id) {
	Node current = root;
	while (current != null) {
	if (current.data == id) {
	return true;
	} else if (current.data > id) {
	current = current.left;
	} else {
	current = current.right;
	}
	}
	return false;
	}
	/**
	* tree 에서 key 를 찾아서 node 를 삭제합니다.
	* @param id
	* @return
	*/
	public boolean delete(int id) {
	Node parent = root;
	Node current = root;
	boolean isLeftChild = false;
	while (current.data != id) {
	parent = current;
	if (current.data > id) {
	isLeftChild = true;
	current = current.left;
	} else {
	isLeftChild = false;
	current = current.right;
	}
	if (current == null) {
	return false;
	}
	}
	// if i am here that means we have found the node
	// Case 1: if node to be deleted has no children
	if (current.left == null && current.right == null) {
	if (current == root) {
	root = null;
	}
	if (isLeftChild == true) {
	parent.left = null;
	} else {
	parent.right = null;
	}
	}
	// Case 2 : if node to be deleted has only one child
	else if (current.right == null) {
	if (current == root) {
	root = current.left;
	} else if (isLeftChild) {
	parent.left = current.left;
	} else {
	parent.right = current.left;
	}
	} else if (current.left == null) {
	if (current == root) {
	root = current.right;
	} else if (isLeftChild) {
	parent.left = current.right;
	} else {
	parent.right = current.right;
	}
	} else if (current.left != null && current.right != null) {
	// now we have found the minimum element in the right sub tree
	Node successor = getSuccessor(current);
	if (current == root) {
	root = successor;
	} else if (isLeftChild) {
	parent.left = successor;
	} else {
	parent.right = successor;
	}
	successor.left = current.left;
	}
	return true;
	}
	/**
	* node 를 삭제할때 좌측 우측 sub 가 있는 경우 parameter node 의 right sub tree 에서 가장 최소 key 를 가진 node 를 반환합니다.
	* @param deleleNode
	* @return
	*/
	public Node getSuccessor(Node deleleNode) {
	Node successsor = null; // current 의 부모 node 를 pointer 로 사용
	Node successsorParent = null; // current 의 조부모 node 를 pointer 로 사용
	Node current = deleleNode.right; // 삭제 할노드의 우측 자식 노드 주소를 current pointer 에 저장
	while (current != null) { // current 값이 없을때까지 반복
	successsorParent = successsor; // current 의 조부모
	successsor = current; // current 의 부모
	current = current.left; // 좌측의 node 주소를 계속 찾음.
	}
	// check if successor has the right child, it cannot have left child for sure
	// if it does have the right child, add it to the left of successorParent.
	// successsorParent
	if (successsor != deleleNode.right) { // successsor 가 삭제 노드의 우측 자식 노드 가 아닐경우
	successsorParent.left = successsor.right; // successsor의 우측 자식 노드를 sucessor 의 자리를 대체한다.
	successsor.right = deleleNode.right; // successsor 의 우측 자식 노드 pointer 는 삭제될 node 의 우측 자식노드의 주소를 가르킨다.
	}
	return successsor;
	}
	/**
	* 이진 탐색 트리에 key 삽입합니다.
	* @param id
	*/
	public void insert(int id) {
	Node newNode = new Node(id);
	if (root == null) {
	root = newNode;
	return;
	}
	Node current = root;
	Node parent = null;
	while (true) {
	parent = current;
	if (id < current.data) {
	current = current.left;
	if (current == null) {
	parent.left = newNode;
	return;
	}
	} else {
	current = current.right;
	if (current == null) {
	parent.right = newNode;
	return;
	}
	}
	}
	}
	/**
	* parameter 로 전달된 node 하위의 sub tree 를 중위 순회(left-root-right)하여 print 합니다.
	* @param root
	*/
	public void display(Node root) {
	if (root != null) {
	display(root.left);
	System.out.print(" " + root.data);
	display(root.right);
	}
	}
	}
	class Node {
	int data;
	Node left;
	Node right;
	// constructor
	public Node(int data) {
	this.data = data;
	left = null;
	right = null;
	}
	}

view raw BinarySearchTree.java hosted with ❤ by GitHub

참고 문서 - 이진탐색트리(java)