이 md 파일은 Typora 에서 작성되었습니다. 읽으실 때, Typora 에서 읽으시는 것이 가장 보기에 좋습니다.
[TOC]
탐색은 '데이터를 찾는 방법'을 의미합니다. 탐색은 탐색 알고리즘만을 얘기하는게 아니라고 소개하는 점이 신기했습니다.
순차 탐색과 이진 탐색 알고리즘에 이어 보간 탐색이라는 용어가 등장합니다.
저도 이 책에서 처음 접한 용어입니다.
보간 탐색은 이진 탐색의 비효율성을 개선시킨 알고리즘이라고 합니다.
보간 탐색은 탐색할 데이터가 앞쪽에 위치할 것으로 예상되면 앞쪽부터 찾는 알고리즘으로, 단번에 찾아내는 경우도 존재한다고 합니다.
보간 탐색의 단점은 나눗셈연산, 정확도를 높이기 위해 실수형 나눗셈을 진행한다는 것이 단점입니다.
보통 우리는 어떤 데이터가 있음을 알고 그 데이터를 탐색하는 것이 아니라, 있는지 없는지 모르겠지만 찾고 싶을 때 탐색합니다.
보통 우리가 찾는 방식은 데이터의 탐색 키를 통해 데이터를 찾아내는 것입니다.
그리고 탐색 키는 항상 그 값이 고유해야합니다.
이진 탐색 다시보기
BinarySearch.java
public class BinarySearch {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int idx = bSearch(arr, 7);
printSearchInfo(idx);
idx = bSearch(arr, 4);
printSearchInfo(idx);
}
public static int bSearch(int[] arr, int target) {
int first = 0; // 탐색 대상의 시작 인덱스 값
int last = arr.length - 1; // 탐색 대상의 마지막 인덱스 값
int mid;
while (first <= last) {
mid = (first + last) / 2; // 탐색 대상의 중앙을 찾는다.
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) { // 탐색 대상이 아니라면 반으로 줄입니다.
last = mid - 1; // 왜 mid에서 1을 뺄까요?
} else {
first = mid + 1; // 왜 mid에서 1을 더할까요?
}
}
return -1;
}
public static void printSearchInfo(int idx) {
String info = "탐색 실패";
if (idx != -1) {
info = "타겟 저장 인덱스: " + idx;
}
System.out.println(info);
}
}사실 책에선 재귀 구조를 들고 왔는데, 큰 차이는 없습니다.
이진 탐색과 보간 탐색의 차이는 탐색 대상을 선택하는 방법에 있고, 이를 개선하면 다음과 같다고 합니다.
mid = (int) ((double) (target - arr[first]) / (arr[last] - arr[first]) * (last - first)) + first;
java에서는 double형이 자동으로 int 형으로 캐스팅 되지 않으므로 강제로 캐스팅 해줘야 합니다.
그리고 이 식은 mid라고 볼 수 없지만, 그대로 유지한다고 합니다.
InterpolSearch.java
public class InterpolSearch {
public static void main(String[] args) {
int[] arr = {1, 3, 5, 7, 9};
int idx = iSearch(arr, 7);
printSearchInfo(idx);
idx = iSearch(arr, 4);
printSearchInfo(idx);
}
public static int iSearch(int[] arr, int target) {
int first = 0; // 탐색 대상의 시작 인덱스 값
int last = arr.length - 1; // 탐색 대상의 마지막 인덱스 값
int mid;
while (first <= last) {
mid = (int) ((double) (target - arr[first]) / (arr[last] - arr[first]) * (last - first))
+ first;
if (arr[mid] == target) {
return mid;
} else if (target < arr[mid]) { // 탐색 대상이 아니라면 반으로 줄입니다.
last = mid - 1; // 왜 mid에서 1을 뺄까요?
} else {
first = mid + 1; // 왜 mid에서 1을 더할까요?
}
}
return -1;
}
public static void printSearchInfo(int idx) {
String info = "탐색 실패";
if (idx != -1) {
info = "타겟 저장 인덱스: " + idx;
}
System.out.println(info);
}
}하지만 아직 고쳐야 할 부분이 남아있다고 합니다.
하지만 우리는 재귀구조가 아니라 그런지 잘 통과합니다.
while (!(arr[first] > target || arr[last] < target)) {이렇게 바꾸면 동작하겠죠?
탐색 대상이 해당 범위내에 존재하지 않을 경우 탐색 대상의 값이 탐색 범위를 벗어난다.를 탈출 조건의 근거로 삼아야 하기 때문입니다. 반대로 while 루프에서는 범위 내에 존재해야겠죠?
탐색에 효율적인 자료구조를 배운다고 합니다.
이진 트리는 탐색에 있어 효율적인 구조입니다. 사실 모든 트리가 그렇습니다. B-Tree의 경우도 그렇고, 탐색용으로 많이 쓰이게 됩니다.
문제는 이것이 정확히 어떤 경로를 타고 들어가야 그 데이터를 찾을 수 있는지 일반 이진트리에서는 알기 어렵습니다.
따라서 이진 탐색 트리는 데이터를 저장하는 규칙이 있습니다. 이 규칙만 있다면 어떤 경로를 타고 가야하는지 명백해집니다.
- 이진 탐색 트리의 노드에 저장된 키(key)는 유일하다.
- 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 크다.
- 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작다.
- 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.
간단히 말해서 작으면 왼쪽으로, 크면 오른쪽으로 데이터를 배치한다.
탐색을 할 때에도 같은 과정을 반복하면 된다.
책이 참 일관성이라고는 하나도 없네요....
ADT 정의 및 테스트 코드 작성부터 들어가보겠습니다.
BinarySearchTreeNode.java
public interface BinarySearchTreeNode<K, V> {
V getNodeData(BinarySearchTreeNode<K, V> bstNode);
BinarySearchTreeNode<K, V> search(K key);
void insert(K key, V value);
}위와 같이 하는 것이 정석적이지만, 훨씬 어려울 것 같아서 아래와 같이 구현하려고 합니다.(사실 별로 안어려울 것 같기도...)
/**
* 이진 탐색 트리 자료구조의 ADT, 인터페이스이자 Node의 인터페이스
*
* @param <E> 데이터의 파라미터 타입
* @author dion
*/
public interface BinarySearchTreeNode<E> {
/**
* 해당 데이터를 가지고 있는 노드를 찾습니다.
*
* @param target 찾으려고 하는 데이터
* @return 해당 데이터를 가지고 있는 노드
*/
BinaryTreeNode<E> search(E target);
/**
* 해당 데이터를 BST에 추가합니다.
*
* @param data BST에 저장할 데이터
*/
void insert(E data);
}BinarySearchTreeNodeTest.java
class BinarySearchTreeNodeTest {
@Test
@DisplayName("이진_탐색_트리_테스트")
void 이진_탐색_트리_테스트() {
BinarySearchTreeNode<Integer> bstRoot = new LinkedBinarySearchTreeNode<>(5, (Comparator
.comparingInt(o -> o)));
BinaryTreeNode<Integer> searchNode;
bstRoot.insert(1);
bstRoot.insert(6);
bstRoot.insert(2);
bstRoot.insert(8);
bstRoot.insert(3);
bstRoot.insert(9);
searchNode = bstRoot.search(1);
assertThat(searchNode).isNotNull();
assertThat(searchNode.getData()).isEqualTo(1);
searchNode = bstRoot.search(4);
assertThat(searchNode).isNull();
searchNode = bstRoot.search(6);
assertThat(searchNode).isNotNull();
assertThat(searchNode.getData()).isEqualTo(6);
searchNode = bstRoot.search(7);
assertThat(searchNode).isNull();
}
}비교를 위해 comparator를 사용했습니다.
LinkedBinarySearchTreeNode.java
public class LinkedBinarySearchTreeNode<E> implements BinarySearchTreeNode<E> {
private final Comparator<E> comparator;
private BinaryTreeNode<E> node;
public LinkedBinarySearchTreeNode(E data, Comparator<E> comparator) {
this.node = new LinkedBinaryTreeNode<>(data);
this.comparator = comparator;
}
@Override
public BinarySearchTreeNode<E> search(E target) {
return null;
}
@Override
public void insert(E data) {
}
}코드 자체는 읽으면 쉽게 이해할 수 있다고 생각됩니다.
@Override
public void insert(E data) {
if (data == null) {
return;
}
BinaryTreeNode<E> curNode = this.node;
BinaryTreeNode<E> parentNode = null;
while (curNode != null) { // 저장할 위치를 찾는다.
E curNodeData = curNode.getData();
if (data == curNodeData) { // 중복저장 허용 안함
return;
}
parentNode = curNode;
if (comparator.compare(curNodeData, data) > 0) {
curNode = curNode.getLeftSubTree();
} else {
curNode = curNode.getRightSubTree();
}
}
BinaryTreeNode<E> newNode = new LinkedBinaryTreeNode<>(data);
if (comparator.compare(parentNode.getData(), data) > 0) { // 크기를 비교해서 원하는 위치에 저장한다.
parentNode.setLeftSubTree(newNode);
} else {
parentNode.setRightSubTree(newNode);
}
}좀 맘에 안들었던 부분이, 비교하는 부분이었습니다.
data의 위치에 따라 부등호 방향이 반대가 되어버려서 비슷한데, 달라보이는 코드였네요.
@Override
public BinaryTreeNode<E> search(E target) {
BinaryTreeNode<E> curNode = this.node;
while (curNode != null) {
E curNodeData = curNode.getData();
if (curNodeData.equals(target)) {
return curNode;
} else if (comparator.compare(curNodeData, target) > 0) {
curNode = curNode.getLeftSubTree();
} else {
curNode = curNode.getRightSubTree();
}
}
return null;
}검색은 간단합니다.
비교해서 같은 것이 나올 때까지 확인해보고, 없으면 null을 반환합니다.
이진 탐색 트리의 삭제는 단순하지 않다고 합니다. 왜냐하면 삭제 후에도 이진트리의 구조가 유지되어야하기 때문입니다.
삭제의 경우는 총 세 가지로 구분됩니다.
- 삭제할 노드가 단말 노드인 경우(GOOD!)
- 삭제할 노드가 하나의 자식 노드를 갖는 경우(SOSO!)
- 삭제할 노드가 두 개의 자식 노드를 갖는 경우(😅)
또, 루트 노드인 경우도 생각해야 합니다.
그림만 보고 넘어갑시다. 설명을 보면 오히려 더 헷갈릴 수도 있을겁니다.
사실 이진트리는 미완성된 이진트리였습니다~
라고 하는데, 솔직히 말해서 맘에 안드는 부분이었네요.
여튼 이진 트리의 인터페이스 및 이진 트리 구현체를 변경해봅시다.
BinaryTreeNode.java
/**
* 왼쪽 서브트리를 제거하고 반환합니다.
*
* @return 왼쪽 서브트리
*/
BinaryTreeNode<E> removeLeftSubTree();
/**
* 오른쪽 서브트리를 제거하고 반환합니다.
*
* @return 오른쪽 서브트리
*/
BinaryTreeNode<E> removeRightSubTree();
/**
* 왼쪽 서브트리를 입력된 서브트리로 대체합니다.
*
* @param subTree 왼쪽 서브트리를 대체할 서브트리
*/
void changeLeftSubTree(BinaryTreeNode<E> subTree);
/**
* 오른쪽 서브트리를 입력된 서브트리로 대체합니다.
*
* @param subTree 오른쪽 서브트리를 대체할 서브트리
*/
void changeRightSubTree(BinaryTreeNode<E> subTree);BinaryTreeNodeTest.java
class BinaryTreeNodeTest {
private BinaryTreeNode<Integer> bt1;
private BinaryTreeNode<Integer> bt2;
private BinaryTreeNode<Integer> bt3;
private BinaryTreeNode<Integer> bt4;
private BinaryTreeNode<Integer> bt5;
@BeforeEach
void setUp() {
bt1 = new LinkedBinaryTreeNode<>(1);
bt2 = new LinkedBinaryTreeNode<>(2);
bt3 = new LinkedBinaryTreeNode<>(3);
bt4 = new LinkedBinaryTreeNode<>(4);
bt5 = new LinkedBinaryTreeNode<>(5);
bt1.setLeftSubTree(bt2);
bt1.setRightSubTree(bt3);
bt2.setLeftSubTree(bt4);
}
@Test
@DisplayName("이진_트리_생성_및_초기화_테스트")
void 이진_트리_생성_및_초기화_테스트() {
assertThat(bt5).isNotNull();
assertThat(bt5.getData()).isEqualTo(5);
assertThat(bt5.getLeftSubTree()).isNull();
assertThat(bt5.getRightSubTree()).isNull();
}
@Test
@DisplayName("이진_트리_저장_및_출력_테스트")
void 이진_트리_저장_및_출력_테스트() {
assertThat(bt1).isNotNull();
assertThat(bt2).isNotNull();
assertThat(bt3).isNotNull();
assertThat(bt4).isNotNull();
assertThat(bt1.getData()).isEqualTo(1);
assertThat(bt2.getData()).isEqualTo(2);
assertThat(bt3.getData()).isEqualTo(3);
assertThat(bt4.getData()).isEqualTo(4);
assertThat(bt1.getLeftSubTree().getData()).isEqualTo(2);
assertThat(bt1.getRightSubTree().getData()).isEqualTo(3);
assertThat(bt1.getLeftSubTree().getLeftSubTree().getData()).isEqualTo(4);
assertThat(bt1.getLeftSubTree().getRightSubTree()).isNull();
}
@Test
@DisplayName("이진_트리_제거_테스트")
void 이진_트리_제거_테스트() {
assertThat(bt1.removeLeftSubTree()).isSameAs(bt2);
assertThat(bt1.removeRightSubTree()).isSameAs(bt3);
assertThat(bt1.getLeftSubTree()).isNull();
assertThat(bt1.getRightSubTree()).isNull();
}
@Test
@DisplayName("이진_트리_대체_테스트")
void 이진_트리_대체_테스트() {
assertThat(bt1.getLeftSubTree()).isSameAs(bt2);
assertThat(bt1.getRightSubTree()).isSameAs(bt3);
bt1.changeLeftSubTree(bt3);
assertThat(bt1.getLeftSubTree()).isSameAs(bt3);
bt1.changeRightSubTree(bt2);
assertThat(bt1.getRightSubTree()).isSameAs(bt2);
}
}LinkedBinaryTreeNode
@Override
public BinaryTreeNode<E> removeLeftSubTree() {
BinaryTreeNode<E> deleteNode = this.getLeftSubTree();
this.left = null;
return deleteNode;
}
@Override
public BinaryTreeNode<E> removeRightSubTree() {
BinaryTreeNode<E> deleteNode = this.getRightSubTree();
this.right = null;
return deleteNode;
}
@Override
public void changeLeftSubTree(BinaryTreeNode<E> subTree) {
this.left = subTree;
}
@Override
public void changeRightSubTree(BinaryTreeNode<E> subTree) {
this.right = subTree;
}열심히 Context Switching을 해오셨으니 수고하셨다는 말씀을 드립니다. ㅎㅎ
BinarySearchTreeNode.java
/**
* 해당 데이터를 BST에서 제거하고 해당 데이터를 저장한 노드를 반환합니다.
*
* @param target 제거할 데이터
* @return 제거된 데이터를 저장한 노드
*/
BinaryTreeNode<E> remove(E target);BinarySearchTreeNodeTest.java
@Test
@DisplayName("이진_탐색_트리_제거_테스트")
void 이진_탐색_트리_제거_테스트() {
int RootNodeData = 5;
int terminalNodeData = 2;
int singleSubTreeNodeData = 6;
int doubleSubTreeNodeData = 8;
BinarySearchTreeNode<Integer> bstRoot = new LinkedBinarySearchTreeNode<>(RootNodeData,
(Comparator.comparingInt(o -> o)));
bstRoot.insert(doubleSubTreeNodeData);
bstRoot.insert(1);
bstRoot.insert(singleSubTreeNodeData);
bstRoot.insert(4);
bstRoot.insert(9);
bstRoot.insert(3);
bstRoot.insert(terminalNodeData);
bstRoot.insert(7);
assertThat(bstRoot.search(terminalNodeData).getData())
.isEqualTo(bstRoot.remove(terminalNodeData).getData());
assertThat(bstRoot.search(singleSubTreeNodeData).getData())
.isEqualTo(bstRoot.remove(singleSubTreeNodeData).getData());
assertThat(bstRoot.search(doubleSubTreeNodeData).getData())
.isEqualTo(bstRoot.remove(doubleSubTreeNodeData).getData());
assertThat(bstRoot.search(RootNodeData).getData())
.isEqualTo(bstRoot.remove(RootNodeData).getData());
}
@Test
@DisplayName("이진_탐색_트리_제거_테스트2")
void 이진_탐색_트리_제거_테스트2() {
BinarySearchTreeNode<Integer> bstRoot = new LinkedBinarySearchTreeNode<>(5,
(Comparator.comparingInt(o -> o)));
bstRoot.insert(8);
bstRoot.insert(1);
bstRoot.insert(6);
bstRoot.insert(3);
bstRoot.insert(2);
bstRoot.insert(4);
bstRoot.insert(9);
bstRoot.insert(7);
assertThat(bstRoot.search(1).getData())
.isEqualTo(bstRoot.remove(1).getData());
assertThat(bstRoot.search(3).getData())
.isEqualTo(bstRoot.remove(3).getData());
assertThat(bstRoot.search(5).getData())
.isEqualTo(bstRoot.remove(5).getData());
assertThat(bstRoot.search(4).getData())
.isEqualTo(bstRoot.remove(4).getData());
assertThat(bstRoot.search(7).getData())
.isEqualTo(bstRoot.remove(7).getData());
assertThat(bstRoot.search(9).getData())
.isEqualTo(bstRoot.remove(9).getData());
assertThat(bstRoot.search(8).getData())
.isEqualTo(bstRoot.remove(8).getData());
}테스트 코드가 좀 더럽습니다... 많이 헷갈리더라고요.
LinkedBinarySearchTreeNode.java
@Override
public BinaryTreeNode<E> remove(E target) {
BinaryTreeNode<E> rootDummyNode = new LinkedBinaryTreeNode<>(null);
BinaryTreeNode<E> parentNode = rootDummyNode;
BinaryTreeNode<E> currentNode = this.node;
BinaryTreeNode<E> deleteNode;
rootDummyNode.changeRightSubTree(this.node);
while (currentNode != null && currentNode.getData() != target) {
parentNode = currentNode;
if (comparator.compare(target, currentNode.getData()) < 0) {
currentNode = currentNode.getLeftSubTree();
} else {
currentNode = currentNode.getRightSubTree();
}
}
if (currentNode == null) { // 삭제 대상이 조회되지 않은 경우
return null;
}
deleteNode = currentNode;
if (deleteNode.getLeftSubTree() == null && deleteNode.getRightSubTree() == null) {
// 삭제 대상이 단말 노드인 경우
if (parentNode.getLeftSubTree() == deleteNode) {
parentNode.removeLeftSubTree();
} else {
parentNode.removeRightSubTree();
}
} else if (deleteNode.getLeftSubTree() == null || deleteNode.getRightSubTree() == null) {
// 삭제 대상이 하나의 자식 노드를 갖는 경우
BinaryTreeNode<E> childNode;
if (deleteNode.getLeftSubTree() != null) {
childNode = deleteNode.getLeftSubTree();
} else {
childNode = deleteNode.getRightSubTree();
}
if (parentNode.getLeftSubTree() == deleteNode) {
parentNode.changeLeftSubTree(childNode);
} else {
parentNode.changeRightSubTree(childNode);
}
} else {
// 둘 다 있는 경우
BinaryTreeNode<E> moveNode = deleteNode.getRightSubTree();
BinaryTreeNode<E> moveParentNode = deleteNode;
// 삭제 대상의 대체 노드 찾기
while (moveNode.getLeftSubTree() != null) {
moveParentNode = moveNode;
moveNode = moveNode.getLeftSubTree();
}
// 대체 노드의 부모 노드와 자식 노드 연결
if (moveParentNode.getLeftSubTree() == moveNode) {
moveParentNode.changeLeftSubTree(moveNode.getRightSubTree());
} else {
moveParentNode.changeRightSubTree(moveNode.getRightSubTree());
}
// 삭제 노드의 하위 노드를 대체 노드에 연결
moveNode.changeLeftSubTree(deleteNode.getLeftSubTree());
moveNode.changeRightSubTree(deleteNode.getRightSubTree());
// 부모 노드의 하위 노드 변경
if (parentNode.getLeftSubTree() != deleteNode) {
parentNode.changeRightSubTree(moveNode);
} else {
parentNode.changeLeftSubTree(moveNode);
}
}
if (rootDummyNode.getRightSubTree() != this.node) {
this.node = rootDummyNode.getRightSubTree();
}
return deleteNode;
}정말 더럽게 긴 메소드입니다.
아마 리팩토링하면 개별 조건을 분리해서 짜지 않을까 싶네요.
이진 트리의 중위 순회를 통해서 정렬된 데이터를 출력할 수 있습니다.
요거는 직접 해보셔도 될 것 같아, 추가하지 않습니다. (저는 해봤습니다.)
중간에 값을 바꾸는 로직이 있었는데 제가 set을 구현하지 않아서, 그냥 노드끼리 바꾸는 것으로 했으니 착오 없으시길 바랍니다.
이진 탐색 트리는 단점이 있습니다. 무엇일까요?
이상적인 경우 이진 탐색 트리는
하지만 이상은 어디까지나 이상입니다. 균형이 맞지 않을 경우 점점
즉 저장되는 순서에 따라 영향을 받을 수 있는 구조라는 것입니다.
이런 문제를 해결한 트리를 '자가 균형 이진 탐색 트리'라고 하고 책에선 '균형 잡힌 이진 트리'라고 하네요.
AVL 트리는 교육용으로 많이 쓰이고
Red-Black 트리는 실제로 많이 쓰인다고 합니다.
B트리는 우리가 아는 그 B 트리입니다. DB와 파일 시스템에서 많이 쓰이죠.
AVL트리는 트리에 노드가 추가되거나 삭제될 때, 트리의 균형 상태를 파악해서 스스로 그 구조를 변경하여 균형을 잡는 트리입니다.
AVL트리에서는 균형의 정도를 표현하기 위해 '균형 인수(Balanced Factor)'라는 것을 사용합니다.
AVL트리의 균형을 잡기 위한 트리 구조의 재조정을 리밸런싱이라고 한다고 합니다.
AVL트리는 균형 인수의 절댓값이 2이상인 경우 리밸런싱을 진행합니다.
AVL 트리의 균형이 무너지는 상태는 4가지 입니다.
균형인수가 +2인 경우, 자식 노드가 왼쪽으로 연이어 연결되었습니다. 이 상태를 'Left Left 상태'라 하고 이를 줄여 'LL 상태' 라고합니다.
그리고 이러한 불균형을 해소하기 위한 리밸런싱 방법이 'LL 회전'입니다.
이 방법은 균형인수가 +2인 노드를 자식노드의 오른쪽 노드가 되게 하는데 있습니다.
또, 자식노드의 오른쪽 자식 노드도 신경을 써야합니다. 이 오른쪽 자식 노드는 균형인수가 +2인 노드의 왼쪽 자식노드가 되게됩니다.
LL 상태와 RR 상태는 방향의 차이입니다.
위 두 경우 모두 연산 순서에 신경써야 합니다.
LR상태는 RR회전을 통해서 LL상태가 되게할 수 있습니다.
RR회전은 부모와 자식의 위치를 바꾸고 부모가된 노드의 왼쪽에 자식이 위치하게 됩니다.
위와 반대로 LL 회전을 하고 RR 상태가 되게 할 수 있습니다.
AVL 트리도 결국 이진 탐색 트리입니다. 따라서 인터페이스는 이진탐색 트리를 사용하고, 구현체만 바꿔주면 됩니다.
BinarySearchTreeNodeTest.java
@Test
@DisplayName("AVL_트리_테스트")
void AVL_트리_테스트() {
BinarySearchTreeNode<Integer> bstRoot = new AVLTreeNode<>(1, (Comparator.comparingInt(o -> o)));
BinaryTreeNode<Integer> searchNode;
bstRoot.insert(5);
bstRoot.insert(6);
bstRoot.insert(2);
bstRoot.insert(8);
bstRoot.insert(3);
bstRoot.insert(9);
searchNode = bstRoot.search(1);
assertThat(searchNode).isNotNull();
assertThat(searchNode.getData()).isEqualTo(1);
searchNode = bstRoot.search(4);
assertThat(searchNode).isNull();
searchNode = bstRoot.search(6);
assertThat(searchNode).isNotNull();
assertThat(searchNode.getData()).isEqualTo(6);
searchNode = bstRoot.search(7);
assertThat(searchNode).isNull();
BinaryTreeNode<Integer> rootNode = bstRoot.search(5);
BinaryTreeNode<Integer> rootNodeLeftSubTree = rootNode.getLeftSubTree();
BinaryTreeNode<Integer> rootNodeRightSubTree = rootNode.getRightSubTree();
assertThat(rootNode.getData()).isEqualTo(5);
assertThat(rootNodeLeftSubTree.getData()).isEqualTo(2);
assertThat(rootNodeRightSubTree.getData()).isEqualTo(8);
assertThat(rootNodeLeftSubTree.getLeftSubTree().getData()).isEqualTo(1);
assertThat(rootNodeLeftSubTree.getRightSubTree().getData()).isEqualTo(3);
assertThat(rootNodeRightSubTree.getLeftSubTree().getData()).isEqualTo(6);
assertThat(rootNodeRightSubTree.getRightSubTree().getData()).isEqualTo(9);
}
@Test
@DisplayName("AVL_트리_제거_테스트")
void AVL_트리_제거_테스트() {
BinarySearchTreeNode<Integer> bstRoot = new AVLTreeNode<>(5, (Comparator.comparingInt(o -> o)));
bstRoot.insert(1);
bstRoot.insert(2);
bstRoot.insert(3);
bstRoot.insert(7);
bstRoot.insert(8);
bstRoot.insert(9);
BinaryTreeNode<Integer> rootNode = bstRoot.search(2);
BinaryTreeNode<Integer> rootNodeLeftSubTree = rootNode.getLeftSubTree();
BinaryTreeNode<Integer> rootNodeRightSubTree = rootNode.getRightSubTree();
BinaryTreeNode<Integer> rootNodeRightSubTreeLeftSubTree = rootNodeRightSubTree.getLeftSubTree();
assertThat(rootNode.getData()).isEqualTo(2);
assertThat(rootNodeLeftSubTree.getData()).isEqualTo(1);
assertThat(rootNodeRightSubTree.getData()).isEqualTo(8);
assertThat(rootNodeRightSubTreeLeftSubTree.getData()).isEqualTo(5);
assertThat(rootNodeRightSubTree.getRightSubTree().getData()).isEqualTo(9);
assertThat(rootNodeRightSubTreeLeftSubTree.getLeftSubTree().getData()).isEqualTo(3);
assertThat(rootNodeRightSubTreeLeftSubTree.getRightSubTree().getData()).isEqualTo(7);
assertThat(bstRoot.search(2).getData()).isEqualTo(bstRoot.remove(2).getData());
assertThat(bstRoot.search(7).getData()).isEqualTo(bstRoot.remove(7).getData());
assertThat(bstRoot.search(8).getData()).isEqualTo(bstRoot.remove(8).getData());
assertThat(bstRoot.search(5).getData()).isEqualTo(bstRoot.remove(5).getData());
}
@Test
@DisplayName("AVL_트리_제거_테스트2")
void AVL_트리_제거_테스트2() {
BinarySearchTreeNode<Integer> bstRoot = new AVLTreeNode<>(1, (Comparator.comparingInt(o -> o)));
bstRoot.insert(3);
bstRoot.insert(4);
bstRoot.insert(5);
bstRoot.insert(7);
bstRoot.insert(8);
bstRoot.insert(9);
BinaryTreeNode<Integer> rootNode = bstRoot.search(3);
BinaryTreeNode<Integer> rootNodeLeftSubTree = rootNode.getLeftSubTree();
BinaryTreeNode<Integer> rootNodeRightSubTree = rootNode.getRightSubTree();
assertThat(rootNode.getData()).isEqualTo(3);
assertThat(rootNodeLeftSubTree.getData()).isEqualTo(1);
assertThat(rootNodeRightSubTree.getData()).isEqualTo(7);
assertThat(rootNodeRightSubTree.getLeftSubTree().getData()).isEqualTo(5);
assertThat(rootNodeRightSubTree.getRightSubTree().getData()).isEqualTo(8);
assertThat(bstRoot.search(1).getData()).isEqualTo(bstRoot.remove(1).getData());
assertThat(bstRoot.search(3).getData()).isEqualTo(bstRoot.remove(3).getData());
assertThat(bstRoot.search(5).getData()).isEqualTo(bstRoot.remove(5).getData());
assertThat(bstRoot.search(4).getData()).isEqualTo(bstRoot.remove(4).getData());
assertThat(bstRoot.search(7).getData()).isEqualTo(bstRoot.remove(7).getData());
assertThat(bstRoot.search(9).getData()).isEqualTo(bstRoot.remove(9).getData());
assertThat(bstRoot.search(8).getData()).isEqualTo(bstRoot.remove(8).getData());
}
}동작은 동일해야 합니다. 하지만 균형이 맞는지를 체크해야해서 검증하는 코드를 추가했습니다.
그런데, 실제 동작을 보증해줄지는 모르겠습니다. 그림을 그려가면서 확인했기 때문입니다.
그리고 추가와 삭제시에 리밸런싱에 대한 로직이 들어가면 되므로 상속으로 확장을 시도해보려고 합니다.
리밸런싱 포인트를 찾는 기준은 루트노드를 기준으로 합니다.
AVLTreeNode.java
public class AVLTreeNode<E> extends LinkedBinarySearchTreeNode<E> {
public AVLTreeNode(E data, Comparator<E> comparator) {
super(data, comparator);
}
}이렇게 진행해보겠습니다.
균형을 이루는지 파악할 때는 높이를 파악할 수 있어야 합니다. 높이는 재귀적으로 파악해야합니다.
private int getHeight(BinaryTreeNode<E> binaryTreeNode) {
if (binaryTreeNode == null) {
return 0;
}
int leftHeight = getHeight(binaryTreeNode.getLeftSubTree());
int rightHeight = getHeight(binaryTreeNode.getRightSubTree());
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1; // 큰 쪽의 높이 반환
}거기에 더해서 균형 인수도 파악해야합니다.
private int getEquilibriumFactor(BinaryTreeNode<E> binaryTreeNode) {
if (binaryTreeNode == null) {
return 0;
}
int leftHeight = getHeight(binaryTreeNode.getLeftSubTree());
int rightHeight = getHeight(binaryTreeNode.getRightSubTree());
return leftHeight - rightHeight;
}private BinaryTreeNode<E> rotateLL(BinaryTreeNode<E> binaryTreeNode) {
// LL 회전을 위한 준비
BinaryTreeNode<E> parentNode = binaryTreeNode;
BinaryTreeNode<E> childNode = parentNode.getLeftSubTree();
// LL 회전
parentNode.changeLeftSubTree(childNode.getRightSubTree());
childNode.changeRightSubTree(parentNode);
return childNode; // 변경된 루트 노드 반환
}
private BinaryTreeNode<E> rotateRR(BinaryTreeNode<E> binaryTreeNode) {
// RR 회전을 위한 준비
BinaryTreeNode<E> parentNode = binaryTreeNode;
BinaryTreeNode<E> childNode = parentNode.getRightSubTree();
// RR 회전
parentNode.changeRightSubTree(childNode.getLeftSubTree());
childNode.changeLeftSubTree(parentNode);
return childNode; // 변경된 루트 노드 반환
}private BinaryTreeNode<E> rotateLR(BinaryTreeNode<E> binaryTreeNode) {
// LR 회전을 위한 준비
BinaryTreeNode<E> parentNode = binaryTreeNode;
BinaryTreeNode<E> childNode = parentNode.getLeftSubTree();
parentNode.changeLeftSubTree(rotateRR(childNode)); // 부분적 RR회전
return rotateLL(parentNode); // LL회전
}
private BinaryTreeNode<E> rotateRL(BinaryTreeNode<E> binaryTreeNode) {
// RL 회전을 위한 준비
BinaryTreeNode<E> parentNode = binaryTreeNode;
BinaryTreeNode<E> childNode = parentNode.getLeftSubTree();
parentNode.changeRightSubTree(rotateLL(childNode)); // 부분적 LL회전
return rotateRR(parentNode); // RR회전
}private void rebalance() {
int equilibriumFactor = getEquilibriumFactor(super.node);
if (equilibriumFactor > 1) { // LL OR LR
if (getEquilibriumFactor(super.node.getLeftSubTree()) > 0) {
super.node = rotateLL(super.node);
} else {
super.node = rotateLR(super.node);
}
}
if (equilibriumFactor < -1) { // RR OR RL
if (getEquilibriumFactor(super.node.getRightSubTree()) < 0) {
super.node = rotateRR(super.node);
} else {
super.node = rotateRL(super.node);
}
}
}@Override
public void insert(E data) {
super.insert(data);
rebalance();
}
@Override
public BinaryTreeNode<E> remove(E target) {
BinaryTreeNode<E> removeNode = super.remove(target);
rebalance();
return removeNode;
}문제는 이게 재귀적으로 일어나지 않아서 예상한 테스트 코드와 다르게 나옵니다.
추후 보완이 필요할 것 같습니다.