이진트리와 이진트리검색
이진트리
효율적인 탐색을 위해서는 어떻게 탐색해야 할까요?
그 보다 효율적인 탐색을 위한 저장방법이 무엇이 있을지 고민해봐야 합니다.
이진트리
이진트리는 탐색작업을 효율적으로 하기 위한 자료구조 입니다.
이진탐색트리를 만들 때는 몇가지 규칙이 있습니다.
-
규칙 1 : 이진 탐색 트리의 노드에 저장된 키는 유일해야합니다.
-
규칙 2 : 루트 노드의 키가 왼쪽 서브 트리를 구성하는 어떠한 노드의 키보다 커야합니다.
현재 루트 노드의 값은 100입니다. 이 노드를 기준으로 왼쪽의 노드들의 값은 100을 넘지 않습니다.
-
규칙 3 : 루트 노드의 키가 오른쪽 서브 트리를 구성하는 어떠한 노드의 키보다 작습니다.
-
규칙 4: 왼쪽과 오른쪽 서브트리도 이진 탐색 트리입니다.
이제 이진탐색트리를 코드로 작성해보겠습니다.
먼저 MyTree라는 클래스를 선언해서 이 클래스안에 작성하겠습니다.
public class MyTree {
}
내부 클래스 선언하기
Tree는 Node간의 연결로 이루어져 있습니다.
Node는 3개의 변수를 갖고 있습니다.
현재 자신의 값을 나타내는 value과 왼쪽 노드를 가르키는 Node타입의 left
그리고 오른쪽 노드를 가르키는 Node타입의 right가 있습니다.
class Node {
int value;
Node left;
Node right;
public Node(int value) {
this.value = value;
this.left = null;
this.right = null;
}
}
내부변수 선언하기
Tree는 가장 상위의 Node만 알고 있으면 됩니다.
Node root;
add 함수 작성하기
이제 본격적으로 Tree에 데이터를 추가하는 add() 함수를 작성해보겠습니다.
add 함수
public void add(int value) {
root = addRecursive(root, value);
}
public Node addRecursive(Node currentNode, int value) {
if(currentNode == null) {
return new Node(value);
}
//왼쪽으로 이동
if(currentNode.value > value) {
currentNode.left = addRecursive(currentNode.left, value);
//오른쪽으로 이동
} else if (currentNode.value <value) {
currentNode.right = addRecursive(currentNode.right,value);
}
// 값이 존재
return currentNode;
}
add 함수는 재귀함수인 addRecursive를 호출하여 반복합니다.
public void add(int value) {
root = addRecursive(root, value);
}
먼저 root 노드를 넣어주어 맨 처음의 노드부터 탐색합니다.
root = addRecursive(root, value);
넣을 값이 노드의 현재 값 보다 작다면 왼쪽으로 이동하고,
//왼쪽으로 이동
if(currentNode.value > value) {
currentNode.left = addRecursive(currentNode.left, value);
넣을 값이 노드의 현재 값 보다 크다면 오른쪽으로 이동합니다.
} else if (currentNode.value <value) {
currentNode.right = addRecursive(currentNode.right,value);
}
넣을 값이 노드의 현재 값과 같다면 현재 노드를 리턴합니다.
// 값이 존재
return currentNode;
addRecursive 함수는 currentNode가 null을 만날 때 까지 자기자신을 계속 호출하게 됩니다.
만약 null을 만나게 된다면, 그 자리에 새로운 노드를 추가하고 리턴합니다.
if(currentNode == null) {
return new Node(value);
}
contains() 함수 작성하기
Contains() 함수는 해당 값이 트리에 존재하는지 검사하는 함수입니다.
만약 값이 존재한다면 True를 리턴하고, 존재하지 않는다면 False를 리턴합니다.
Contains() 함수도 add() 함수처럼 재귀함수를 이용합니다.
contains() 함수
public boolean contains(int value) {
return containsRecursive(root, value);
}
public boolean containsRecursive(Node currentNode, int value) {
if(currentNode == null) {
return false;
}
if(currentNode.value == value) {
return true;
}
return currentNode.value > value ?
containsRecursive(currentNode.left, value) :
containsRecursive(currentNode.right, value);
}
먼저 contains 함수를 만들겠습니다.
public boolean contains(int value) {
return containsRecursive(root, value);
}
그런 다음 containsRecursive 함수를 만들어주세요.
public boolean containsRecursive(Node currentNode, int value) {
}
이 함수는 호출될때 첫번째 인자는 트리의 root를 받고, 두번째 인자는 찾을 값을 받습니다.
public boolean containsRecursive(Node currentNode, int value) {
if(currentNode == null) {
return false;
}
if(currentNode.value == value) {
return true;
}
return currentNode.value > value ?
containsRecursive(currentNode.left, value) :
containsRecursive(currentNode.right, value);
}
if(currentNode == null) {
return false;
}
계속해서 탐색했는데, 다음 탐색할 Node가 null이라면 해당 값이 존재하지 않기 때문에 false를 리턴합니다.
if(currentNode.value == value) {
return true;
}
Node의 값이 찾을 value와 일치한다면 true를 반환 해줍니다.
return currentNode.value > value ?
containsRecursive(currentNode.left, value) :
containsRecursive(currentNode.right, value);
이 두개의 조건에 만족하지 않는다면, 계속 탐색하게되는데, Node의 값보다 탐색할 값이 작다면 왼쪽노드로 탐색하고,
그게아니라면 오른쪽 노드를 탐색하게 됩니다.
remove 함수 작성하기
remove 함수
public Node removeRecursive(Node currentNode, int value) {
// 찾는 값이 없으면 null을 반환
if(currentNode == null) {
return null;
}
// 찾는 값이 존재
if(currentNode.value == value) {
// 자식 노드들이 하나도 없으면
if(currentNode.right == null && currentNode.left == null) {
return null;
}
//자식노드가 하나만 있으면
if(currentNode.right == null) {
// currentNode = currentNode.left;
return currentNode.left;
}
//자식노드가 하나만 있으면
if(currentNode.left == null) {
// currentNode = currentNode.right;
return currentNode.right;
}
//자식노드가 두개 있으면
int smallestValue = findSmallestValue(currentNode);
currentNode.value = smallestValue;
currentNode.right = removeRecursive(currentNode.right, smallestValue);
return currentNode;
}
if (value < currentNode.value) {
currentNode.left = removeRecursive(currentNode.left, value);
return currentNode;
}
currentNode.right = removeRecursive(currentNode.right, value);
return currentNode;
}
public int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}
해당 Node를 삭제하는 Remove 함수를 작성하겠습니다.
Remove 함수는 생각해야 할 경우가 많은데요, 만약 중간 노드가 삭제 됬다면,
트리의 특성에 맞게 노드를 다시 이어줘야하기 때문입니다.
Remove 함수도 이전 함수들과 같이 재귀함수를 이용합니다.
먼저 Remove 함수를 만들겠습니다.
remove 함수
public void remove(int value) {
root = removeRecursive(root, value);
}
remove 함수는 재귀함수인 removeRecursive를 호출합니다.
첫번째 인자로는 root Node를 넣어주고, 두번째는 삭제할 값을 넣어줍니다.
removeRecursive 함수
public Node removeRecursive(Node currentNode, int value) {
}
먼저 마지막으로 탐색했을 때 다음노드가 null이라면,
null을 반환하여 재귀함수가 더 이상 호출되지 않도록 합니다.
// 찾는 값이 없으면 null을 반환
if(currentNode == null) {
return null;
}
만약 찾는 값이 존재한다면 3가지로 분기를 해줘야합니다.
if(currentNode.value == value) {
}
- 자식 노드들이 하나도 없는가?
- 자식노드가 하나만 있는가?
- 자식노드가 두개가 있는가?
먼저 자식노드들이 하나도 없는 경우를 보겠습니다.
자식노드들이 하나도 없는 경우
해당 트리에서 50을 없앤다고 가정해봅시다.
50의 자식들은 존재하지 않으므로 해당 Node를 null로 표현해주면 됩니다.
50은 100의 왼쪽에 있으므로 100.left = null 이런식으로 코드를 짜면 100과 50은 연결이 끊기게 됩니다.
// 찾는 값이 존재
if(currentNode.value == value) {
// 자식 노드들이 하나도 없으면
if(currentNode.right == null && currentNode.left == null) {
return null;
}
}
자식노드들이 하나만 있는 경우
이제 자식노드를 하나만 갖고있는 경우를 생각해봅시다.
50을 삭제한다고 가정하면, 50은 삭제가되고, 100의 왼쪽노드는 25가 됩니다.
코드로는 100.left = 50.left 로 작성하면 될 것 같습니다.
50을 삭제한다고 가정하면, 50은 삭제되고 100의 왼쪽노드는 70이 됩니다.
코드로는 100.left = 50.right 로 작성하면 될 것 같습니다.
// 찾는 값이 존재
if(currentNode.value == value) {
// 자식 노드들이 하나도 없으면
if(currentNode.right == null && currentNode.left == null) {
return null;
}
//자식노드가 하나만 있으면
if(currentNode.right == null) {
return currentNode.left;
}
//자식노드가 하나만 있으면
if(currentNode.left == null) {
return currentNode.right;
}
}
자식노드가 두개 있으면
자식노드가 두개 있으면 조금은 생각을 해봐야합니다.
다음과 같은 트리가 있다고 가정해봅시다.
50을 삭제한다고 가정하면 어떤 값이 50을 대체하게 될까요?
여기서 이진트리의 규칙을 잘 이용해야 합니다.
다음과 같은 이진트리에서 100을 기준으로 왼쪽노드들은 절대 100을 넘지 않습니다.
또한 다음과 같은 이진트리에서 50을 기준으로 왼쪽노드들은 절대 50을 넘지 않습니다.
이런 특징을 살려서 50을 대체할 숫자를 찾으면 됩니다.
50을 삭제한다고 가정했을 때 50보다 큰 숫자를 찾아야하니 50의 오른쪽 노드에서 찾으면 되는데,
그 중에 가장 작은 숫자를 찾아합니다.
//자식노드가 두개 있으면
int smallestValue = findSmallestValue(currentNode);
currentNode.value = smallestValue;
currentNode.right = removeRecursive(currentNode.right, smallestValue);
현재 currentNode는 50의 숫자를 가진 노드입니다.
findSmallestValue를 호출해 가장 작은 숫자를 찾습니다.
찾은 가장작은 숫자가 50을 대체하게 되고(예제에서는 60), 가장작은 숫자(60)를 노드에서 제거해줍니다.
가장 작은 숫자를 찾는 함수
public int findSmallestValue(Node root) {
return root.left == null ? root.value : findSmallestValue(root.left);
}
이진트리탐색
이진트리를 탐색하는 방법에는 여러종류가 있는데요, 그 중에서도 DFS(깊이우선탐색)과 BFS(너비우선탐색)을 알아보겠습니다.
DFS(깊이우선탐색)
깊이우선탐색은 한쪽노드를 계속 파고들어 최대한 깊숙히 들어가는 탐색입니다.
//깊이 우선 탐색
public void dfs() {
dfsR(root);
}
public void dfsR(Node node) {
if(node != null) {
System.out.print(node.value + " ");
dfsR(node.left);
dfsR(node.right);
}
}
BFS(너비우선탐색)
너비우선탐색은 최대한 넓게 탐색하는 방법입니다.
//너비 우선 탐색!
public void bfs() {
if (root == null) {
return;
}
Queue<Node> nodes = new LinkedList<>();
nodes.add(root);
while (!nodes.isEmpty()) {
Node node = nodes.remove();
System.out.print(" " + node.value);
if (node.left != null) {
nodes.add(node.left);
}
if (node.right!= null) {
nodes.add(node.right);
}
}
}
시간복잡도
최악의 경우에는 한쪽으로 기울어진 사향트리가 되기 때문에
이런경우에는 시간복잡도가O(n)이 됩니다.
LinkedList하고 비슷하죠
만약 이진트리가 균형적으로 생성되어 있는 경우는 트리의 높이에 비례하게 됩니다.
트리의 높이를 = h 라고 했을 때, h = log2n 이므로
시간복잡도는 O(log n)을 가집니다.
테스트코드
@Test
public void TreeTest() {
MyTree tree = new MyTree();
tree.add(100);
tree.add(50);
tree.add(200);
tree.add(25);
tree.add(70);
tree.add(12);
tree.add(35);
tree.add(60);
tree.add(90);
tree.dfs();
tree.bfs();
assertTrue(tree.contains(25));
tree.remove(25);
assertFalse(tree.contains(25));
}