자바 [JAVA] - Binary Search Tree (이진 탐색 트리) 구현하기
자료구조 관련 목록 링크 펼치기
0. 자바 컬렉션 프레임워크 (Java Collections Framework)
3. 단일 연결리스트 (Singly LinkedList)
4. 이중 연결리스트 (Doubly LinkedList)
6. 스택 (Stack)
11. 연결리스트 덱 (LinkedList Deque)
12. 배열 힙 (Heap)
15. 해시 셋 (Hash Set)
17. 이진 탐색 트리 (Binary Search Tree) - [현재 페이지]
- Binary Search Tree
일단 이 글을 읽기전에 만약 제네릭에 대해 잘 모른다면 아래 글을 참고하시길 바란다.
오늘은 Tree의 일종인 이진 탐색 트리(Binary Search Tree)에 대해 알아보고자 한다.
만약 필자의 자료구 글을 쭉 봐왔다면 의문이 하나 들 수 있다.
"왜 Linked Hash Set 다음에 Binary Search Tree이지??"
이유는 다름이 아니라 그 다음에 구현해야 할 Set 중 하나가 TreeSet이기 때문이다. 아직 포스팅은 안했지만, 잠깐 살짝 언급하자면, TreeSet은 Red-Black Tree(레드 블랙 트리)를 기반으로 구현된다.
그럼 왜 Red-Black Tree가 아닌 Binary Search Tree 인가..?
일단, Red-Black Tree는 이론적으로 구현이 상당히 어려운 자료구조 중 하나다. 즉, Tree 자료구조에 대한 기본 지식이 탄탄하지 못한다면 Red-Black Tree를 암만 구현한다 한들 이해를 하고 구현하는 것이 아닌 그냥 베끼기 수준에 그칠 수밖에 없다.
그렇기에 Tree에서 가장 기본적인 Binary Search Tree를 구현해본 뒤, Red-Black Tree, AVL Tree 를 구현해본 다음에 TreeSet으로 넘어갈 예정이다.
[Tree 란]
먼저 Binary Search Tree를 보면 3개의 단어가 합쳐진 것을 알 수 있다.
바로 Binary(이진), Search(탐색), Tree(트리)이다.
즉, 이분화된 탐색을 위한(혹은 특화된) 트리 자료구조라는 뜻이다.
그러면 일단 가장 먼저 트리가 무엇인지부터 보자.
트리는 사실 필자가 힙 및 우선순위 큐를 다루었을 때 이미 한 번 다뤘었 던 적이 있다.
그렇지만, 그 글을 다시 찾아가기 귀찮을 수 있으니 내용이 중복되더라도 다시 한 번 트리(tree)가 무엇인지 잠깐 보고가자.
위와같은 구조를 Tree 구조라고 한다. 위 그림을 거꾸로 보면 나무같이 생겨서 tree구조라고 한다. 여기서 몇 가지 알아야 할 것이 있다. 이 부분만 짚자면 아래와 같다.
부모 노드(parent node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 높은 노드를 의미 (ex. F의 부모노드 : B)
자식 노드(child node) : 자기 자신(노드)과 연결 된 노드 중 자신보다 낮은 노드를 의미 (ex. C의 자식노드 : G, H)
루트 노드 (root node) : 일명 뿌리 노드라고 하며 루트 노드는 하나의 트리에선 하나밖에 존재하지 않고, 부모노드가 없다. 위 이미지에선 녹색이 뿌리노드다.
단말 노드(leaf node) : 리프 노드라고도 불리며 자식 노드가 없는 노드를 의미한다. 위 이미지에서 주황색 노드가 단말노드다.
내부 노드(internal node) : 단말 노드가 아닌 노드
형제 노드(sibling node) : 부모가 같은 노드를 말한다. (ex. D, E, F는 모두 부모노드가 B이므로 D, E, F는 형제노드다.)
깊이(depth) : 특정 노드에 도달하기 위해 거쳐가야 하는 '간선의 개수'를 의미 (ex. F의 깊이 : A→B→F 이므로 깊이는 2가 됨)
레벨(level) : 특정 깊이에 있는 노드들의 집합을 말하며, 구현하는 사람에 따라 0 또는 1부터 시작한다. (ex. D, E, F, G, H)
차수(degree) : 특정 노드가 하위(자식) 노드와 연결 된 개수 (ex. B의 차수 = 3 {D, E, F} )
이 정도만 알고 있으면 된다.
그러면 Binary(이진)은 무슨 뜻일까? 쉽게 말해 이분화 된다는 것이다.
앞서 본 트리 구조에서 특정한 형태로 제한을 하게 되는데, 모든 노드의 최대 차수를 2로 제한한 것이다. 조금 쉽게 말하자면 각 노드는 자식노드를 최대 2개까지밖에 못갖는다는 것이다. 이를 '이진 트리(Binary Tree)'라고 한다.
위의 이미지에서는 B노드가 차수가 3이므로 이진트리가 아니다. 즉, 이진트리의 경우 다음과 같은 형태를 띈다.
그럼 이제 마지막으로 탐색에 특화 된 트리는 무엇을 의미할까?
일단, 한 번 고민을 해보자. 만약 위 이진트리의 각 노드가 갖고있는 값이 규칙 없이 중구난방이면 특정 값을 찾기 위해서는 최악의 경우 저 각각의 노드를 모두 순회(탐색)해야 한다.
이를 방지하고자 위 이진트리에서 우리는 조건을 하나 더 붙이게 된다.
"부모 노드를 기준으로 왼쪽 자식 노드들은 부모 노드보다 값이 작으며, 오른쪽 자식 노드들은 부모 노드보다 값이 크다"
조금 더 줄여 말하자면 나를 부모 노드라고 할 때 자신보다 작은 값은 왼쪽 자식노드, 자신보다 큰 값은 오른쪽 노드에 배정한다는 것이다.
이해를 돕기 위해 이미지로 보자면 아래와 같다.
굳이 왜 P 위에 ...을 두었는가를 얘기하자면, 위 조건은 각 노드들 모두가 만족해야한다는 의미다.
만약 Binary Tree에서 설명했던 이미지를 기준으로 예시를 들자면 다음과 같다.
위와 같이 부모 노드 기준으로 대소 관계에 따라 왼쪽엔 작은 값이, 오른쪽엔 큰 값이 들어가도록 구성하면 된다.
이렇게 구성사면 우리가 특정 값을 탐색하려 할 때 다음과 같은 장점이 있다.
현재 탐색 노드와 찾으려는 값의 대소 관계를 비교해서 작다면 왼쪽 노드로 탐색하러 가면 되고, 반대로 크면 오른쪽 노드로, 같다면 그 값을 찾게 된 것이다.
이렇게 구성하면 우리가 원하는 이진 탐색 트리가 되는 것이다.
여기서 참고해야 할 상황이 있다.
"만약 이미 트리에 있는 값을 중복해서 추가하면 어떻게 되나요?"
이 질문에 대해 잠깐 답을 하고 넘어가는게 좋을 것 같다. 일반적으로 알고리즘은 중복되는 값을 허용하지 않는 방향으로 구현을 많이한다. 이진 탐색 트리, 줄여서 BST의 경우 검색을 용이하게 하기 위한 자료구조이면서 위 메커니즘은 일종의 탐색 알고리즘으로도 많이 쓰여 아마 필자 뿐만 아니라 대부분의 블로거 분들 또한 중복 원소에 대해서는 허용하지 않는 방향으로 구현을 할 것이다.
물론 중복원소를 구현하는 것은 그리 어렵지 않다.
앞서 말했던 "부모 노드를 기준으로 왼쪽 자식 노드들은 부모 노드보다 값이 작으며, 오른쪽 자식 노드들은 부모 노드보다 값이 크다"
이 조건을 왼쪽 혹은 오른쪽 자식노드 중 하나를 선택해서 같을 경우의 조건도 붙여주면 된다.
쉽게말해 왼쪽 노드 조건을 부모랑 같거나 작은으로 바꿀 수도 있고, 혹은 오른쪽 노드 조건을 부모랑 같거나 큰으로 바꾸면 될 뿐이다.
(단, 양쪽 노드 모두 같을경우를 적용하면 안된다)
일단, 필자는 중복 원소는 허용하지 않을 생각이다.
또한 이 글과 연계하여 나중에 쓰게 될 TreeSet도 중복 원소를 허용하지 않는 Set 자료구조이기 때문에 지금은 중복 원소를 굳이 고려해줄 필요가 없다고 판단한 것도 있다. 이 점 참고하시기를 바란다.
또한 이 글과 앞으로 쓸 Tree 자료구조들은(TreeSet 제외) 따로 Interface를 다루진 않을 것이다. 애초에 필자가 기획한 자료구조는 자바 컬렉션 프레임워크를 중점으로 다루는 것이라 이 Tree 자료구조는 약간 번외편으로 두는 것이라 따로 설명할 필요가 없을 것 같기도 하고, 더군다나 이미 Heap에서 한 번 다뤘었기 때문에 굳이 중복하여 내용을 올릴 필요가 없어 보이기 때문이다.
그리고 중요한 점이 있다.
필자는 add 메소드와 remove 메소드를 재귀를 활용하지 않고 반복문만을 활용하여 구현 할 것이다.
필자의 자료구조 글들을 보면 알겠지만, 불가피한 상황 혹은 재귀로 구현하더라도 반복문과 큰 차이가 없을 경우를 제외하곤 쓰지 않는다.
또한 필자가 이 글을 쓰기 전에 BinarySearchTree를 구현한 다른 글들을 살펴보았는데, 반복문으로 구현한 글이 거의 찾아보기 힘들기도 하여 반복문으로 구현하는 것이 좀 더 가치가 있을 것 같다고 생각이 든다.
그렇다고 오해하면 안되는 것이 재귀로 구현한게 잘못되었다거나 나쁘다가 아니다. 오히려 Tree라는 자료구조를 처음 마주 할 때엔 재귀적 접근 방식이 훨씬 이해하기 편하다. 그렇기 때문에 혹여 재귀적으로 쉽게 구현하고 싶다면 다른 블로거분들의 글을 보시는 것이 오히려 현명하실 수도 있다.
필자가 최대한 이해하기 쉽게 설명은 하겠지만, 아무래도 반복문으로는 설명해야 할 내용도 좀 더 많아지고, 결정적으로 명필가는 아니기에.. 이해가 안된다면 댓글로 질문 남겨주시면 최대한 설명드리려 할 것이고 만약 그래도 이해가 안된다하시면.. 미리 죄송하다고 말을 드리고 싶다.
그럼 본격적으로 가보도록 하자.
- Node 구현
기본적으로 Tree는 Node를 기반으로 구성된다. 물론 배열로도 구현은 가능하지만, 이후 있을 Tree 자료구조들에선 '회전'이라는 개념이 등장하기 때문에 오히려 노드로 구현하는게 좀 더 용이하다.
앞선 설명에서도 보셨듯 일단 Tree에 필요한 노드(Node)는 다음과 같이 구성된다.
[Node.java]
class Node<E> {
E value;
/*
* 부모 노드는 BinarySearchTree에서는 당장 쓰이진 않으나
* 추후 용이하게 쓰이니 미리 부모노드를 가리키는 변수도 같이
* 구현하면서 익숙해지는 것이 좋다.
*/
Node<E> left;
Node<E> right;
Node<E> parent;
Node(E value) {
this(value, null);
}
Node(E value, Node<E> parent) {
this.value = value;
this.parent = parent;
this.right = null;
this.left = null;
}
}
위 주석으로도 쓰여있지만, 사실 Binary Search Tree 에서는 parent를 가리키는 변수를 필요로 하진 않는다.
그저 root노드에서 child노드로 단방향으로 값을 비교해나가면서 탐색 방향을 정하고 조건에 맞는 위치로 가게 되면 삭제, 삽입, 반환 등 작업을 하기 때문에 당장은 필요 없으나, 앞으로 Red-Black Tree, AVL Tree 등 다양한 심화 트리 자료구조에선 parent 정보를 담고있는 것이 매우 유용하기 때문에 미리 익숙해질 겸 넣었다.
또한 이후 구현 때 어차피 Binary Search Tree 을 기반으로 하기 때문에 그 때 가서 부모노드를 다시 수정해서 Binary Search Tree를 재구성 하는 것 보단 그대로 응용 할 수 있도록 연속성 측면에서도 이렇게 하는게 맞겠다 싶었다.
- BinarySearchTree 구현
[구현 바로가기]
<필수 목록>
◦ size, isEmpty, contains, clear 메소드 구현
<부가 목록>
◦ 순회 구현
◦ 전체 코드
[BinarySearchTree 클래스 및 생성자 구성하기]
이 번에 구현 할 BinarySearchTree는 Node를 기반으로 데이터를 저장하는 방식으로 LinkedList와 유사한 성격을 보인다. 그러므로 만약 앞선 기초적인 LinkedList 를 구현해본 적이 없다면 단일연결리스트(SinglyLinkedList) 글을 보고 먼저 구현해오시는 것을 추천드린다.
[BinarySearchTree.java]
import java.util.Comparator;
public class BinarySearchTree<E> {
private Node<E> root; // 루트(최상단) 노드
private int size; // 요소(노드)의 개수
private final Comparator<? super E> comparator;
public BinarySearchTree() {
this(null);
}
public BinarySearchTree(Comparator<? super E> comparator) {
this.comparator = comparator;
this.root = null;
this.size = 0;
}
}
변수부터 먼저 차례대로 설명해주도록 하겠다.
root : BinarySearchTree의 최상단 노드, 즉 루트 노드를 가리키고 있는 변수다.
size : BinarySearchTree가 갖고있는 요소(원소)의 개수 변수다.
comparator : 여러분들이 객체를 정렬하고자 할 때, 혹은 임의의 순서로 정렬하고 싶을 때 Comparator 를 파라미터로 받아 설정할 수 있도록 한 변수다.
그리고 생성자는 크게 2가지로 나누었다.
먼저 우리는 BinarySearchTree에서 값의 비교가 필요한 만큼 정렬 방법은 크게 두 가지가 있다. 하나는 Comparable이고, 하나는 Comparator다.
그렇기에 사용자가 별도의 Comparator을 넘겨주지 않는경우 comparator = null로 처리하여 이후 변수 비교 때 Comparable을 사용하도록 하고, 사용자가 정렬 방법을 따로 넘겨주고자 Comparator을 받을 땐 변수 비교를 comparator을 사용하여 쓸 수 있도록 2가지로 나누었다.
또한 처음 BinarySearchTree를 생성 할 때에는 아무런 데이터가 없으므로 당연히 root가 가리킬 노드가 없기에 null로 초기화 및 size는 0으로 초기화 해주도록 한다.
위와같이 구성하면, 만약 사용자가 해당 BinarySearchTree 클래스를 사용용하고자 한다면 다음과 같이 생성 할 수 있을 것이다.
BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
[add 메소드 구현]
본격적으로 BinarySearchTree에 데이터를 삽입해볼 수 있도록 해보자.
BinarySearchTree의 삽입 과정은 크게 두 가지로 나뉜다.
1. 사용자가 Comparator을 사용하여 정렬 방법을 BinarySearchTree 생성단계에서 넘겨받은 경우 (comparator가 null이 아닌 경우)
2. 클래스 내에 정렬 방식을 Comparable로 구현했거나 기본 정렬 방식을 따르는 경우 (comparator가 null인 경우)
이 것을 기억하고, 한 번 삽입 과정을 보자.
위 예시처럼 만약 삽입하려는 데이터가 14라고 가정하자.
그리고 root부터 시작하여 값을 비교하여 현재 value가 current노드보다 작다면 왼쪽노드(left)로, 크다면 오른쪽(right)노드로 비교할 노드인 current노드를 갱신하는 것이다. 그러다가 빈 노드(null Node)을 만나게 되면, 직전에 탐색했던 노드를 가리키는 currentParent 노드의 자식에 연결하면 된다.
위 예시에서 나오지 않는 케이스가 있다.
"만약에 탐색과정 중에 value랑 값이 같은 노드가 있다면?"
이럴 때는 탐색을 중단해버리면 된다.
코드로 보자면 다음과 같다. 최대한 이해하기 쉽게 주석을 달아놓겠다.
/**
* Binary Search Tree에 삽입하는 메소드
*
* @param value 삽입하고자 하는 데이터
* @return 정상적으로 삽입 되었을 경우 true, 중복 원소를 삽입할 경우 false를 반환
*/
public boolean add(E value) {
/*
* comparator(사용자 지정 비교기)가 없을 경우(=null)에는 Comparable,
* 있을 경우에는 Comparator를 사용하는 메소드로 보낸다.
* 그리고, 각 메소드는 정상적으로 삽입이 완료되었다면 null을 반환할 것이고,
* 중복 원소를 삽입 할 경우 해당 value를 반환할 것이기 때문에
* 비교 연산으로 null인지 아닌지 여부를 반환한다.
*/
if(comparator == null) {
return addUsingComparable(value) == null;
}
return addUsingComparator(value, comparator) == null;
}
// Comparable을 이용한 add메소드
private E addUsingComparable(E value) {
Node<E> current = root; // 탐색할 노드를 가리키는 current node
// 만약 current가 null, 즉 root가 null이면 root에 새 노드를 만들고 null반환
if(current == null) {
root = new Node<E>(value);
size++;
return null;
}
Node<E> currentParent; // current의 직전 탐색 노드를 가리키는 노드
// 삽입 할 노드가 비교 될 수 있도록 한 변수를 만든다.
@SuppressWarnings("unchecked")
Comparable<? super E> compValue = (Comparable<? super E>) value;
int compResult; // 비교 결과(양수, 0, 음수)를 담고 있을 변수
do {
// 다음 순회에서 current의 부모노드를 가리킬 수 있도록 현재 current를 저장
currentParent = current;
compResult = compValue.compareTo(current.value);
/*
* 비교 결과 value 보다 current.value 보다 작으면
* current를 current의 왼쪽 자식으로 갱신하고,
* value보다 current.value가 크다면 current를 오른쪽
* 자식으로 갱신하며, 같을 경우 순회를 중단하고 value를 반환한다.
*/
if(compResult < 0) {
current = current.left;
} else if(compResult > 0) {
current = current.right;
}
else {
return value;
}
} while(current != null);
// 순회가 완료되어 삽입해야 할 위치를 찾았다면 삽입 할 value를 노드로 만든다.
Node<E> newNode = new Node<E>(value, currentParent);
// 직전 비교 결과에 따라 currentParent의 오른쪽 혹은 왼쪽 노드에 새 노드를 연결해준다.
if(compResult < 0) {
currentParent.left = newNode;
}
else {
currentParent.right = newNode;
}
size++;
return null;
}
// Comparator을 이용한 add
private E addUsingComparator(E value, Comparator<? super E> comp) {
Node<E> current = root;
if(current == null) {
root = new Node<E>(value, null);
size++;
return null;
}
Node<E> currentParent;
int compResult;
do {
currentParent = current;
compResult = comp.compare(value, current.value);
if(compResult < 0) {
current = current.left;
}
else if(compResult > 0) {
current = current.right;
}
else {
return value;
}
} while(current != null);
Node<E> newNode = new Node<E>(value, currentParent);
if(compResult < 0) {
currentParent.left = newNode;
}
else {
currentParent.right = newNode;
}
size++;
return null;
}
comparator에 대해서는 파라미터로 넘어온 Comparator로 비교하는 것만 다를 뿐 로직 자체는 같기 때문에 별다른 주석은 안달았다.
[remove 메소드 구현]
그럼 삭제 및 반환은 어떻게 구현해야할까? 아마 여기서 많은 분들이 가장 어렵게 느낄 것이다.
실제로도 다른 구현부보다 삭제 구현이 가장 많은 양을 담당하게 될 것이다.
그렇다고 그냥 넘어가지 말고 최대한 풀어서 이해하기 쉽도록 풀어쓰려 노력할테니 천천히 따라오면서, 이해가 안되는 부분은 댓글로 남겨주시기를 바란다.
일단 삭제 노드를 찾는 것은 위 add 메소드와 과정 자체는 유사하다.
add메소드에서는 같은 값을 갖는 노드가 있으면 탐색을 중단하고 그대로 값을 반환했었다. 그리고 current 노드가 null일 경우 해당 위치에 삽입하려는 값을 노드로 새로 연결시켰다.
remove도 탐색과정은 같다. 다만 remove메소드는 같은 값을 찾으면 그 노드를 삭제해야하고, 반대로 null일 경우 삭제할 노드가 없는것이다.
우리가 노드를 삭제해야 할 때 반드시 고려해야할 점이 있다. 바로 노드가 삭제되더라도 이진탐색트리를 만족해야 한다는 것이다. 이 부분은 차차 삭제 과정을 설명하면서 왜 중요한지 알아보기로 하고..
그럼 일단 삭제할 노드를 찾았다고 가정하고 노드를 삭제할 때 발생 할 수 있는 경우들을 생각해보자.
일단 노드가 삭제 될 때, 크게 3가지 경우로 나눠 볼 수 있다.
1. 삭제하는 노드가 자식노드를 갖고 있지 않을 때
2. 삭제하는 노드가 왼쪽 또는 오른쪽 자식 노드를 갖고 있을 때
3. 삭제하는 노드가 왼쪽, 오른쪽 자식 노드 모두 갖고 있을 때
즉, 이미지로 보면 이렇다.
위 처럼 삭제 할 자식노드를 갖고 있지 않을 땐 해당 노드만 삭제해주면 되기 때문에 별다른 어려움은 없어보인다.
위와 같이 한쪽의 자식노드만 있을 경우엔 그 자식노드를 삭제한 노드의 위치로 끌고오기만 하면 되기 때문에 그리 어려운 작업은 아니다.
좀 더 직관적으로 보자면 다음과 같다.
즉, 왼쪽 혹은 오른쪽 자식 노드 중 한 쪽만 갖고 있다면 그대로 삭제된 노드를 대체하더라도 Binary Search Tree의 조건을 만족할 수 있다.
근데, 문제는 다음과 같다.
위와 같이 중간에 껴있는 노드를 삭제할 경우 어떻게 할 것이냐는거다.
일단 저기 빈 공간을 다른 노드로 대체해야 하긴 할 것 같은데.. 무엇을 대체해야 할까?
여기서 우리는 조금 고민을 해야한다. 이 부분이 트리에서 가장 어려운 부분이라 천천히 이해하면서 넘어가보도록 하자.
일단 Binary Search Tree 조건에 맞추면서 트리 형태를 유지를 해야한다. "그냥 7 노드를 위로 올리면 되는거 아니에요?" 라고 할 수도 있지만, 만약에 7 노드의 자식 노드가 두 개 모두 있을 경우에는 그럼 어떻게 할 것인가?
만약 그런 경우라면 자식노드가 3개가 되어버리는 문제가 생긴다.
좀 더 이해하기 쉬운 이미지로 보자면 이렇다.
위 방식으로는 결국 Binary Search Tree의 조건을 만족시키지 못한다는 것을 볼 수 있다.
그러면 어떻게 해결해야 할까.
여기에는 크게 두 가지 해법이 있다.
1. 삭제된 노드의 오른쪽 자식 노드에서 제일 작은 노드로 대체하는 방법
2. 삭제된 노드의 왼쪽 자식 노드에서 제일 큰 노드로 대체하는 방법
일단, 왜 오른쪽 자식 노드에선 제일 작은 노드 혹은 왼쪽 자식 노드에선 제일 큰 노드로 대체해야하는지 그 이유를 이해해야한다.
Binary Search Tree 처음 설명에서 이미지와 함께 필자가 언급했던 한 규칙이 있다.
스크롤해서 다시 올려보기 귀찮으실테니 다시 한 번 이미지를 갖고왔다.
위 이미지를 보자. 자기 노드보다 작은 것은 왼쪽 자식노드로, 자기 노드보다 큰 노드는 오른쪽 자식노드로 갖는다는 것이다.
그렇다면, 위 구조를 재귀적으로 생각해본다면 P 노드에서 값이 가장 가까운 두 노드는 무엇일까?
바로 P 왼쪽 자식노드에서 가장 오른쪽에 있는 노드, 그리고 P의 오른쪽 자식노드에서 가장 왼쪽에 있는 노드가 될 것이다.
감이 안잡힌다면 다음 이미지를 보자.
위와 같이 좀 더 구체적인 예시로 보면 확 와닿을 것이다.
예로들어 D노드를 기준으로 가장 가까운 값을 갖는 두 노드라면? 다음과 같을 것이다.
위와 같이 Q, R 노드가 D와 가장 가까운 값을 갖는 노드가 될 것이다.
하나만 예를 더 들어보자. 만약에 B노드라면??
감이 잡히시는가? 이렇듯, 우리가 삭제하는 노드에 대해 가장 가까운 값으로 대체하기 위해서는 왼쪽 자식 노드에서 가장 큰 노드(=가장 오른쪽에 위치한 노드) 혹은 오른쪽 자식 노드에서 가장 작은 노드(=가장 왼쪽에 위치한 노드) 중 하나를 선택하면 되는 것이다.
다시 정리하자면 이렇다.
대체할 노드를 선정하는 방법은 다음과 같다.
방법 1. 삭제된 노드의 오른쪽 자식 노드에서 제일 작은 노드로 대체하는 방법
방법 2. 삭제된 노드의 왼쪽 자식 노드에서 제일 큰 노드로 대체하는 방법
일단 필자는 방법 1을 기준으로 설명할 것이나, 방법 2로 하고싶은 분들의 경우 필자가 작성하는 코드의 반대로 작성하면 된다.
자, 그러면 일단, 삭제할 노드는 찾았다고 가정하고, 삭제할 노드에서 가장 가까운 노드를 찾는 메소드를 만들어보자.
일단, 오른쪽 자식노드에서 가장작은 노드를 탐색한다한다면, 계속 왼쪽 자식 노드를 찾아나가면 된다. 문제는 최종적으로 대체할 노드가 선정되었을 때다.
대체할 노드가 선정되었을 경우 일단, 해당 노드를 원래 참조하고 있던 부모 노드와의 링크도 끊어주어야 한다.
그리고 결정적으로 여기서 많이 잘못된 코드를 올리곤 하는데, 가장 작은 노드를 찾았다고 한들, 그 가장 작은 노드가 자식 노드를 갖고있지 않는다는 의미가 아니다. 우리는 왼쪽 자식노드로만 계속 탐색했기 때문에 가장 작은 노드가 왼쪽 자식노드는 갖고있지 않는다는 것은 보장되나, 오른쪽 자식노드는 갖고있을 수 있다는 것이다.
말로하면 이해가 되지 않을 것이니 그런 경우에 대한 예시 이미지를 한 번 보자.
위 처럼 B노드의 오른쪽 자식 노드(E)를 기준으로 가장 작은 노드는 J노드다. 하지만 E와 J노드만 연결을 끊어주면 끝나는 것이 아니라, J노드의 오른쪽 자식노드가 있다면 이를 E노드와 연결을 해주어야한다는 것이다. (사실 연결을 끊는다기보다는 값(value)을 대체해주는 것이다.)
필자도 글을 찾다보니 의외로 이 부분을 고려하지 못하고 구현한 코드가 많았는데 만약 위와 같은 케이스를 인지하지 못하고 구현하면, P노드를 포함한 그의 자식노드들까지 모두 버려지는 불상사가 발생한다.
자 그럼, 이제 정리를 해보자.
노드를 삭제하는 경우 크게 3가지가 존재했다.
1. 삭제하는 노드가 자식노드를 갖고 있지 않을 때
2. 삭제하는 노드가 왼쪽 또는 오른쪽 자식 노드를 갖고 있을 때
3. 삭제하는 노드가 왼쪽, 오른쪽 자식 노드 모두 갖고 있을 때
하나씩 다시 살펴보면
[삭제하는 노드가 자식노드를 갖고 있지 않을 때]
이 경우에는 해당 노드만 삭제해주면 끝난다.
[삭제하는 노드가 왼쪽 또는 오른쪽 자식 노드를 갖고 있을 때]
이 경우 자식노드를 삭제노드의 위치로 옮겨오면 끝난다.
[삭제하는 노드가 왼쪽, 오른쪽 자식 노드 모두 갖고 있을 때]
이 경우 '삭제하는 노드의 오른쪽 자식 노드에서 가장 작은 노드'를 갖고 온 뒤, 해당 노드를 삭제하고자 하는 노드에 대체한다.
이 때 우리는 대체할 노드를 후계자(Successor)라고 한다. 즉, 양쪽 자식 모두 있을 때는 이 후계자를 찾는 과정이 하나 더 들어간다는 것이다.
그러면 일단, 후계자(Successor)를 찾는 메소드부터 차근차근 구현해보자.
일단, 삭제할 노드가 주어질 것이다. 그러면 가장 먼저 해야 할 것이 바로 '오른쪽 노드'를 갖고 온뒤 거기서부터 가장 작은 노드를 찾아가는 것이다. 코드로 보면 다음과 같다.
/**
* 삭제되는 노드의 자리를 대체할 노드(후계자)를 찾는 메소드
* (오른쪽 자식 노드 중 가장 작은 노드를 찾음)
*
* @param node 삭제되는 노드(=대체되어야 할 노드)
* @return 대체할 노드
*/
private Node<E> getSuccessorAndUnlink(Node<E> node) {
Node<E> currentParent = node; // 대체 할 노드의 부모노드를 가리키는 노드
Node<E> current = node.right; // 초기에 오른쪽 자식 노드를 가리키도록 한다.
/**
* 처음 탐색하게되는 오른쪽 자식 노드(current)에서
* current의 왼쪽 자식이 없다는 것은 current노드,
* 즉 오른쪽 첫 자식노드가 대체되는 노드가 된다는 것이다.
*
* 그렇기 때문에 대체해야하는 노드는 삭제되는 노드의 오른쪽 자식이 되며
* 이에 대체되는 노드 자리(currentParent)의 오른쪽 자식은
* current의 오른쪽 자식을 가리키고, currentParent는 이후
* current의 값이 반환되고, 상위 메소드에서 currentParent자리에
* 값이 대체되게 된다.
*/
if (current.left == null) {
currentParent.right = current.right;
if (currentParent.right != null) {
currentParent.right.parent = currentParent;
}
current.right = null;
return current;
}
// 가장 작은 노드를 찾을 때 까지 반복한다.
while (current.left != null) {
currentParent = current;
current = current.left;
}
/*
* 만약 후계자가 될 노드(가장 작은 노드)의 오른쪽 노드가 존재한다면
* currentParent의 왼쪽 자식노드는 오른쪽 자식노드와 연결되어야 한다.
*
* 만약 current.right = null 이라면
* 후계자가 될 노드의 자식노드는 존재하지 않으므로 자연스럽게
* 후계자 노드의 부모노드는 후계자가 다른노드로 대체되러 가기 때문에
* 후계자의 부모노드의 왼쪽자식노드는 자연스럽게 null을 가리키게 된다.
*/
currentParent.left = current.right;
if (currentParent.left != null) {
currentParent.left.parent = currentParent;
}
current.right = null;
return current;
}
코드가 그렇게 복잡하진 않다. (또한 필자가 앞서 parent변수가 당장 필요하진 않다고 했던만큼 만약 parent변수를 안쓰고 구현할 것이라면 parent 를 새로 연결해주는 부분은 삭제해도 된다.)
그런데 필자가 위에서 설명하지 못한 부분이 있다. 주석에도 써놓았듯 바로 삭제할 노드를 대체할 후계자 노드가 바로 오른쪽 자식으로 오른쪽 자식노드가 가장 작은 값일 경우다.
여기서 하나 의문이 드는 사람은 아래 접은 글을 보길 바란다.
"왜 후계자 노드를 그대로 갖고와서 연결하지 않고 링크를 끊은 다음 굳이 값을 대체해야 하는 이유가 뭔가요?"
이러한 질문이 있을 수 있을 것 같다.
걷보기에는 successor 노드를 remove노드에 대체만 해주면 될 것 같지만, 실제로는 더 복잡해진다.
생각해보자. remove node는 이미 양쪽 자식을 반드시 갖고있는 경우다. 이 말은 remove node와 연결 되어있는 노드는 총 3개라는 것이다. remove 노드의 부모노드, remove 노드의 왼쪽 노드, remove 노드의 오른쪽 노드 이렇게 말이다.
만약 successor 노드를 그대로 대체할 경우 remove 노드와 연결 된 모든 링크를 끊은 뒤, successor 노드에 remove 노드의 부모노드와 왼쪽 자식노드를 새로 연결해야 한다.
이 때, 그렇다면, remove 노드의 부모노드하고는 어떻게 연결할 것인가?
결국 remove 노드의 부모 노드도 알고있어야 한다. 물론 필자가 node 변수에서 parent 변수를 두었기 때문에 remove.parent 를 통해 remove 노드의 부모 노드를 갖고와 해당 노드의 자식 노드를 successor 노드를 가리키도록 할 순 있으나, 만약 parent 변수를 두지 않았을 경우에는 훨씬 복잡해진다.
이러한 이유로, 굳이 링크를 모두 끊을 필요 없이 이미 연결 된 링크는 유지한 채 데이터(value)만 바꿔주는 것이 훨씬 구현하기도 쉽다.
그러면 일단, 삭제할 노드의 양 쪽 자식 노드가 모두 존재할 경우에 대해 가장 가까운(대체 할)노드를 찾아 반환하는 메소드를 만들었으니
1. 삭제하는 노드가 자식노드를 갖고 있지 않을 때
2. 삭제하는 노드가 왼쪽 또는 오른쪽 자식 노드를 갖고 있을 때
3. 삭제하는 노드가 왼쪽, 오른쪽 자식 노드 모두 갖고 있을 때
이 메소드를 이제 만들어보자.
/**
* 삭제 할 노드에 대해 삭제를 수행하는 메소드
*
* @param node 삭제 할 노드
* @return 삭제 후 대체 되고 난 뒤의 해당 위치의 노드를 반환
*/
private Node<E> deleteNode(Node<E> node) {
if (node != null) {
// 자식노드가 없을 경우
if (node.left == null && node.right == null) {
// 삭제하려는 노드가 root일 경우 root를 끊어버리고 종료한다.
if (node == root) {
root = null;
}
// 그 외에는 단말 노드이므로 해당 노드만 삭제한다.
// 자연스럽게 node의 부모노드는 null을 참조하게 됨
else {
node = null;
}
return null;
}
// 양쪽의 자식노드가 모두 있을 경우
if (node.left != null && node.right != null) {
// 대체 노드를 찾아온다. (앞선 만들었던 후계자를 찾는 메소드다)
Node<E> replacement = getSuccessorAndUnlink(node);
// 삭제 된 노드에 대체 노드의 값을 대체해준다.
node.value = replacement.value;
}
// 왼쪽 노드만 존재할 경우
else if (node.left != null) {
/*
* 삭제할 노드가 root일 경우 왼쪽자식 노드(대체되는 노드)를
* 삭제할 노드로 옮긴 다음 root를 대체노드를 가리키도록 변경한다
*/
if (node == root) {
node = node.left;
root = node;
root.parent = null;
} else {
node = node.left;
}
}
// 오른쪽 노드만 존재할 경우
else {
/*
* 삭제할 노드가 root일 경우 오른쪽자식 노드(대체되는 노드)를
* 삭제할 노드로 옮긴 다음 root를 대체노드를 가리키도록 변경한다
*/
if (node == root) {
node = node.right;
root = node;
root.parent = null;
} else {
node = node.right;
}
}
}
return node;
}
그러면 '삭제할 노드를 찾았다는 가정하에' 삭제하는 메소드까지는 구현이 끝났다.
이제 실제로 임의의 값이 주어지면 '값이 같은 삭제할 노드'를 찾아낸 뒤, 해당 노드를 바로 위에서 만들었던 deleteNode 메소드로 보내면 삭제 메소드 구현은 끝난다.
이 전의 add 메소드와 똑같이 Comparable, Comparator 경우를 나누어서 구현하겠다.
/**
* 삭제 메소드
* @param o 삭제할 값
* @return 삭제 된 노드의 value 값 혹은 매칭 값이 없을 경우 null을 반환한다.
*/
public E remove(Object o) {
if (root == null) {
return null;
}
if (comparator == null) {
return removeUsingComparable(o);
} else {
return removeUsingComparator(o, comparator);
}
}
/**
* Comparable을 이용한 데이터 삭제
*
* @param value 삭제하고자 하는 데이터
* @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
*/
private E removeUsingComparable(Object value) {
@SuppressWarnings("unchecked")
E oldVal = (E) value;
Node<E> parent = null, current = root;
// 삭제하고자 하는 노드가 부모 노드로부터 왼쪽 자식 노드인지 오른쪽 자식 노드인지 알기 위한 변수
boolean hasLeft = false;
if (root == null) {
return null;
}
@SuppressWarnings("unchecked")
Comparable<? super E> compValue = (Comparable<? super E>) value;
// 삭제할 노드를 찾는다.
do {
int resComp = compValue.compareTo(current.value);
if (resComp == 0) {
break;
}
parent = current;
if (resComp < 0) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
} while (current != null);
// 만약 탐색 끝에 삭제해야할 노드를 찾지 못했다면 null 반환
if (current == null) {
return null;
}
// 부모 노드가 없을 경우 == 삭제하는 노드가 root일 경우
if (parent == null) {
deleteNode(current);
size--;
return oldVal;
}
// 삭제 노드가 부모노드의 왼쪽 자식일 경우
if (hasLeft) {
parent.left = deleteNode(current);
// 만약 새로 이어질 노드가 존재한다면, 해당 대체 노드의 부모노드도 갱신
if (parent.left != null) {
parent.left.parent = parent;
}
}
// 삭제 노드가 부모노드의 오른쪽 자식일 경우
else {
parent.right = deleteNode(current);
// 만약 새로 이어질 노드가 존재한다면, 해당 대체 노드의 부모노드도 갱신
if (parent.right != null) {
parent.right.parent = parent;
}
}
size--;
return oldVal;
}
/**
* Comparator을 이용한 데이터 삭제
*
* @param value 삭제하고자 하는 데이터
* @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
*/
private E removeUsingComparator(Object value, Comparator<? super E> comp) {
@SuppressWarnings("unchecked")
E oldVal = (E) value;
Node<E> parent = null, current = root;
boolean hasLeft = false;
if (root == null) {
return null;
}
@SuppressWarnings("unchecked")
E compValue = (E) value;
do {
int resComp = comp.compare(compValue, current.value);
if (resComp == 0) {
break;
}
parent = current;
if (resComp < 0) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
} while (current != null);
if (current == null) {
return null;
}
if (parent == null) {
deleteNode(current);
size--;
return oldVal;
}
if (hasLeft) {
parent.left = deleteNode(current);
if (parent.left != null) {
parent.left.parent = parent;
}
} else {
parent.right = deleteNode(current);
if (parent.right != null) {
parent.right.parent = parent;
}
}
size--;
return oldVal;
}
위와 같이 작성하면 된다. 참고로 연결을 재구성해야하기 때문에 필자의 코드에선 Node의 parent 정보도 반드시 갱신해야한다. (만약 parent 변수를 사용 안한다면 필요는 없다)
내용이 너무 길었다. 한 번 remove 메소드에 필요한 코드들을 하나로 묶어 보자.
[remove 메소드 묶어보기]
/**
* 삭제 메소드
* @param o 삭제할 값
* @return 삭제 된 노드의 value 값 혹은 매칭 값이 없을 경우 null을 반환한다.
*/
public E remove(Object o) {
if (root == null) {
return null;
}
if (comparator == null) {
return removeUsingComparable(o);
} else {
return removeUsingComparator(o, comparator);
}
}
/**
* Comparable을 이용한 데이터 삭제
*
* @param value 삭제하고자 하는 데이터
* @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
*/
private E removeUsingComparable(Object value) {
@SuppressWarnings("unchecked")
E oldVal = (E) value;
Node<E> parent = null, current = root;
boolean hasLeft = false;
if (root == null) {
return null;
}
@SuppressWarnings("unchecked")
Comparable<? super E> compValue = (Comparable<? super E>) value;
do {
int resComp = compValue.compareTo(current.value);
if (resComp == 0) {
break;
}
parent = current;
if (resComp < 0) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
} while (current != null);
if (current == null) {
return null;
}
if (parent == null) {
deleteNode(current);
size--;
return oldVal;
}
if (hasLeft) {
parent.left = deleteNode(current);
if (parent.left != null) {
parent.left.parent = parent;
}
}
else {
parent.right = deleteNode(current);
if (parent.right != null) {
parent.right.parent = parent;
}
}
size--;
return oldVal;
}
/**
* Comparator을 이용한 데이터 삭제
*
* @param value 삭제하고자 하는 데이터
* @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
*/
private E removeUsingComparator(Object value, Comparator<? super E> comp) {
@SuppressWarnings("unchecked")
E oldVal = (E) value;
Node<E> parent = null, current = root;
boolean hasLeft = false;
if (root == null) {
return null;
}
@SuppressWarnings("unchecked")
E compValue = (E) value;
do {
int resComp = comp.compare(compValue, current.value);
if (resComp == 0) {
break;
}
parent = current;
if (resComp < 0) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
} while (current != null);
if (current == null) {
return null;
}
if (parent == null) {
deleteNode(current);
size--;
return oldVal;
}
if (hasLeft) {
parent.left = deleteNode(current);
if (parent.left != null) {
parent.left.parent = parent;
}
} else {
parent.right = deleteNode(current);
if (parent.right != null) {
parent.right.parent = parent;
}
}
size--;
return oldVal;
}
/**
* 삭제 할 노드에 대해 삭제를 수행하는 메소드
*
* @param node 삭제 할 노드
* @return 삭제 후 대체 되고 난 뒤의 해당 위치의 노드를 반환
*/
private Node<E> deleteNode(Node<E> node) {
if (node != null) {
if (node.left == null && node.right == null) {
if (node == root) {
root = null;
}
else {
node = null;
}
return null;
}
if (node.left != null && node.right != null) {
Node<E> replacement = getSuccessorAndUnlink(node);
node.value = replacement.value;
}
else if (node.left != null) {
if (node == root) {
node = node.left;
root = node;
root.parent = null;
} else {
node = node.left;
}
} else {
if (node == root) {
node = node.right;
root = node;
root.parent = null;
} else {
node = node.right;
}
}
}
return node;
}
/**
* 삭제되는 노드의 자리를 대체할 노드(후계자)를 찾는 메소드
* (오른쪽 자식 노드 중 가장 작은 노드를 찾음)
*
* @param node 삭제되는 노드(=대체되어야 할 노드)
* @return 대체할 노드
*/
private Node<E> getSuccessorAndUnlink(Node<E> node) {
Node<E> currentParent = node;
Node<E> current = node.right;
if (current.left == null) {
currentParent.right = current.right;
if (currentParent.right != null) {
currentParent.right.parent = currentParent;
}
current.right = null;
return current;
}
while (current.left != null) {
currentParent = current;
current = current.left;
}
currentParent.left = current.right;
if (currentParent.left != null) {
currentParent.left.parent = currentParent;
}
current.right = null;
return current;
}
[size, isEmpty, contains, clear 메소드 구현]
진짜 여기까지 오시느라 고생하셨다.. 현재 BinarySearchTree에 저장 된 요소의 개수를 알고 싶을 때 size값을 리턴하기 위한 메소드로 size()를 하나 만들고, 해당 BinarySearchTree이 비어있는 상태인지를 확인하기 위한 isEmpty() 메소드를 만들 것이다.
또한 contains로 찾고자 하는 요소가 BinarySearchTree에 존재하는지 볼 수 있도록 아주 간단하게 구현해볼 것이다.
마지막으로 가끔 BinarySearchTree에 있는 모든 요소들을 비우고싶을 때가 있다. 그럴 때 쓸 수 있는 clear 메소드도 같이 보도록 하자.
size, isEmpty, contains, clear 메소드
/**
* BinarySearchTree에 있는 원소의 개수를 반환해주는 메소드
*
* @return BinarySearchTree에 있는 원소의 개수를 반환
*/
public int size() {
return this.size;
}
/**
* BinarySearchTree가 비어있는지를 판단하는 메소드
*
* @return BinarySearchTree가 비어있을 경우 true, 아닐경우 false를 반환
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* 해당 객체가 BinarySearchTree에 존재하는지를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
public boolean contains(Object o) {
// comparator가 null 일경우 Comparable로 비교하도록 한다.
if (comparator == null) {
return containsUsingComparable(o);
}
return containsUsingComparator(o, comparator);
}
/**
* Comparable을 이용한 객체 존재 여부를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
private boolean containsUsingComparable(Object o) {
// 비교 가능한 변수로 만든다
@SuppressWarnings("unchecked")
Comparable<? super E> value = (Comparable<? super E>) o;
Node<E> node = root;
while (node != null) {
int res = value.compareTo(node.value);
if (res < 0) {
node = node.left;
} else if (res > 0) {
node = node.right;
}
// res == 0 이라는 것은 같다는 의미로 true를 반환
else {
return true;
}
}
return false;
}
/**
* Comparable을 이용한 객체 존재 여부를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @param comparator 사용자에 의해 BinarySearchTree에 지정 된 비교기
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
private boolean containsUsingComparator(Object o, Comparator<? super E> comparator) {
@SuppressWarnings("unchecked")
E value = (E) o;
Node<E> node = root;
while (node != null) {
int res = comparator.compare(value, node.value);
if (res < 0) {
node = node.left;
} else if (res > 0) {
node = node.right;
} else {
return true;
}
}
return false;
}
/**
* BinarySearchTree를 초기화 하는 메소드
*/
public void clear() {
size = 0;
/*
* root를 끊어주면 하위 모든 노드들도 더이상
* 참조할 수 없기 때문에 GC 처리 된다.
*/
root = null;
}
[size, isEmpty, contains, clear 메소드 묶어보기]
/**
* BinarySearchTree에 있는 원소의 개수를 반환해주는 메소드
*
* @return BinarySearchTree에 있는 원소의 개수를 반환
*/
public int size() {
return this.size;
}
/**
* BinarySearchTree가 비어있는지를 판단하는 메소드
*
* @return BinarySearchTree가 비어있을 경우 true, 아닐경우 false를 반환
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* 해당 객체가 BinarySearchTree에 존재하는지를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
public boolean contains(Object o) {
if (comparator == null) {
return containsUsingComparable(o);
}
return containsUsingComparator(o, comparator);
}
/**
* Comparable을 이용한 객체 존재 여부를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
private boolean containsUsingComparable(Object o) {
@SuppressWarnings("unchecked")
Comparable<? super E> value = (Comparable<? super E>) o;
Node<E> node = root;
while (node != null) {
int res = value.compareTo(node.value);
if (res < 0) {
node = node.left;
} else if (res > 0) {
node = node.right;
} else {
return true;
}
}
return false;
}
/**
* Comparable을 이용한 객체 존재 여부를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @param comparator 사용자에 의해 BinarySearchTree에 지정 된 비교기
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
private boolean containsUsingComparator(Object o, Comparator<? super E> comparator) {
@SuppressWarnings("unchecked")
E value = (E) o;
Node<E> node = root;
while (node != null) {
int res = comparator.compare(value, node.value);
if (res < 0) {
node = node.left;
} else if (res > 0) {
node = node.right;
} else {
return true;
}
}
return false;
}
/**
* BinarySearchTree를 초기화 하는 메소드
*/
public void clear() {
size = 0;
root = null;
}
<순회>
[순회 메소드 구현]
이제 BinarySearchTree의 꽃 트리의 순회에 대해 마지막으로 짚고 넘어가보자.
순회를 하기 전 일단 하나의 트리를 놓고 예시를 들어가며 진행해보고자 한다.
그동안 예시로 많이 들었던 트리라 익숙할 것이다.
일단, 한 번 생각해보자. 위 구조를 정말 간략하게 표현하면 어떻게 될까?
위 형식을 '재귀적'으로 구조를 이루는 것이 BinarySearchTree다.
그러면 우리는 트리를 순회 하면서 원소들을 출력하고자 할 때 크게 3개로 나눌 수 있는데, P원소를 출력한 뒤 자식에 대해 탐색을 할 것인지, 혹은 자식 노드를 먼저 탐색하고 P를 출력할 것인지, 또는 왼쪽 자식 노드를 탐색한 뒤 P를 출력하고 오른쪽 자식 노드를 탐색할 것인지로 나눌 수 있다.
좀 더 쉽게 말하자면, P, P의 왼쪽 자식, P의 오른쪽 자식 이 중 무엇이 우선순위인가를 정하는 것과 유사하다고 볼 수 있다.
즉, 크게 다음과 같이 우선순위를 정할 수 있다.
오른쪽은 재귀적으로 이해하기 어렵다면 그냥 저렇게 3개의 노드가 있을 때를 생각하면 된다는 의미로 넣었다.
자 그러면 위와같이 3개의 순회 방식이 있다.
좀 더 쉽게 외우려면 '부모 노드'를 기준으로 우선순위가 몇 위인지를 판단하면 된다. (단 자식노드의 순서는 왼쪽 자식노드가 오른쪽 자식노드보다 우선권을 갖는다는 전제로 이루어진다.)
전위순회 (PreOrder) : 부모노드가 최우선순위를 갖는다. (부모 > 왼쪽 자식 > 오른쪽 자식)
중위순회 (InOrder) : 부모노드가 중간 우선순위를 갖는다. (왼쪽 자식 > 부모 > 오른쪽 자식)
후위순회 (PostOrder) : 부모노드가 가장 낮은 우선순위를 갖는다. (왼쪽 자식 > 오른쪽 자식 > 부모)
위와 같이 보면 된다.
그러면 다시 돌아와서..
위 트리를 각각 순회 방식에 따라 적용하면 어떻게 될까? ('재귀적으로 사고'하는 것이 핵심이다.)
답을 말하자면,
전위순회 (PreOrder) : 23 -> 12 -> 7 -> 1 -> 16 -> 14 -> 17 -> 40 -> 29 -> 55 -> 61
중위순회 (InOrder) : 1 -> 7 -> 12 -> 14 -> 16 -> 17 -> 23 -> 29 -> 40 -> 55 -> 61
후위순회 (PostOrder) : 1 -> 7 -> 14 -> 17 -> 16 -> 12 -> 29 -> 61 -> 55 -> 40 -> 23
감이 오시는가?
그렇다면 코드로 짜보도록 하자.
/**
* 전위 순회
* (부모 노드 > 왼쪽 자식 노드 > 오른쪽 자식 노드)
*/
public void preorder() {
preorder(this.root);
}
public void preorder(Node<E> o) {
// null이 아닐 떄 까지 재귀적으로 순회
if(o != null) {
System.out.print(o.value + " "); // 부모 노드
preorder(o.left); // 왼쪽 자식 노드
preorder(o.right); // 오른쪽 자식 노드
}
}
/**
* 중위 순회
* (왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드)
*/
public void inorder() {
inorder(this.root);
}
public void inorder(Node<E> o) {
if(o != null) {
inorder(o.left); // 왼쪽 자식 노드
System.out.print(o.value + " "); // 부모 노드
inorder(o.right); // 오른쪽 자식 노드
}
}
/**
* 후위 순회
* (왼쪽 자식 노드 > 오른쪽 자식 노드 > 부모 노드)
*/
public void postorder() {
postorder(this.root);
}
public void postorder(Node<E> o) {
if(o != null) {
postorder(o.left); // 왼쪽 자식 노드
postorder(o.right); // 오른쪽 자식 노드
System.out.print(o.value + " "); // 부모 노드
}
}
이 것이 끝이다.
필자가 계속 '재귀'를 강조하는 이유가, 위 처럼 재귀 탐색으로 한다면 결국 부모노드 출력부분의 위치만 바뀜에 따라 전위, 중위, 후위 순회를 간단하게 구현 할 수 있다는 것이다.
위 코드를 테스트 해보자.
public class Test {
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
// 예제에 있는 트리와 동일하게 구성
tree.add(23);
tree.add(12);
tree.add(40);
tree.add(7);
tree.add(16);
tree.add(1);
tree.add(14);
tree.add(17);
tree.add(29);
tree.add(55);
tree.add(61);
System.out.print("전위 순회 : ");
tree.preorder(); // 전위 순회
System.out.println();
System.out.print("중위 순회 : ");
tree.inorder(); // 중위 순회
System.out.println();
System.out.print("후위 순회 : ");
tree.postorder(); // 후위 순회
System.out.println();
}
}
[테스트 결과]
[순회 메소드 묶어보기]
/**
* 전위 순회
* (부모 노드 > 왼쪽 자식 노드 > 오른쪽 자식 노드)
*/
public void preorder() {
preorder(this.root);
}
public void preorder(Node<E> o) {
if(o != null) {
System.out.print(o.value + " ");
preorder(o.left);
preorder(o.right);
}
}
/**
* 중위 순회
* (왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드)
*/
public void inorder() {
inorder(this.root);
}
public void inorder(Node<E> o) {
if(o != null) {
inorder(o.left);
System.out.print(o.value + " ");
inorder(o.right);
}
}
/**
* 후위 순회
* (왼쪽 자식 노드 > 오른쪽 자식 노드 > 부모 노드)
*/
public void postorder() {
postorder(this.root);
}
public void postorder(Node<E> o) {
if(o != null) {
postorder(o.left);
postorder(o.right);
System.out.print(o.value + " ");
}
}
여담으로 중위순회를 보면 BinarySearchTree의 특성상 '오름차순'으로 순회를 한다는 것을 볼 수 있다. (당연하게도 왼쪽 자식노드는 부모노드보다 작고, 오른쪽 자식 노드는 부모노드보다 크기 때문)
그러면 여기서 하나를 더 응용 할 수 있다.
역순, 즉 '내림차순' 순회도 구현이 가능하지 않을까?
어떻게 하면 될까?
오른쪽 자식 노드 -> 부모노드 -> 왼쪽 자식노드 이 순서대로 하면 내림차순이 되지 않을까?
즉, 아래 코드가 중위 순회였다면,
public void inorder() {
inorder(this.root);
}
public void inorder(Node<E> o) {
if(o != null) {
inorder(o.left); // 왼쪽 자식 노드
System.out.print(o.value + " "); // 부모 노드
inorder(o.right); // 오른쪽 자식 노드
}
}
위 코드에서 자식노드 탐색 순서를 바꿔주면 되는 거 아닌가?
public void reverseInorder() {
reverseInorder(this.root);
}
public void reverseInorder(Node<E> o) {
if (o != null) {
reverseInorder(o.right); // 오른쪽 자식 노드
System.out.print(o.value + " "); // 부모 노드
reverseInorder(o.left); // 왼쪽 자식 노드
}
}
그리고 실제로 테스트를 해보자.
public class Test {
public static void main(String[] args) {
BinarySearchTree<Integer> tree = new BinarySearchTree<Integer>();
// 예제에 있는 트리와 동일하게 구성
tree.add(23);
tree.add(12);
tree.add(40);
tree.add(7);
tree.add(16);
tree.add(1);
tree.add(14);
tree.add(17);
tree.add(29);
tree.add(55);
tree.add(61);
System.out.print("중위 순회 : ");
tree.inorder(); // 중위 순회
System.out.println();
System.out.print("역중위 순회 : ");
tree.reverseInorder(); // 역중위 순회
System.out.println();
}
}
[결과]
이런식으로 결과가 잘 나오는 것을 볼 수 있다.
- 전체 코드
import java.util.Comparator;
public class BinarySearchTree<E> {
private Node<E> root;
private int size;
private final Comparator<? super E> comparator;
public BinarySearchTree() {
this(null);
}
public BinarySearchTree(Comparator<? super E> comparator) {
this.comparator = comparator;
this.root = null;
this.size = 0;
}
/**
* Binary Search Tree에 삽입하는 메소드
*
* @param value 삽입하고자 하는 데이터
* @return 정상적으로 삽입 되었을 경우 true, 중복 원소를 삽입할 경우 false를 반환
*/
public boolean add(E value) {
/*
* comparator(사용자 지정 비교기)가 없을 경우(=null)에는 Comparable,
* 있을 경우에는 Comparator를 사용하는 메소드로 보낸다.
* 그리고, 각 메소드는 정상적으로 삽입이 완료되었다면 null을 반환할 것이고,
* 중복 원소를 삽입 할 경우 해당 value를 반환할 것이기 때문에
* 비교 연산으로 null인지 아닌지 여부를 반환한다.
*/
if(comparator == null) {
return addUsingComparable(value) == null;
}
return addUsingComparator(value, comparator) == null;
}
// Comparable을 이용한 add메소드
private E addUsingComparable(E value) {
Node<E> current = root; // 탐색할 노드를 가리키는 current node
// 만약 current가 null, 즉 root가 null이면 root에 새 노드를 만들고 null반환
if(current == null) {
root = new Node<E>(value);
size++;
return null;
}
Node<E> currentParent; // current의 직전 탐색 노드를 가리키는 노드
// 삽입 할 노드가 비교 될 수 있도록 한 변수를 만든다.
@SuppressWarnings("unchecked")
Comparable<? super E> compValue = (Comparable<? super E>) value;
int compResult; // 비교 결과(양수, 0, 음수)를 담고 있을 변수
do {
// 다음 순회에서 current의 부모노드를 가리킬 수 있도록 현재 current를 저장
currentParent = current;
compResult = compValue.compareTo(current.value);
/*
* 비교 결과 value 보다 current.value 보다 작으면
* current를 current의 왼쪽 자식으로 갱신하고,
* value보다 current.value가 크다면 current를 오른쪽
* 자식으로 갱신하며, 같을 경우 순회를 중단하고 value를 반환한다.
*/
if(compResult < 0) {
current = current.left;
} else if(compResult > 0) {
current = current.right;
}
else {
return value;
}
} while(current != null);
// 순회가 완료되어 삽입해야 할 위치를 찾았다면 삽입 할 value를 노드로 만든다.
Node<E> newNode = new Node<E>(value, currentParent);
// 직전 비교 결과에 따라 currentParent의 오른쪽 혹은 왼쪽 노드에 새 노드를 연결해준다.
if(compResult < 0) {
currentParent.left = newNode;
}
else {
currentParent.right = newNode;
}
size++;
return null;
}
// Comparator을 이용한 add
private E addUsingComparator(E value, Comparator<? super E> comp) {
Node<E> current = root;
if(current == null) {
root = new Node<E>(value, null);
size++;
return null;
}
Node<E> currentParent;
int compResult;
do {
currentParent = current;
compResult = comp.compare(value, current.value);
if(compResult < 0) {
current = current.left;
}
else if(compResult > 0) {
current = current.right;
}
else {
return value;
}
} while(current != null);
Node<E> newNode = new Node<E>(value, currentParent);
if(compResult < 0) {
currentParent.left = newNode;
}
else {
currentParent.right = newNode;
}
size++;
return null;
}
/**
* 삭제 메소드
* @param o 삭제할 값
* @return 삭제 된 노드의 value 값 혹은 매칭 값이 없을 경우 null을 반환한다.
*/
public E remove(Object o) {
if (root == null) {
return null;
}
if (comparator == null) {
return removeUsingComparable(o);
} else {
return removeUsingComparator(o, comparator);
}
}
/**
* Comparable을 이용한 데이터 삭제
*
* @param value 삭제하고자 하는 데이터
* @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
*/
private E removeUsingComparable(Object value) {
@SuppressWarnings("unchecked")
E oldVal = (E) value;
Node<E> parent = null, current = root;
// 삭제하고자 하는 노드가 부모 노드로부터 왼쪽 자식 노드인지 오른쪽 자식 노드인지 알기 위한 변수
boolean hasLeft = false;
if (root == null) {
return null;
}
@SuppressWarnings("unchecked")
Comparable<? super E> compValue = (Comparable<? super E>) value;
// 삭제할 노드를 찾는다.
do {
int resComp = compValue.compareTo(current.value);
if (resComp == 0) {
break;
}
parent = current;
if (resComp < 0) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
} while (current != null);
// 만약 탐색 끝에 삭제해야할 노드를 찾지 못했다면 null 반환
if (current == null) {
return null;
}
// 부모 노드가 없을 경우 == 삭제하는 노드가 root일 경우
if (parent == null) {
deleteNode(current);
size--;
return oldVal;
}
// 삭제 노드가 부모노드의 왼쪽 자식일 경우
if (hasLeft) {
parent.left = deleteNode(current);
// 만약 새로 이어질 노드가 존재한다면, 해당 대체 노드의 부모노드도 갱신
if (parent.left != null) {
parent.left.parent = parent;
}
}
// 삭제 노드가 부모노드의 오른쪽 자식일 경우
else {
parent.right = deleteNode(current);
// 만약 새로 이어질 노드가 존재한다면, 해당 대체 노드의 부모노드도 갱신
if (parent.right != null) {
parent.right.parent = parent;
}
}
size--;
return oldVal;
}
/**
* Comparator을 이용한 데이터 삭제
*
* @param value 삭제하고자 하는 데이터
* @param comparator 사용자에 의해 BinarySearchTree에 지정 된 비교기
* @return 정상적으로 삭제되었을 경우 value를 반환하나, 삭제할 노드가 없을경우 null을 반환한다.
*/
private E removeUsingComparator(Object value, Comparator<? super E> comp) {
@SuppressWarnings("unchecked")
E oldVal = (E) value;
Node<E> parent = null, current = root;
boolean hasLeft = false;
if (root == null) {
return null;
}
@SuppressWarnings("unchecked")
E compValue = (E) value;
// 삭제할 노드를 찾는다.
do {
int resComp = comp.compare(compValue, current.value);
if (resComp == 0) {
break;
}
parent = current;
if (resComp < 0) {
hasLeft = true;
current = current.left;
} else {
hasLeft = false;
current = current.right;
}
} while (current != null);
if (current == null) {
return null;
}
if (parent == null) {
deleteNode(current);
size--;
return oldVal;
}
if (hasLeft) {
parent.left = deleteNode(current);
if (parent.left != null) {
parent.left.parent = parent;
}
} else {
parent.right = deleteNode(current);
if (parent.right != null) {
parent.right.parent = parent;
}
}
size--;
return oldVal;
}
/**
* 삭제 할 노드에 대해 삭제를 수행하는 메소드
*
* @param node 삭제 할 노드
* @return 삭제 후 대체 되고 난 뒤의 해당 위치의 노드를 반환
*/
private Node<E> deleteNode(Node<E> node) {
if (node != null) {
// 자식노드가 없을 경우
if (node.left == null && node.right == null) {
// 삭제하려는 노드가 root일 경우 root를 끊어버리고 종료한다.
if (node == root) {
root = null;
}
// 그 외에는 단말 노드이므로 해당 노드만 삭제한다.
// 자연스럽게 node의 부모노드는 null을 참조하게 됨
else {
node = null;
}
return null;
}
// 양쪽의 자식노드가 모두 있을 경우
if (node.left != null && node.right != null) {
// 대체 노드를 찾아온다.
Node<E> replacement = getSuccessorAndUnlink(node);
// 삭제 된 노드에 대체 노드의 값을 대체해준다.
node.value = replacement.value;
}
// 왼쪽 노드만 존재할 경우
else if (node.left != null) {
/*
* 삭제할 노드가 root일 경우 왼쪽자식 노드(대체되는 노드)를
* 삭제할 노드로 옮긴 다음 root를 대체노드를 가리키도록 변경한다
*/
if (node == root) {
node = node.left;
root = node;
root.parent = null;
} else {
node = node.left;
}
}
// 오른쪽 노드만 존재할 경우
else {
/*
* 삭제할 노드가 root일 경우 오른쪽자식 노드(대체되는 노드)를
* 삭제할 노드로 옮긴 다음 root를 대체노드를 가리키도록 변경한다
*/
if (node == root) {
node = node.right;
root = node;
root.parent = null;
} else {
node = node.right;
}
}
}
return node;
}
/**
* 삭제되는 노드의 자리를 대체할 노드(후계자)를 찾는 메소드
* (오른쪽 자식 노드 중 가장 작은 노드를 찾음)
*
* @param node 삭제되는 노드(=대체되어야 할 노드)
* @return 대체할 노드
*/
private Node<E> getSuccessorAndUnlink(Node<E> node) {
Node<E> currentParent = node; // 대체 할 노드의 부모노드를 가리키는 노드
Node<E> current = node.right; // 초기에 오른쪽 자식 노드를 가리키도록 한다.
/**
* 처음 탐색하게되는 오른쪽 자식 노드(current)에서
* current의 왼쪽 자식이 없다는 것은 current노드,
* 즉 오른쪽 첫 자식노드가 대체되는 노드가 된다는 것이다.
*
* 그렇기 때문에 대체해야하는 노드는 삭제되는 노드의 오른쪽 자식이 되며
* 이에 대체되는 노드 자리(currentParent)의 오른쪽 자식은
* current의 오른쪽 자식을 가리키고, currentParent는 이후
* current의 값이 반환되고, 상위 메소드에서 currentParent자리에
* 값이 대체되게 된다.
*/
if (current.left == null) {
currentParent.right = current.right;
if (currentParent.right != null) {
currentParent.right.parent = currentParent;
}
current.right = null;
return current;
}
// 가장 작은 노드를 찾을 때 까지 반복한다.
while (current.left != null) {
currentParent = current;
current = current.left;
}
/*
* 만약 후계자가 될 노드(가장 작은 노드)의 오른쪽 노드가 존재한다면
* currentParent의 왼쪽 자식노드는 오른쪽 자식노드와 연결되어야 한다.
*
* 만약 current.right = null 이라면
* 후계자가 될 노드의 자식노드는 존재하지 않으므로 자연스럽게
* 후계자 노드의 부모노드는 후계자가 다른노드로 대체되러 가기 때문에
* 후계자의 부모노드의 왼쪽자식노드는 자연스럽게 null을 가리키게 된다.
*/
currentParent.left = current.right;
if (currentParent.left != null) {
currentParent.left.parent = currentParent;
}
current.right = null;
return current;
}
/**
* BinarySearchTree에 있는 원소의 개수를 반환해주는 메소드
*
* @return BinarySearchTree에 있는 원소의 개수를 반환
*/
public int size() {
return this.size;
}
/**
* BinarySearchTree가 비어있는지를 판단하는 메소드
*
* @return BinarySearchTree가 비어있을 경우 true, 아닐경우 false를 반환
*/
public boolean isEmpty() {
return size() == 0;
}
/**
* 해당 객체가 BinarySearchTree에 존재하는지를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
public boolean contains(Object o) {
// comparator가 null 일경우 Comparable로 비교하도록 한다.
if (comparator == null) {
return containsUsingComparable(o);
}
return containsUsingComparator(o, comparator);
}
/**
* Comparable을 이용한 객체 존재 여부를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
private boolean containsUsingComparable(Object o) {
// 비교 가능한 변수로 만든다
@SuppressWarnings("unchecked")
Comparable<? super E> value = (Comparable<? super E>) o;
Node<E> node = root;
while (node != null) {
int res = value.compareTo(node.value);
if (res < 0) {
node = node.left;
} else if (res > 0) {
node = node.right;
}
// res == 0 이라는 것은 같다는 의미로 true를 반환
else {
return true;
}
}
return false;
}
/**
* Comparable을 이용한 객체 존재 여부를 판단하는 메소드
*
* @param o 찾고자 하는 객체
* @param comparator 사용자에 의해 BinarySearchTree에 지정 된 비교기
* @return 해당 객체가 존재 할 경우 true, 아닐 경우 false를 반환
*/
private boolean containsUsingComparator(Object o, Comparator<? super E> comparator) {
@SuppressWarnings("unchecked")
E value = (E) o;
Node<E> node = root;
while (node != null) {
int res = comparator.compare(value, node.value);
if (res < 0) {
node = node.left;
} else if (res > 0) {
node = node.right;
} else {
return true;
}
}
return false;
}
/**
* BinarySearchTree를 초기화 하는 메소드
*/
public void clear() {
size = 0;
/*
* root를 끊어주면 하위 모든 노드들도 더이상
* 참조할 수 없기 때문에 GC 처리 된다.
*/
root = null;
}
/**
* 전위 순회
* (부모 노드 > 왼쪽 자식 노드 > 오른쪽 자식 노드)
*/
public void preorder() {
preorder(this.root);
}
public void preorder(Node<E> o) {
// null이 아닐 떄 까지 재귀적으로 순회
if(o != null) {
System.out.print(o.value + " "); // 부모 노드
preorder(o.left); // 왼쪽 자식 노드
preorder(o.right); // 오른쪽 자식 노드
}
}
/**
* 중위 순회
* (왼쪽 자식 노드 > 부모 노드 > 오른쪽 자식 노드)
*/
public void inorder() {
inorder(this.root);
}
public void inorder(Node<E> o) {
if(o != null) {
inorder(o.left); // 왼쪽 자식 노드
System.out.print(o.value + " "); // 부모 노드
inorder(o.right); // 오른쪽 자식 노드
}
}
/**
* 후위 순회
* (왼쪽 자식 노드 > 오른쪽 자식 노드 > 부모 노드)
*/
public void postorder() {
postorder(this.root);
}
public void postorder(Node<E> o) {
if(o != null) {
postorder(o.left); // 왼쪽 자식 노드
postorder(o.right); // 오른쪽 자식 노드
System.out.print(o.value + " "); // 부모 노드
}
}
}
위 코드는 아래 깃허브에서도 소스 코드를 편리하게 보실 수 있다. 또한 깃허브에 올라가는 코드들은 조금 더 기능을 추가하거나 수정되어 올라가기에 약간의 차이는 있을 수 있지만 전체적인 구조는 바뀌지 않으니 궁금하시거나 참고하실 분들은 아래 링크로 가서 보시는 걸 추천한다.
[소스코드 모아보기]
kdgyun/Data_Structure
Contribute to kdgyun/Data_Structure development by creating an account on GitHub.
github.com
- 정리
오늘은 조금 어려운 내용이었을 것이다. 아무래도 트리의 가장 기초라곤 하나, 구현 방식을 기초적인 방식이 아닌 실제 이후 구현 할 TreeSet 자료구조에 발맞추어 구현해나가는 것이라 반복문을 활용한 내용들이 주를 이루기 때문에..
하지만 필자가 자신하는 것은 위 내용을 완벽히 이해하고 구조를 파악할 수 있다면 이후 구현 할 좀 더 복잡한 자료구조들에 대해서도 분명 쉽게 구현하실 수 있게 될 것이다.
가끔 댓글로 자료구조가 중요하냐라고 묻는데, 음.. 요즘은 사실 자료구조 그 자체만 보면 확실히 점점 필수와는 거리가 멀어지고 있다고는 보인다. 하지만 그럼에도 중요한 점이라면 이러한 구현을 통해 논리적 구조를 파악하고 구현하며 다양한 에러들을 접해보면서 성장할 수 있는 중요한 촉매제 같은 역할을 해준다는 건 변함이 없는 것 같다.
그렇기 때문에 최대한 이해하기 쉽게 쓰려고 노력은 한다만 해당 자료구조 자체 난이도가 높아서 조금은 걱정이긴 하다. 혹여 이해가 안되는 부분, 또는 질문이 있다면 언제든 댓글을 남겨주시면 된다. 최대한 빠르게 답변드리겠다.
'자료구조 > Java' 카테고리의 다른 글
| 자바 [JAVA] - Linked Hash Set (연결 해시 셋) 구현하기 (2) | 2021.07.02 |
|---|---|
| 자바 [JAVA] - Hash Set (해시 셋) 구현하기 (14) | 2021.04.14 |
| 자바 [JAVA] - Set Interface (셋 인터페이스) (0) | 2021.04.09 |
| 자바 [JAVA] - Priority Queue (우선순위 큐) 구현하기 (24) | 2021.03.04 |
| 자바 [JAVA] - 배열을 이용한 Heap (힙) 구현하기 (52) | 2021.02.10 |