Skip to content

Instantly share code, notes, and snippets.

@keehyun2
Created April 27, 2018 02:18
Show Gist options
  • Save keehyun2/c293cd18a871d6a6074cda3631632b34 to your computer and use it in GitHub Desktop.
Save keehyun2/c293cd18a871d6a6074cda3631632b34 to your computer and use it in GitHub Desktop.
BinarySearchTree
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;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment