BinarySearchTree 학습
Binary Search Tree
이진 탐색 트리: 이진 트리의 형태를 가지며 왼쪽 자식 노드는 나보다 작고 오른쪽 자식 노드는 나보다 큰 특징을 가진 자료구조
이진트리: 노드의 최대 차수가 2인 트리
이분화된 탐색을 위한 트리이며 이전 포스팅내용 heap과 같은 트리구조입니다.
그러나 힙(heap)은 최댓값과 최솟값을 찾기 위한 자료구조이며 이진 탐색 트리는 탐색이 목적인 자료구조입니다.
힙은 같은 레벨의 노드끼리의 대소관계가 없으나 이진 탐색 트리는 형제 노드의 대소관계를 활용합니다.
O(logN)의 시간 복잡도를 가지나 편향된 트리와 가까워질수록 O(n)에 가까워집니다.
이를 개선한 방식 AVL Tree, RedBlack Tree가 있습니다.
구현부
삽입, 삭제, 순회, 유틸성 연산을 포함하며 재귀적인 방식으로 구현되어 있습니다.
선언부입니다.
구현하다 보니 size값을 만드는 것을 놓쳐서 size()에서는 직접 탐색을 하며 원소의 개수를 구합니다.
다시 추가를 할까 했지만 공부도 할 겸 다른 방식으로 풀고자 size값은 제외했습니다.
public class BiSearchTree {
public Node root;
public BiSearchTree(int val) {
this.root = new Node(val);
}
Tree의 Node 코드입니다.
이전 포스팅에서는 Generic이 많이 사용됐지만 BST에 집중하기 위해서 이번 포스팅에서는 제외했습니다.
class Node {
int val;
Node left;
Node right;
public Node(int val) {
this.val = val;
this.left = null;
this.right = null;
}
public boolean hasLeft() {
return left != null;
}
public boolean hasRight() {
return right != null;
}
}
삽입 연산입니다.
자신(node)에 대하여 다시 자기 자신을 반환합니다.
만약 자신(node)이 null인 경우 새로운 val(input) Node를 반환하며 null이 아닌 경우에는
val와 자신의 값을 비교하여 작다면 insert(node.left, val) 크다면 insert(node.right, val)를 호출합니다.
자기 자신을 반환하게 되면 node.left = node.left 즉 다시 원래자리 그대로 할당을 합니다.
하지만 node가 null이다. 이것은 단말노드가 호출한 메서드라는 의미가 되어
node.left = new Node(val)가 됩니다.
null이 아닌 경우에는 내부 노드이므로 삽입을 위한 적절한 위치를 찾아 탐색을 합니다.
public boolean insert(int val) {
root = insert(val, root);
return true;
}
private Node insert(int val, Node node) {
// 단말 노드의 자식 노드로 삽입됩니다.
if(node == null) {
return new Node(val);
}
// 적절한 자리를 찾아 탐색
if(val < node.val) {
node.left = insert(val, node.left);
} else {
node.right = insert(val, node.right);
}
// 새로 삽입이 되는 자리가 아닌 경우에는 모두 여기서 메서드를 종료합니다.
return node;
}
삭제 연산입니다.
1. 처음에 자기 자신이 단말 노드가 호출한 경우에는 null을 반환합니다.
2. 다음으로 삭제하려는 값을 찾았다면 삭제를 시작합니다.
3. 삭제 대상이 아니라면 이분 탐색을 합니다.
4. 마지막으로 자기 자신을 반환합니다.
해당 과정이 root부터 단말 노드까지 모두 적용됩니다.
삭제 대상이 단말 노드인 경우 null을 반환하여 [node.left = null or node.right = null]을 만들어 줍니다.
내부 노드인 경우 자식 노드가 1개와 2개의 경우로 나뉩니다.
1개는 간단합니다. 왼쪽에 있다면 자신의 오른쪽 노드를 왼쪽 자식노드의 오른쪽 자식으로 할당하고 왼쪽 노드를 반환합니다.
2개에서 조금 복잡해지는데
hasLeft() && hasRight()가 true인 경우입니다.
왼쪽, 오른쪽 두 개 중에서 1개를 올려야 합니다. 그렇다고 바로 올리면
차수가 2개를 넘어버리므로 이진 탐색 트리를 벗어납니다.
올바른 구현방식은 왼쪽을 선택하였다면 왼쪽 트리에서 제일 큰 값을 삭제된 자리에 넣어야 합니다.
이때 제일 큰 값을 참조하는 부모 노드에서 참조를 끊어주고
큰 값의 자식 노드를 다시 왼쪽 트리의 단말 노드(새로운 가장 큰 값)에 자식으로 편입시켜주어야 합니다.
이제 자신(node)의 자식 노드를 제일 큰 값을 가지는 노드에게 할당해 주고 반환해 줍니다.
public void delete(int val) {
root = delete(val, root);
}
public Node delete(int val, Node node) {
// 탐색종료
if(node == null) {
return null;
}
// 노드 발견
if(node.val == val) {
// 좌측
if(node.hasLeft()) {
Node LofDelete = node.left;
// 좌측의 노드가 오른쪽 자식을 가지는 경우
if(LofDelete.hasRight()){
// 좌측의 오른쪽 자식중 제일 큰값
Node biggestOfLTree = getBiggestNode(LofDelete);
// biggestOfLTree의 연결을 끊어냅니다.(삭제 노드자리에 가야함)
unlinkRightLeafNode(LofDelete);
// biggestOfLTree의 자식노드를 부모노드에 연결
getBiggestNode(LofDelete).right = biggestOfLTree.left;
// biggestOfLTree가 삭제되는 자리에 가기때문에 기존 노드의 연결상태를 가져옵니다.
biggestOfLTree.left = node.left;
biggestOfLTree.right = node.right;
// 삭제되는 노드자리에 새로운 노드를 반환
return biggestOfLTree;
// 좌측의 노드가 오른쪽 자식이 없는 경우
}else {
LofDelete.right = node.right;
return LofDelete;
}
}
// 우측버전, 좌측버전을 반전해줍니다.
if(node.hasRight()){
Node RofDelete = node.right;
if(RofDelete.hasLeft()){
Node smallestNodeOfRtree = getSmallestNode(RofDelete);
unlinkLeftLeafNode(RofDelete);
getSmallestNode(RofDelete).left = smallestNodeOfRtree.right;
smallestNodeOfRtree.left = node.left;
smallestNodeOfRtree.right = node.right;
return smallestNodeOfRtree;
}
RofDelete.left = node.left;
return RofDelete;
}
// 삭제하려는 노드가 단말 노드인 경우는 null을 반환합니다.
return null;
}
// 탐색
if(node.val != val) {
if (val < node.val) {
node.left = delete(val, node.left);
} else {
node.right = delete(val, node.right);
}
}
// 그외의 노드는 그대로 반환
return node;
}
단말 노드의 연결을 끊어주는 메서드와 가장 큰 노드, 가장 작은 노드를 찾는 메서드입니다.
unlink는 자신의 오른쪽 자식노드가 존재하지만 오른쪽 자식의 오른쪽 자식 노드가 없을 때 (자식은 있지만 손주가 없는)까지
재귀적으로 호출하여 마지막노드의 참조를 null로 만듭니다.
getSmallest는 가장 작은 값은 제일 좌측에 위치하며 hasLeft가 true일 때까지 호출하며
마지막에 false일 때 자신(단말)을 반환합니다.
getBiggest는 반대로 동작합니다.
private void unlinkRightLeafNode(Node node){
if(node == null) {
return;
}
unlinkRightLeafNode(node.right);
if(node.hasRight() && !node.right.hasRight()) {
node.right = null;
}
}
private void unlinkLeftLeafNode(Node node){
if(node == null) {
return;
}
unlinkLeftLeafNode(node.left);
if(node.hasRight() && !node.left.hasRight()) {
node.left = null;
}
}
private Node getBiggestNode(Node node) {
if(node.hasRight()) {
return getBiggestNode(node.right);
} else {
return node;
}
}
private Node getSmallestNode(Node node) {
if(node.hasLeft()) {
return getSmallestNode(node.left);
} else {
return node;
}
}
순회입니다.
전위 순회, 중위 순회, 후위 순회가 구현되어 있습니다. + 역 중위 순회
전위 순회(pre order) : root -> left -> right
중위 순회(in order) : left -> root -> right
후위 순회(post order) : left -> right -> root
역 방향 중위 순회(in order) : right -> root -> left
외우기 어렵다면 root를 기준으로 자신의 우선 순의를 생각하면 됩니다.
중위 순회를 사용하면 오름차순으로 탐색을 하게 되며
내림차순으로도 구현을 하고 싶다면 left와 right를 뒤집어 사용하면 됩니다.(역 방향)
public void inOrder() {
inOrder(root);
}
public void postOrder() {
postOrder(root);
}
public void preOrder() {
preOrder(root);
}
public void inOrderReverse() {
inOrderReverse(root);
}
public void inOrder(Node node) {
if(node == null) {
return;
}
inOrder(node.left);
System.out.println(node.val);
inOrder(node.right);
}
private void inOrderReverse(Node node) {
if(node == null) {
return;
}
inOrderReverse(node.right);
System.out.println(node.val);
inOrderReverse(node.left);
}
public void postOrder(Node node) {
if(node == null) {
return;
}
inOrder(node.left);
inOrder(node.right);
System.out.println(node.val);
}
public void preOrder(Node node) {
if(node == null) {
return;
}
System.out.println(node.val);
inOrder(node.left);
inOrder(node.right);
}
트리의 크기를 구합니다.
삽입, 삭제 연산마다 크기를 수정하면 되지만 재귀호출 학습차원에서 구현해 봤습니다.
트리의 모든 노드에 접근하게 되며 모두 마지막 node에서부터
0(left default size) + 0(right default size) + 1(자신)을 반환하며 차곡차곡 모두 더하여 반환을 합니다.
public int size() {
return size(root, 0);
}
private int size(Node node, int size) {
if(node == null) {
return size;
}
return size(node.left, size) + size(node.right, size) + 1;
}
root가 없다면 true입니다.
public boolean isEmpty() {
return root == null;
}
임의의 요소가 트리안에 포함되어 있는지 확인합니다.
size()와 같은 맥락의 로직이며 자신이 단말노드의 자식( = null)이라면 false를 반환합니다.
자신이 내부노드일 때 [node.val == val]라면 true를 반환합니다.
아니라면 이분 탐색을 합니다.
이분 탐색 시 leftResult or rightResult 2개 중에서 1개라도 true가 나왔다면 true를 반환합니다.
true를 반환받는 모든 contains()은 OR 연산으로 true를 반한하게 되어
사용자에게 true를 반환하게 됩니다.
true가 없다면 당연하게도 제일 처음 호출된 contains()는 false를 반환합니다.
public boolean contains(int val) {
return contains(root, val);
}
private boolean contains(Node node, int val) {
if(node == null) {
return false;
}
boolean leftResult = false;
boolean rightResult = false;
if(node.val > val) {
leftResult = contains(node.left, val);
}else if(node.val < val){
rightResult = contains(node.right, val);
}else {
return true;
}
return leftResult || rightResult;
}
끝