1. 이진 탐색 트리란?
정렬된(Ordered, Sorted) 상태의 이진 트리 구조를 의미한다. 이전 포스팅에서도 설명했지만 비-선형 구조의 형태를 사용하는 것에는 이유가 있다. 그 중 하나는 빠른 데이터 저장 및 탐색도 있다.
이진 탐색 트리는 Parent 노드를 중심으로 Left Child 노드는 Parent보다 작은 값 / Right Child 노드는 Parent보다 큰 값만 저장하도록 하여 전체 구조를 정렬된 상태로 유지하는 것이다. 아래 그림을 통해 살펴보자.
위 그림을 보면 각 층위(level)을 내려오면서 Parent 노드 보다 Child Node가 가진 데이터가 크거나 작도록 저장되어 있는 상태임을 확인할 수 있다.
이러한 구조가 어째서 필요할까? 동일한 데이터가 LinkedList에 저장되어 있다고 생각해보자. 만약 9라는 데이터를 찾고자 한다고 예를 들어보자. LinkedList에는 다음과 같이 데이터가 저장되어 있을 것이다.
LinkedList 저장 순서 : 1 - 3 - 4 - 8 - 9 - 10 - 13
그렇다면, 9라는 데이터를 찾기 위해서 5번의 탐색을 수행해야 한다. 그러나 위 사진의 트리 형태라면 어떨까? 제일 Root 노드 부터 생각해보자. 8 - 10 - 9 의 순서로 바로 찾을 수 있다.
Root 노드의 데이터를 우선 비교하여 찾고자 하는 값이 8보다 크다면 Right Child 노드를 다음으로 찾는다. Right Child 노드보다 찾고자 하는 값이 작으니 거기서 다시 Left Child 노드를 찾는다. 해당 노드가 답이므로 반환하면 된다.
이 형태로 진행하기만 해도 트리 형태가 더욱 짧게 해당 데이터를 찾을 수 있게 되어 있다. 대략적인 시간복잡도를 표현하자면 선형구조의 경우 O(n) 이며, 트리와 같은 경우에는 O(logn) 의 시간복잡도를 갖는다.
2. 이진 탐색 트리 구현하기
트리와 이진 트리에 대한 이해를 충분히 했다는 가정하에 아래의 코드를 이어가 직접 구현해보자.
참고로 아래 구현에서는 캡슐화와 같은 부분은 코드를 줄여서 표현하기 위해 생략하였다.
① Node 클래스
Node 클래스는 이전의 포스팅에서 이진 트리와 같이 저장할 데이터와 Parent / Child 노드에 대한 정보를 갖는다. 그런데 해당 노드들에 저장되는 값들을 기준으로 정렬해서 전체 트리 구조를 구현할 것이므로 Comparable<Node> 인터페이스를 구현한다.
class Node<T extends Comparable> implements Comparable<Node>{
T value;
Node parent;
Node left;
Node right;
public Node(T value){
this.value = value;
}
@Override
public int compareTo(Node node) {
return this.value.compareTo(node.value);
}
}위와 같이 구현하여 value 라는 속성을 기준으로 정렬이 가능한 구조를 설계할 것이다.
② BinarySearchTree 클래스 - 기본 구조
BinarySearchTree 클래스는 전체 트리 구조의 인스턴스를 생성하고 해당 트리 구조에 데이터 삽입 / 삭제 / 순회 등이 가능하도록 구조를 설계하고자 한다. 우선 간단한 뼈대는 아래와 같이 형성한다.
public class BinarySearchTree<T>{
class Node<T extends Comparable> implements Comparable<Node>{
T value;
Node parent;
Node left;
Node right;
public Node(T value){
this.value = value;
}
@Override
public int compareTo(Node node) {
return this.value.compareTo(node.value);
}
}
public Node root = null;
public int size = 0;
}Node 클래스는 해당 클래스의 Inner Class로 구조를 짰으며, Root 노드의 정보와 전체 노드의 수에 대한 정보를 확인할 수 있도록 구현하였다.
③ BinarySearchTree 클래스 - 데이터 삽입(insert)
데이터를 삽입하는 경우 Node Object를 만들고 해당 Object가 어느 위치에 삽입될 것인지에 대한 결정을 해야 한다. 해당 결정은 최초 Root 노드 부터 시작하여 비교한다. 아래의 로직을 참고하자.
ⓐ Root 노드가 null, 즉 비어있다면 Root 노드를 새 노드로 지정한다.
ⓑ Root 노드가 null이 아니라면, Root 노드의 value 값과 전달된 value 값을 비교하여 다음 비교군을 left / right 어느 방향으로 갈지 결정한다.
ⓒ 비교군으로 이동한 뒤 해당 노드가 null이면 해당 노드에 새 노드를 삽입하고 현재 parent 노드를 새 노드의 parent로 지정하고 parent의 child 노드로 현재 노드를 지정한다.
ⓓ 아니라면 ⓑ 과정을 반복한다.
코드는 다음과 같다.
public <T extends Comparable> boolean insert(T value){
Node newNode = new Node(value);
if(root == null){
root = newNode;
} else {
Node current = root;
Node parent = null;
while(true){
parent = current;
if(current.value.compareTo(value) > 0){ // 전달된 값이 더 작다면
current = parent.left;
if(current == null){
parent.left = newNode;
break;
}
} else { // 전달된 값이 더 크거나 같다면
current = parent.right;
if(current == null){
parent.right = newNode;
break;
}
}
}
newNode.parent = parent;
}
size++;
return true;
}
참고로 위 코드에서는 중복된 값도 넣을 수 있도록 구현하였다. 일부 트리 구조를 설명할 때, 중복 값을 제외하라고 설명하는 경우가 있는데 반드시 그런 것은 아니다. 따라서 중복 값을 넣을 수 있는 구조로 구현한다. 아래의 StackOverFlow 내용을 참조
Are duplicate keys allowed in the definition of binary search trees?
I'm trying to find the definition of a binary search tree and I keep finding different definitions everywhere. Some say that for any given subtree the left child key is less than or equal to the ...
stackoverflow.com
Generic 부분에 대해 간단히 설명하면 Method에 전달된 value 파라미터가 T 타입인데, 이것이 비교가 가능한 타입이어야 하므로 <T extends Comaparable> 을 통해 컴파일러가 오류를 내지 않도록 설정한 것이다.
④ BinarySearchTree 클래스 - 데이터 찾기(find)
Find method는 이진 탐색 트리 내에 저장되어 있는지 value 값을 찾는 방법이다. 해당 value를 저장하고 있는 노드를 반환하도록 구현한다. 코드는 아래와 같다.
public <T extends Comparable> Node find(T value){
if(root == null) return null;
Node current = root;
while(!current.value.equals(value)){
if(current.value.compareTo(value) > 0){ // 현재 값이 전달된 값보다 더 크다면
current = current.left;
} else {
current = current.right;
}
if(current == null){
throw new NullPointerException();
}
}
return current;
}
로직을 살펴보면 Root 노드가 비어있다면 전체 트리 구조가 비어 있는 것이므로 null 값을 반환시킨다.
그 후에는 Root 노드를 기반으로 각 값을 비교하며 해당 찾고자 하는 노드가 맞는지를 검사한다. 만약 계속 Child 노드를 내려가다가 비교할 노드가 null이라면 null을 반환하면 된다.
④ BinarySearchTree 클래스 - 데이터 순회(inOrder, preOrder, postOrder, levelOrder)
이전 포스팅에서 설명했듯이 각각은 중위 / 전위 / 후위 / 레벨(층위) 순회 방식이다.
중위는 현재 노드를 중간에, 전위는 먼저, 후위는 나중에 순회하며, 레벨 순회는 각 층위를 순서대로 모두 탐색하며 진행하는 방식이다. 이 순회 방식들은 레벨 순위를 제외하고는 간단하게 재귀적 방식으로 풀어낼 수 있다.
전위 순회는 특히 추후 포스팅할 DFS(Depth-First-Search) 방식에 자주 쓰이며 레벨 순회는 BFS(Breadth-First-Search)에 많이 쓰인다. 아래의 코드를 보자.
public void inOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
inOrder(root);
}
private void inOrder(Node node){
if(node != null){
inOrder(node.left);
System.out.print(node.value + ",");
inOrder(node.right);
}
}
public void preOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
preOrder(root);
}
private void preOrder(Node node){
if(node != null){
System.out.print(node.value + ",");
preOrder(node.left);
preOrder(node.right);
}
}
public void postOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
postOrder(root);
}
private void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value + ",");
}
}
public void levelOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node temp = q.peek();
System.out.print(",");
if(temp.left != null){
q.add(temp.left);
}
if(temp.right != null){
q.add(temp.right);
}
q.poll();
}
}
순회를 Root 부터 시작하도록 하기 위해 층위 순회를 제외하고는 2개씩 Method를 생성하여 만들었다. 이해하기 어렵지 않다.
⑤ BinarySearchTree 클래스 - 최소 / 최대값 찾기(getMin, getMax)
계속 설명하였듯이, 이진 탐색 트리는 기본적으로 정렬되어 있는 상태이다. 따라서 손 쉽게 현재 저장된 데이터 중 최소값과 최대값을 찾을 수 있다.
최소값을 찾는 방법은 가장 왼쪽 아래에 있는 노드까지 가서 해당 노드를 반환하면 된다.
마찬가지로 최대값은 반대로 가장 오른쪽 아래에 있는 노드까지 가서 해당 노드를 반환한다.
아래의 코드를 보자
public Node getMin(){
if(root == null){
throw new NullPointerException();
}
return getSubTreeMin(root);
}
public Node getSubTreeMin(Node start){
if(start == null){
throw new NullPointerException();
}
Node current = start;
while(current.left != null){
current = current.left;
}
return current;
}
public Node getMax(){
if(root == null){
throw new NullPointerException();
}
return getSubTreeMax(root);
}
public Node getSubTreeMax(Node start){
if(start == null){
throw new NullPointerException();
}
Node current = start;
while(current.right != null){
current = current.right;
}
return current;
}
위 코드를 보면 getSubTreeMin, getSubTreeMax를 통해 전체 트리 구조가 아닌 일부 내부의 부분 트리의 최소, 최대값을 찾을 수 있도록 설정하였다.
이 메소드는 노드를 삭제 시에도 사용할 것이라서 미리 생성해두었다.
⑥ BinarySearchTree 클래스 - 데이터 삭제(remove)
이진 탐색 트리에서 가장 구현이 복잡한 것이 바로 이 삭제이다. 잘 생각해보면 이유를 알 수 있다. 우선 성격상 전체 트리 구조는 형태를 유지해야 하며, 전체 데이터는 정렬된 상태여야 한다.
그렇다면 만약 중간에 있던 노드가 삭제되면 어떻게 해야할까? 정렬을 유지하기 위해 다른 노드를 삭제된 위치에 놓아야 하고 어떤 노드를 선택할지를 잘 결정해야 한다. 아래의 3가지 경우를 생각해볼 수 있다.
1) 삭제할 대상인 노드의 Child 노드가 없는 경우
2) 삭제할 대상인 노드의 Child 노드가 한 쪽만 있는 경우
3) 삭제할 대상인 노드의 Child 노드가 양 쪽 모두 있는 경우
각각에 대해 살펴보자.
ⓐ 삭제할 대상인 노드의 Child 노드가 없는 경우( 삭제 대상 노드가 Leaf 인 경우 )
이 때는 매우 간단하다. 단순히 해당 노드를 null로 설정하고 해당 노드의 parent 노드의 left 혹은 right를 null로 설정하면 완료된다. 아래의 그림을 보자. Child 노드가 없다면 삭제만 진행해도 전체 구조에 영향이 없다.
위에서 9라는 값이 저장된 노드를 삭제한다 해도 전체 정렬 상태에 아무런 영향이 없다는 것을 알 수 있고 해당 삭제된 위치에 다른 노드를 삽입할 이유가 없다.
ⓑ 삭제할 대상인 노드의 Child 노드가 한 쪽만 있는 경우
이 경우도 매우 간단하다. 삭제 대상인 노드의 Child 노드가 하나만 있으므로 삭제 대상인 노드의 Parent와 Child를 상호 연결시켜주면 완료된다. 아래의 그림을 보자.
위 그림에서 보면 17이라는 정보를 갖는 노드를 삭제한다고 생각해보자. 그러면 해당 노드의 Parent 노드인 13이 저장된 노드와 Child 노드인 15가 저장된 노드를 상호 연결시켜주면 문제가 해결된다. 아래의 그림을 보자.
위에서 설명한 대로 각 노드들끼리 상호 연결시켜 주었다. 그러나 전체 트리 구조에 문제가 발생하지 않는다.
ⓒ 삭제할 대상인 노드의 Child 노드가 두 쪽 모두 있는 경우
이 경우가 사실 제일 문제이다. 만약 두 Child 노드가 모두 있는데 위의 방법 처럼 한쪽 노드만 삭제된 위치에 놓고 연결시키면 반대쪽 SubTree 노드들은 붕 뜬 상태가 된다.
또한 명심해야할 것은 전체 트리 구조의 정렬된 상태를 규칙으로 유지해야 한다는 것이다. 일단 바로 아래 그림을 보자.
위 그림과 같이 13이라는 값이 저장된 노드가 삭제되었다고 가정해보자.
그렇다면 해당 위치에 대체할 노드로 어떤 노드가 가장 적합할까? 두 가지 옵션이 있다.
1) 13 데이터가 저장된 노드의 왼쪽 서브 트리에서 가장 큰 데이터가 저장된 노드
2) 13 데이터가 저장된 노드의 오른쪽 서브 트리에서 가장 작은 데이터가 저장된 노드
실제로 각각의 데이터로 대체했다고 생각해보자. 전체 트리 구조에서 전혀 문제가 발생하지 않는다. 이 대체 노드를 서브 트리 내의 가장 작은 혹은 가장 큰 데이터 노드를 찾아야 하기 때문에 상단에서 getSubTreeMin / getSubTreeMax 메소드를 생성하였다.
지금까지 설명한 내용에 대한 전체 코드를 아래에서 확인할 수 있다.
public <T extends Comparable> Node remove(T value){
Node target = find(value);
Node parent = target.parent;
// 부모 노드와 현재 target 노드의 관계 알아내기
boolean isLeft = target.equals(root) ? false : target.equals(parent.left) ? true : false;
Node replacement;
// 자식 노드가 없는 경우
if(target.left == null && target.right == null){
target = null;
// 왼쪽 자식 노드만 있는 경우
} else if(target.right == null){
replacement = target.left;
if(target.equals(root)){ // root를 삭제한다면 root 정보를 바꿔준다.
root = replacement;
} else if(isLeft){
parent.left = replacement; // parent와의 관계를 통해 연결해준다.
} else {
parent.right = replacement;
}
replacement.parent = parent; // 대체된 노드의 parent도 변경한다.
// 우측 자식 노드만 있는 경우
} else if(target.left == null){
replacement = target.right;
if(target.equals(root)){ // root를 삭제한다면 root 정보를 바꿔준다.
root = replacement;
} else if(isLeft){
parent.left = replacement; // parent와의 관계를 통해 연결해준다.
} else {
parent.right = replacement;
}
replacement.parent = parent; // 대체된 노드의 parent도 변경한다.
// 양 쪽 자식 노드가 모두 있는 경우
} else {
// 이번 코드 예시에선 좌측 서브 트리의 가장 큰 노드로 대체해보자.
Node leftSubTreeRoot = target.left;
Node rightSubTreeRoot = target.right;
replacement = getSubTreeMax(leftSubTreeRoot);
replacement.parent.right = null; // 대체 노드로 사용했으니 해당 자리는 null로 변경
// 대체된 후 모든 관계를 바꿔주어야 함.
if(target.equals(root)){
root = replacement;
} else if(isLeft){
parent.left = replacement;
} else {
parent.right = replacement;
}
replacement.left = leftSubTreeRoot;
replacement.right = rightSubTreeRoot;
replacement.parent = parent;
}
return target;
}
코드가 상당히 길다고 느껴질 수 있으나, 찬찬히 읽으면 쉽게 이해할 수 있다.
전체 코드는 아래와 같다.
import java.util.LinkedList;
import java.util.Queue;
public class BinarySearchTree<T>{
class Node<T extends Comparable> implements Comparable<Node>{
T value;
Node parent;
Node left;
Node right;
public Node(T value){
this.value = value;
}
@Override
public int compareTo(Node node) {
return this.value.compareTo(node.value);
}
}
public Node root = null;
public int size = 0;
public <T extends Comparable> boolean insert(T value){
Node newNode = new Node(value);
if(root == null){
root = newNode;
} else {
Node current = root;
Node parent = null;
while(true){
parent = current;
if(current.value.compareTo(value) > 0){ // 현재 값이 전달된 값보다 더 크다면
current = parent.left;
if(current == null){
parent.left = newNode;
break;
}
} else { // 현재 값이 전달된 값보다 작거나 같다면
current = parent.right;
if(current == null){
parent.right = newNode;
break;
}
}
}
newNode.parent = parent;
}
size++;
return true;
}
public <T extends Comparable> Node find(T value){
if(root == null) return null;
Node current = root;
while(!current.value.equals(value)){
if(current.value.compareTo(value) > 0){ // 현재 값이 전달된 값보다 더 크다면
current = current.left;
} else {
current = current.right;
}
if(current == null){
throw new NullPointerException();
}
}
return current;
}
public void inOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
inOrder(root);
}
private void inOrder(Node node){
if(node != null){
inOrder(node.left);
System.out.print(node.value + ",");
inOrder(node.right);
}
}
public void preOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
preOrder(root);
}
public void preOrder(Node node){
if(node != null){
System.out.print(node.value + ",");
preOrder(node.left);
preOrder(node.right);
}
}
public void postOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
postOrder(root);
}
public void postOrder(Node node){
if(node != null){
postOrder(node.left);
postOrder(node.right);
System.out.print(node.value + ",");
}
}
public void levelOrder(){
if(root == null){
System.out.println("Tree is Empty");
return;
}
Queue<Node> q = new LinkedList<>();
q.add(root);
while(!q.isEmpty()){
Node temp = q.peek();
System.out.print(",");
if(temp.left != null){
q.add(temp.left);
}
if(temp.right != null){
q.add(temp.right);
}
q.poll();
}
}
public Node getMin(){
if(root == null){
throw new NullPointerException();
}
return getSubTreeMin(root);
}
public Node getSubTreeMin(Node start){
if(start == null){
throw new NullPointerException();
}
Node current = start;
while(current.left != null){
current = current.left;
}
return current;
}
public Node getMax(){
if(root == null){
throw new NullPointerException();
}
return getSubTreeMax(root);
}
public Node getSubTreeMax(Node start){
if(start == null){
throw new NullPointerException();
}
Node current = start;
while(current.right != null){
current = current.right;
}
return current;
}
public <T extends Comparable> Node remove(T value){
Node target = find(value);
Node parent = target.parent;
// 부모 노드와 현재 target 노드의 관계 알아내기
boolean isLeft = target.equals(root) ? false : target.equals(parent.left) ? true : false;
Node replacement;
// 자식 노드가 없는 경우
if(target.left == null && target.right == null){
target = null;
// 왼쪽 자식 노드만 있는 경우
} else if(target.right == null){
replacement = target.left;
if(target.equals(root)){ // root를 삭제한다면 root 정보를 바꿔준다.
root = replacement;
} else if(isLeft){
parent.left = replacement; // parent와의 관계를 통해 연결해준다.
} else {
parent.right = replacement;
}
replacement.parent = parent; // 대체된 노드의 parent도 변경한다.
// 우측 자식 노드만 있는 경우
} else if(target.left == null){
replacement = target.right;
if(target.equals(root)){ // root를 삭제한다면 root 정보를 바꿔준다.
root = replacement;
} else if(isLeft){
parent.left = replacement; // parent와의 관계를 통해 연결해준다.
} else {
parent.right = replacement;
}
replacement.parent = parent; // 대체된 노드의 parent도 변경한다.
// 양 쪽 자식 노드가 모두 있는 경우
} else {
// 이번 코드 예시에선 좌측 서브 트리의 가장 큰 노드로 대체해보자.
Node leftSubTreeRoot = target.left;
Node rightSubTreeRoot = target.right;
replacement = getSubTreeMax(leftSubTreeRoot);
replacement.parent.right = null; // 대체 노드로 사용했으니 해당 자리는 null로 변경
// 대체된 후 모든 관계를 바꿔주어야 함.
if(target.equals(root)){
root = replacement;
} else if(isLeft){
parent.left = replacement;
} else {
parent.right = replacement;
}
replacement.left = leftSubTreeRoot;
replacement.right = rightSubTreeRoot;
replacement.parent = parent;
}
return target;
}
}
오류가 있는 부분은 댓글로 남겨주시면 반영하겠습니다. 감사합니다.
'자바 프로그래밍 > 자료구조(Data Structure)' 카테고리의 다른 글
| 자료구조 - 스택, 큐 직접 구현(Stack, Queue) (0) | 2020.09.30 |
|---|---|
| 자료구조 - 세그먼트 트리(Segment Tree) (0) | 2020.09.20 |
| 자료구조 - 트리(Tree), 이진 트리(Binary Tree) (0) | 2020.08.22 |
| 자료구조 - HashMap 들여다보기(2) (1) | 2020.08.20 |
| 자료구조 - HashMap 들여다보기(1) (0) | 2020.08.19 |
