이진 탐색 트리에서 원소의 삭제는 해당 노드를 삭제하면서 트리의 전체적인 구조가 이진 탐색 트리의 기준에 맞게 노드들이 다시 재배열 되도록 하는 것이 중요하다.
삭제 연산은 3가지의 케이스가 존재하며 다음과 같다.
삭제할 노드가 자식을 가지고 있지 않은 경우
삭제할 노드가 자식을 하나 가지고 있는 경우
삭제할 노드가 자식을 둘 가지고 있는 경우
3가지 케이스 모두 그림을 통해 자세히 알아보도록 하자. 우리가 테스트로 사용할 트리의 구조는 아래와 같다고 가정하자
트리의 구조
선행 조건
원소를 삭제하기 위해서는 당연하게도 우선 해당 원소의 위치를 찾아야 한다. 만약 해당 위치가 null이 된다면 해당 트리에 삭제할 원소가 존재하지 않는다는 것으로 원소의 존재유무 역시 판단할 수 있다.
이를 구현한 코드는 아래와 같다.
public void removeNode(int key){
Node cur = null; // 현재 가리키는 노드
Node parent = null; // 현재 가리키는 노드의 부모 노드
Node predecessor = null;
Node successor = null;
cur = this.root;
while(cur != null){
if (cur.data == key){
break;
}
parent = cur;
if (cur.data < key){
cur = cur.right;
} else{
cur = cur.left;
}
}
if (cur == null){
return;
}
}
자식이 하나도 없는 케이스
예시 사진에서 8을 삭제한다고 가정하자. 8은 어떠한 자식도 없으므로 해당 노드를 삭제하고 해당 노드의 부모 노드인 5의 우측 링크를 null로 하면 끝이다.
만약 부모 노드가 null인 경우, 즉 루트 노드 하나만 남아있고 그 노드를 삭제해야할 경우 트리가 비어있으므로 트리의 루트를 null로 지정하면 끝이다.
public void removeNode(int key){
Node cur = null; // 현재 가리키는 노드
Node parent = null; // 현재 가리키는 노드의 부모 노드
Node predecessor = null;
Node successor = null;
cur = this.root;
while(cur != null){
if (cur.data == key){
break;
}
parent = cur;
if (cur.data < key){
cur = cur.right;
} else{
cur = cur.left;
}
}
if (cur == null){
return;
}
// 삭제할 노드가 자식을 가지고 있지 않은 경우
if (cur.left == null && cur.right == null){
if (parent == null){
this.root = null;
} else{
if (parent.left == cur){
parent.left = null;
} else{
parent.right = null;
}
}
}
}
자식이 하나인 케이스
사진에서 15를 삭제한다고 가정하자. 15는 자식으로 20을 가지고 있다.
이 경우 역시 간단하다. 삭제할 노드의 부모 노드의 자식을 삭제할 노드가 아닌 삭제할 노드의 자식 노드를 가리키도록 링크를 재설정 하면 된다.
새로운 링크를 설정하는 모습
만약 루트 노드가 하나의 자식을 가지고 있고 루트 노드를 삭제하는 경우, 루트를 삭제할 루트노드의 자식으로 변경하면 해결된다.
이를 구현한 코드는 다음과 같다.
public void removeNode(int key){
Node cur = null; // 현재 가리키는 노드
Node parent = null; // 현재 가리키는 노드의 부모 노드
Node predecessor = null;
Node successor = null;
cur = this.root;
while(cur != null){
if (cur.data == key){
break;
}
parent = cur;
if (cur.data < key){
cur = cur.right;
} else{
cur = cur.left;
}
}
if (cur == null){
return;
}
// 삭제할 노드가 자식을 가지고 있지 않은 경우
if (cur.left == null && cur.right == null){
if (parent == null){
this.root = null;
} else{
if (parent.left == cur){
parent.left = null;
} else{
parent.right = null;
}
}
} else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null){
// 삭제할 노드의 자식이 하나인 경우
if (parent == null){
if (cur.left != null){
this.root = cur.left;
else{
this.root = cur.right;
}
} else{
if (parent.left == cur){
if (cur.left != null){
parent.left = cur.left;
} else{
parent.left = cur.right;
}
} else{
if (cur.left != null){
parent.right = cur.left;
} else{
parent.right = cur.right;
}
}
}
}
}
삭제할 노드의 자식이 두 개인 경우
해당 경우가 가장 까다로운 경우로 이 경우에는 다음과 같은 과정을 거쳐 노드를 삭제하게 된다.
삭제할 노드의 좌측 서브트리 중 가장 큰 값을 가진 노드를 삭제할 노드와 위치를 바꾼다.
삭제할 노드의 우측 서브트리 중 가장 작은 값을 가진 노드와 위치를 바꾸어도 상관없다.
이후 삭제할 노드를 삭제한다.
예를 들어 위 트리에서 10을 삭제한다고 가정하자. 10은 5, 15라는 두 자식을 가지고 있으므로 10의 좌측 서브트리를 먼저 보아야 한다.
10의 좌측 서브트리는 5를 루트로 하는 서브트리이며 이 서브트리에서 가장 큰 값은 해당 서브트리에서 가장 오른쪽에 있는 8이 된다.
이후 이 노드를 삭제할 노드인 10이 있는 위치로 옮긴다. 그렇다면 구조는 다음과 같이 될 것이다.
삭제한 이후의 트리
이 구조는 이진 탐색 트리의 조건을 만족한다.
이를 수행하기 위해서는 좌측 서브트리 중 가장 큰 값을 가진 노드를 가리키는 포인터와 해당 노드의 부모 노드를 가리키는 포인터가 필요하다. 필자는 이 두 포인터를 위의 코드에서 각각 successor와 predecessor로 이름지어놓았다.
그럼 위의 삭제 과정에서 predecessor와 successor가 어떻게 움직이는지 살펴보자.
처음 successor는 삭제할 노드인 10의 좌측 자식인 5를 가리키고, predecessor는 5의 부모인 10을 가리킨다.
좌측 서브트리의 최대값은 좌측 서브트리에서 가장 우측에 존재하는 노드이므로 sucessor는 계속 우측으로 이동하며, predecessor는 successor가 직전에 가리킨 노드를 가리키며 계속 successor의 부모 노드를 가리키도록 한다.
위 과정을 수행하면 successor는 좌측 서브트리에서 가장 큰 값인 8을 가리키고 있을 것이고, predecessor는 5를 가리키고 있을 것이다. 이제 남은 것은 successor의 값인 8을 삭제할 노드의 값에 덮어씌우는 것과 predecessor의 링크를 재설정 하는 것이다.
predecessor의 우측 링크는 좌측 서브트리에서 가장 큰 값인 8의 좌측 자식을 가리키도록 한다. 이렇게 하면 만약 8의 좌측 자식이 존재한다 하더라도 자연스럽에 5의 우측 자식으로 끌어올려 데이터의 유실을 막을 수 있다.
주의해야할 점
위 방식은 얼핏 보면 잘 동작할 것처럼 보인다. 하지만 해당 방식에는 치명적인 오류가 존재하는데 이를 보기 위해 다음과 같은 트리가 있다고 가정하자.
문제가 발생하는 트리 구조
여기서 8을 삭제한다고 가정하자. 그렇다면 predecessor는 8을 가리키고, successor는 삭제할 노드의 좌측 자식인 5를 가리키게 된다.
이제 좌측 서브트리에서 최대값을 찾아 predecessor와 successor를 갱신해야한다. 하지만 우측 자식이 존재하지 않기 떄문에 저 둘의 값이 갱신되지 않는다!
이제 predecessor가 가리키고 있는 8에 successor의 값인 5를 덮어씌운다. 또한 predecessor의 우측 링크는 successor의 좌측 링크인 null을 가리키도록 하자.
삭제 연산이 끝나고 트리는 다음과 같은 결과가 된다.
위 트리의 삭제 연산의 결과
무언가 이상하다고 생각되지 않는가? 전혀 엉뚱한 노드를 삭제하는 것은 물론이고 중복된 데이터가 존재하게 되버려 이진 탐색 트리의 구조가 깨져버렸다.
이는 predecessor와 successor가 저렇게 한번 지정한 대상에서 갱신이 이루어지지 않을 때 발생하는 상황으로 해당 상황에 대하여 별도의 처리를 해주어야 한다.
해결법은 간단한데 predecessor와 successor가 원래 지정한 객체에서 달라졌는지를 확인하고 달라지지 않았다면 successor의 값을 삭제할 노드의 값에 덮어씌우고, 삭제할 노드의 좌측 링크를 successor의 좌측 자식을 가리키도록 하면 해결된다.
예시로 아래와 같은 트리 구조에서 8을 삭제한다고 가정하자.
예시 트리
predecessor는 8, successor는 5에서 갱신되지 않는다. 이는 트리 구조를 보면 바로 알 수 있을 것이다.
이제 삭제할 노드 8의 값을 5로 지정한다. 그리고 삭제할 노드의 좌측 링크를 successor의 좌측 자식을 가리키도록 지정한다. 이렇게 되면 삭제할 노드의 좌측 링크는 3을 가리키게 되어 3이 끌어올려지게 될 것이다.
따라서 해당 연산의 결과는 아래와 같게 된다.
정상적으로 삭제된 트리의 구조
해당 구조는 이진 탐색 트리의 조건을 잘 만족한다.
이제 유의사항과 위의 구현 원리를 이용하여 코드로 구현해보자.
public void removeNode(int key){
Node cur = null; // 현재 가리키는 노드
Node parent = null; // 현재 가리키는 노드의 부모 노드
Node predecessor = null; // successor의 부모 노드를 가리키는 포인터
Node successor = null; // 좌측 서브트리에서 가장 큰 값을 가리키는 포인터
cur = this.root;
while(cur != null){
if (cur.data == key){
break;
}
parent = cur;
if (cur.data < key){
cur = cur.right;
} else{
cur = cur.left;
}
}
if (cur == null){
return;
}
// 삭제할 노드가 자식을 가지고 있지 않은 경우
if (cur.left == null && cur.right == null){
if (parent == null){
this.root = null;
} else{
if (parent.left == cur){
parent.left = null;
} else{
parent.right = null;
}
}
} else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null){
// 삭제할 노드의 자식이 하나인 경우
if (parent == null){
if (cur.left != null){
this.root = cur.left;
else{
this.root = cur.right;
}
} else{
if (parent.left == cur){
if (cur.left != null){
parent.left = cur.left;
} else{
parent.left = cur.right;
}
} else{
if (cur.left != null){
parent.right = cur.left;
} else{
parent.right = cur.right;
}
}
} else if (cur.left != null && cur.right != null){
// 삭제할 노드가 두 자식을 가진 경우
predecessor = cur;
successor = predecessor.left;
while(successor.right != null){
predecessor = successor;
successor = successor.right;
}
if (predecessor == cur){
cur.data = successor.data;
cur.left = successor.left;
} else{
cur.data = successor.data;
predecessor.right = successor.left;
}
}
}
}
이렇게 삭제를 마무리지었다. 코드는 길지만 사실상 이전에 말했던 원리들과 동작을 그대로 코드로 구현한 것에 불과하다.
데이터의 탐색
탐색은 이진 탐색 트리에서 값을 찾는 것으로 이진 탐색 트리의 원리를 그대로 따라가면 된다.
탐색은 루트부터 시작하며 입력받은 값과 현재 비교하고 있는 노드의 값을 비교해 입력값이 작다면 비교 중인 노드의 좌측으로, 크다면 우측으로 이동하며 동일하다면 값을 찾은 것으로 true(존재한다)를 반환하면 된다.
public boolean searchNode(int key){
Node cur = this.root;
while(cur != null){
if (cur.data < key){
cur = cur.right;
} else if (cur.data > key){
cur = cur.left;
} else{
return true;
}
}
return false;
}
정리
이진 탐색 트리는 삽입 연산 보단 삭제 연산의 비중이 훨씬 크고 복잡하다. 삭제 연산을 유심히 보며 구현할 수 있도록 해야한다.
현재 구현 방법은 반복문을 통해 구현하고 있는데 재귀적 방식을 사용하여 구현할 수 도 있다. 재귀적으로 구현할 경우 반복문에 비해 코드의 길이가 매우 간결해지고 직관적이라는 장점이 있다.
아래는 이진 탐색 트리의 전체적인 구현과 그 테스트 코드이다.
class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
this.left = null;
this.right = null;
}
}
class BinarySearchTree{
Node root;
BinarySearchTree(){
this.root = null;
}
public void addNode(int key){
if (root == null){
root = new Node(key);
return;
}
if (searchNode(key)){
return;
}
Node cur = this.root;
while (true){
Node pre = cur;
if (cur.data < key){
cur = cur.right;
if (cur == null){
pre.right = new Node(key);
break;
}
} else{
cur = cur.left;
if (cur == null){
pre.left = new Node(key);
break;
}
}
}
}
public boolean searchNode(int key){
Node cur = this.root;
while(cur != null){
if (cur.data < key){
cur = cur.right;
} else if (cur.data > key){
cur = cur.left;
} else{
return true;
}
}
return false;
}
public void removeNode(int key){
Node cur = null;
Node parent = null;
Node predecessor = null;
Node successor = null;
cur = this.root;
while(cur != null){
if (cur.data == key){
break;
}
parent = cur;
if (cur.data < key){
cur = cur.right;
} else{
cur = cur.left;
}
}
if (cur == null){
return;
}
if (cur.left == null && cur.right == null){
if (parent == null){
this.root = null;
} else{
if (parent.left == cur){
parent.left = null;
} else{
parent.right = null;
}
}
} else if (cur.left != null && cur.right == null || cur.left == null && cur.right != null){
if (parent == null){
if (cur.left != null){
this.root = cur.left;
} else{
this.root = cur.right;
}
} else{
if (parent.left == cur){
if (cur.left != null){
parent.left = cur.left;
} else{
parent.left = cur.right;
}
} else{
if (cur.left != null){
parent.right = cur.left;
} else{
parent.right = cur.right;
}
}
}
} else if (cur.left != null && cur.right != null){
predecessor = cur;
successor = predecessor.left;
while(successor.right != null){
predecessor = successor;
successor = successor.right;
}
if (predecessor == cur){
cur.data = successor.data;
cur.left = successor.left;
} else{
cur.data = successor.data;
predecessor.right = successor.left;
}
}
}
public void traversal(Node cur){
if (cur == null){
return;
}
traversal(cur.left);
System.out.print(cur.data + " ");
traversal(cur.right);
}
}
public class StudyCode {
public static void main(String[] args){
BinarySearchTree bst = new BinarySearchTree();
/*
bst.addNode(20);
bst.addNode(30);
bst.addNode(10);
bst.addNode(5);
bst.addNode(3);
bst.addNode(8);
bst.addNode(12);
bst.addNode(11);
bst.addNode(14);
bst.addNode(23);
bst.addNode(34);
bst.traversal(bst.root);
System.out.println();
bst.removeNode(12);
bst.removeNode(10);
bst.traversal(bst.root);
System.out.println();
*/
bst.addNode(10);
bst.addNode(5);
bst.addNode(20);
bst.traversal(bst.root);
System.out.println();
bst.removeNode(10);
bst.traversal(bst.root);
}
}
