자바에서의 Binary Search Tree 기본 구현 및 Procedure Abstraction #2
Description
이진탐색트리란? -> 이진 탐색(Binary Search) + 연결리스트(LinkedList)
이진 탐색 트리에는 다음과 같은 속성이 있습니다.
- 모두 유일한(중복되지 않는) 키 값을 가진다.
- 왼쪽과 오른쪽의 서브트리도 이진트리여야 한다.
- 노드의 왼쪽 서브트리는 루트의 키보다 작은 값을 가진다.
- 노드의 오른쪽 서브트리는 루트의 키보다 큰 값을 가진다.
- 무작위로 값을 집어넣어도 어느정도의 균형을 이룬다.
그렇다면 기본적인 Binary Search Tree를 만들어 보겠습니다.
초기의 Binary Search Tree 이하 BST 는 다음과 같습니다.
class BinarySearchTreeNumber {
BinarySearchTreeNumber left;
BinarySearchTreeNumber right;
double value;
public BinarySearchTreeNumber(double number) {
this.value = number;
this.left = null;
this.right = null;
}
}
가장 기본적인 add 연산을 생각해 보겠습니다.
BST는 다음의 규칙을 따릅니다.
-
노드의 왼쪽 서브트리는 루트의 키보다 작은 값을 가진다.
-
노드의 오른쪽 서브트리는 루트의 키보다 큰 값을 가진다.
이 조건을 만족 시키기 위해서는 add연산을 행 할때
해당 노드가 가지고있는 원소의 값을 비교하여 left 혹은 right로 보내는 로직이 필요합니다.
public void add(BinarySearchTreeNumber bst, double value) {
double temp = bst.value;
if (temp - value > 0) { // 내가 더 커 -> 그럼 left에
if (bst.left != null) {
add(bst.left, value);
} else {
bst.left = new BinarySearchTreeNumber(value);
}
} else if (temp - value < 0) { // 내가 더 작아 -> 그럼 right로
if (bst.right != null) {
add(bst.right, value);
} else {
bst.right = new BinarySearchTreeNumber(value);
}
}
}
다음의 add 연산을 사용한다면 우리는 무리없이 bst를 구조를 만들 수 있습니다.
하지만 bst.left 와 같이 별도의 메서드 사용없이 instance variable에 접근할 수 있는 점이 마음에 들지 않습니다.
따라서 구조를 살짝만 변경하겠습니다.
class BinarySearchTreeNumber {
private static final Logger logger = LoggerFactory.getLogger(BinarySearchTree.class);
private BinarySearchTreeNumber left;
private BinarySearchTreeNumber right;
private double value;
public double getValue() {
return value;
}
public void setLeft(BinarySearchTreeNumber left) {
this.left = left;
}
public void setRight(BinarySearchTreeNumber right) {
this.right = right;
}
public BinarySearchTreeNumber getLeft() {
return left;
}
public BinarySearchTreeNumber getRight() {
return right;
}
public BinarySearchTreeNumber(double number) {
this.value = number;
this.left = null;
this.right = null;
}
}
public void add(BinarySearchTreeNumber bst, double value) {
double temp = bst.getValue();
if (temp - value > 0) { // 내가 더 커 -> 그럼 left에
if (bst.getLeft() != null) {
add(bst.getLeft(), value);
} else {
bst.setLeft(new BinarySearchTreeNumber(value));
}
} else if (temp - value < 0) { // 내가 더 작아 -> 그럼 right로
if (bst.getRight() != null) {
add(bst.getRight(), value);
} else {
bst.setRight(new BinarySearchTreeNumber(value));
}
}
}
그런데 정말 BST는 무작위로 input값을 집어넣어도 균형을 이룰까요??
1023개의 노드를 가지고 있는 완전 balanced tree의 모든 leaf 노드의 깊이는 9 입니다. (leaft node == 자식이 없는 == left , right가 없는 노드)
이 idea를 이용하여 저희가 구현한 BST가 balance를 만족하는지 보겠습니다.
leaf노드 깊이의 평균을 측정하는 메서드 만들어 보겠습니다.
- 평균 = leaf노드 깊이 총합 / 총 leaf노드 수
leaf노드는 자식노드가 없는 , 즉 left, right 어떠한 것도 존재하지 않는 노드기 때문에
node.getLegt() ==node.getRight() == null 이라면 leaf 노드로 봐도 문제가 없어 보입니다.
먼저 leaf노드 수를 측정하는 메서드를 만들어 보겠습니다.
public static double countLeafNode(BinarySearchTreeNumber bst, double count) {
double sum = 0;
if (bst.getLeft() == null && bst.getRight() == null) {
return count;
}
if (bst.getLeft() != null) {
sum += countLeafNode(bst.getLeft(), 1);
}
if (bst.getRight() != null) {
sum += countLeafNode(bst.getRight(), 1);
}
return sum;
}
재귀적으로 구현된 이 메서드는 , 자식노드가 존재한다면 그 자식노드를 불러 전체적인 tree 를 탐색합니다.
tree전체를 탐색해야 하는 완전탐색 알고리즘으로 조금 무식해 보일 수 있지만 직관적이고 쉬운 방법입니다.
거의 유사한 구조로 모든 leaf노드의 깊이를 측정하는 메서드도 작성해 보겠습니다.
public static double sumLeafNodeDepth(BinarySearchTreeNumber bst, double depth) {
double depthSum = 0;
if (bst.getLeft() == null && bst.getRight() == null) { // leaf 노드면
return depth;
}
if (bst.getLeft() != null) {
depthSum += sumLeafNodeDepth(bst.getLeft(), depth + 1);
}
if (bst.getRight() != null) {
depthSum += sumLeafNodeDepth(bst.getRight(), depth + 1);
}
return depthSum;
}
추가적으로 leaf노드의 최대 깊이를 측정하는 메서드도 작성해 보겠습니다.
public static double getMaxDepth(BinarySearchTreeNumber bst, double depth) {
double maxDepth = 0;
if (bst.getLeft() == null && bst.getRight() == null) { // leaf 노드면
return depth;
}
if (bst.getLeft() != null) {
maxDepth = Math.max(maxDepth, getMaxDepth(bst.getLeft(), depth + 1));
}
if (bst.getRight() != null) {
maxDepth = Math.max(maxDepth, getMaxDepth(bst.getRight(), depth + 1));
}
return maxDepth;
}
이것으로 우리는 leaf노드 깊이의 평균과 최대를 구함으로써 어느정도 Balance를 갖는 tree인지를 판별 가능해졌습니다.
실제로 1023개의 노드를 add한후 측정해 본다면 제법 괜찮은 Balance를 확인 가능합니다.
그런데 메서드들의 생김새가 거의 비슷합니다
-
인자가 BinarySearchTreeNumber , double
-
double 타입을 return
따라서 이 메서드들을 Procedure Abstraction 해보겠습니다.
@FunctionalInterface
interface SearchTree {
double searchTree(BinarySearchTreeNumber bst, double number);
}
SearchTree라는 함수형 인터페이스를 추가해 줬습니다.
public static double calcLeaf(SearchTree searchTree, BinarySearchTreeNumber bst, double number) {
return searchTree.searchTree(bst, number);
}
또 연산을 묶어줄 메서드 하나를 만들었습니다.
이 메서드의 사용은 다음과 같습니다.
SearchTree sumLeafDepth = new SearchTree() {
@Override
public double searchTree(BinarySearchTreeNumber bst, double number) {
return BinarySearchTreeNumber.sumLeafNodeDepth(bst, number);
}
};
SearchTree countLeafNode = new SearchTree() {
@Override
public double searchTree(BinarySearchTreeNumber bst, double number) {
return BinarySearchTreeNumber.countLeafNode(bst, number);
}
};
SearchTree maxLeafDepth = new SearchTree() {
@Override
public double searchTree(BinarySearchTreeNumber bst, double number) {
return BinarySearchTreeNumber.getMaxDepth(bst,number);
}
};
logger.info("{}", BinarySearchTreeNumber.calcLeaf(sumLeafDepth, bst, 0));
logger.info("{}", BinarySearchTreeNumber.calcLeaf(countLeafNode, bst, 1));
logger.info("{}", BinarySearchTreeNumber.calcLeaf(maxLeafDepth, bst, 0));
다음과 같이 calcLeaf 메서드 하나로 다양한 연산이 가능해 졌습니다.
더 좋은 Procedure Abstraction이 있다면 추가적으로 달아주기시 바랍니다.