[자료구조] 이진 탐색 트리(BST)의 개념 및 순회 방법
이진 탐색 트리 (Binary Search Tree) 의 개념
이진 탐색 트리란 ?
Binary Search Tree (이하, BST)는 모든 노드의 왼쪽 서브 트리가 해당 노드 보다 작은 값을 가지고, 오른쪽 서브 트리가 해당 노드 보다 큰 값을 가지는 구조의 Binary Tree 입니다.
위의 그림에서는 노드 20의 왼쪽 서브 트리는 모두 20보다 작은 값을 가지고, 오른쪽 서브 트리의 모든 값은 20보다 큰 값을 가지고 있습니다. 그런데 만약 자식 노드 중 이러한 조건을 하나라도 만족하지 않는 노드가 존재한다면 BST가 아니게 됩니다.
예를 들어 5의 자식 노드 중 오른쪽 자식 노드가 1의 값을 가진다면, 해당 트리는 더이상 BST가 아닙니다.
이러한 특징을 가지는 BST는 항상 작은 값은 왼쪽, 큰 값은 오른쪽으로 정렬되어 있기 때문에 많은 알고리즘에서 데이터 탐색할 때 많이 사용됩니다.
데이터 탐색,삽입,삭제 시 일반적으로는 O(logN)의 시간 복잡도를 가지지만, 최악의 경우 트리가 편향되어 O(n)의 시간 복잡도가 소요되는 경우가 있습니다.
이진 탐색 트리의 장단점
장점
- 데이터의 삽입 / 삭제가 유연하다
- 노드 간의 Reference만 조절하면 되기 때문에, 물리적으로 연속적인 메모리 공간에 저장하는 Array보다 유연합니다.
- 값이 정렬되어 있기 때문에 값의 순서대로 순회할 수 있습니다. (중위 순회)
- 값이 정렬되어 있기 때문에, 삽입/삭제/검색의 시간이 일반적으로 빠릅니다 (시간 복잡도 : O(logN))
단점
- 만약 이진 탐색 트리가 아래의 그림과 같이 한쪽으로 편향되는 경우에는 삽입/삭제/검색의 수행 시간이 느려지고, 최악의 경우 O(N)의 시간복잡도를 가지게 됩니다.
이러한 문제를 해결하기 위해 스스로 균형을 잡는 이진 탐색 트리인 AVL 트리와 Red-Black 트리가 사용되곤 합니다.
이진 탐색 트리 (Binary Search Tree) 순회 방식
BST의 순회 방식으로는 현재 노드를 순회하는 순서에 따라 전위 순회(preorder traversal), 중위 순회(inorder traversal), 후위 순회(postorder traversal)가 있습니다.
전위 순회(pre order traversal)
전위 순회는 현재 노드를 먼저 방문한 뒤, 재귀적으로 왼쪽 서브 트리를 모두 순회 하고 그 다음 오른쪽 서브 트리를 순회하는 방식입니다.
즉, 현재 노드를 가장 먼저 순회한 뒤 나머지 서브트리를 순회하는 방식입니다.
"현재 노드 방문 (ex) 값 출력) => 재귀적으로 왼쪽 서브 트리 순회 => 재귀적으로 오른쪽 서브 트리 순회"
위의 그림을 통해 예시를 들어보겠습니다.
1. 순회를 시작하게 되면 현재 노드는 20이기 때문에 먼저 본인 노드를 방문하고, 그 다음 왼쪽 서브 트리를 재귀 호출합니다.
2. 왼쪽 서브 트리의 현재 노드가 5가 되고 마찬가지로 본인을 먼저 방문 한 뒤, 왼쪽 서브 트리를 재귀 호출합니다.
2. 왼쪽 서브 트리의 현재 노드인 3번 노드는 본인을 방문 한 뒤, 하위 서브트리가 없기 때문에 부모 노드인 5번으로 돌아갑니다.
3. 5번 노드는 왼쪽서브 트리를 모두 순회했기 때문에, 오른쪽 서브 트리를 재귀 호출 합니다.
4. 이와 같은 식으로 오른쪽 서브 트리를 모두 순회한 뒤에는 20번 노드로 반환되고, 20번 노드는 동일한 방식으로 오른쪽 서브트리를 순회합니다.
📌 결과적으로 순회 경로는 다음과 같습니다.
20 -> 5 -> 3 -> 15 -> 10 -> 17 -> 50 -> 30 -> 40
중위 순회(in order traversal)
중위 순회는 재귀적으로 왼쪽 서브 트리를 모두 순회 한 뒤에 현재 노드를 방문하고, 그 다음 오른쪽 서브 트리를 순회하는 방식입니다.
중위 순회는 값의 순서대로 (ex) 숫자면 크기, 문자면 알파벳 순) 순회를 할 수 있다는 장점이 있습니다.
"재귀적으로 왼쪽 서브 트리 순회 => 현재 노드 방문 (ex) 값 출력) => 재귀적으로 오른쪽 서브 트리 순회"
위의 그림을 통해 예시를 들어보겠습니다.
1. 현재 노드 20을 먼저 방문하는 것이 아닌, 왼쪽 서브 트리의 마지막 노드까지 계속해서 순회합니다.
(경로 : 20번 -> 5번 -> 3번)
2. 왼쪽 서브 트리의 마지막 노드인 3번 노드에 도착하면 더이상 왼쪽 서브 트리가 없기 때문에, 현재 노드인 3번 노드를 방문합니다. 그리고 오른쪽 서브 트리 또한 없기 때문에 부모 노드인 5번 노드로 돌아갑니다.
3. 5번 노드는 왼쪽 서브 트리를 모두 순회했기 때문에 본인 노드를 순회하고, 오른쪽 서브트리를 순회합니다.
4. 15번 노드는 먼저 왼쪽 서브트리를 모두 순회하고, 본인 노드를 순회한 뒤 오른쪽 서브 트리를 모두 순회합니다. (이 노드의 경우 10번 -> 15번 -> 17번 순으로 순회합니다)
5. 15번 노드가 모두 순회를 끝냈기 때문에 5번 노드로 돌아가고, 5번 노드도 모두 순회를 끝냈기 때문에 루트 노드인 20번으로 돌아갑니다.
6. 20번 노드는 왼쪽 서브 트리를 모두 순회했기 때문에 본인 노드을 방문하고 (ex) 값 출력), 오른쪽 서브트리 순회를 시작합니다.
7. 위와 같은 방식으로 오른쪽 서브 트리를 모두 순회합니다.
📌 결과적으로 순회 경로는 다음과 같습니다.
3 -> 5 -> 10 -> 15 -> 17 -> 20 -> 30 -> 40 -> 50
후위 순회(post order traversal)
후위 순회는 재귀적으로 왼쪽 서브 트리를 모두 순회하고, 그 다음 오른쪽 서브 트리를 순회한 다음 마지막으로 현재 노드를 방문하는 방식입니다.
즉, 현재 노드를 가장 마지막에 방문하는 방식이라고 할 수 있습니다.
"재귀적으로 왼쪽 서브 트리 순회 => 재귀적으로 오른쪽 서브 트리 순회 => 현재 노드 방문 (ex) 값 출력)"
후위 순회도 나머지 순회 방식과 비슷하게 예시를 들어보겠습니다.
1. 현재 노드 20을 먼저 방문하는 것이 아닌, 왼쪽 서브 트리의 마지막 노드까지 계속해서 순회합니다.
(경로 : 20번 -> 5번 -> 3번)
2. 3번 노드에 도착하면 왼쪽 서브 트리와 오른쪽 서브 트리가 모두 없기 때문에, 현재 노드를 방문한 뒤 5번 노드로 돌아갑니다.
3. 5번 노드는 왼쪽 서브트리를 모두 순회했기 때문에, 오른쪽 서브트리를 위와 같은 방식으로 순회합니다.
4. 5번의 오른쪽 서브트리를 모두 순회한 뒤 본인 노드를 방문하고, 다시 20번 노드로 돌아갑니다.
5. 20번 노드는 왼쪽 서브 트리를 모두 순회했기 때문에, 오른쪽 서브트리를 순회하기 시작합니다.
6. 동일한 방법으로 오른쪽 트리를 모두 순회한 뒤에, 20번 노드로 다시 돌아와서 현재 노드를 방문하고 순회를 마칩니다.
📌 결과적으로 순회 경로는 다음과 같습니다.
3 -> 10 -> 17 -> 15 -> 5 -> 40 -> 30 -> 50 -> 20
자바 코드 구현
Binary Searh Tree의 전위,중위,후위 순회는 자바 언어로 다음과 같이 구현할 수 있습니다.
// 노드를 나타내는 클래스
public static class Node {
public Node left;
public Node right;
public int data;
// 생성자
public static Node makeNode(Node left, int data, Node right) {
Node node = new Node();
node.setLeft(left);
node.setData(data);
node.setRight(right);
return node;
}
// Getter
public Node getLeft() {
return left;
}
public Node getRight() {
return right;
}
}
public class BST {
public static void main(String[] args) {
Node node10 = Node.makeNode(null, 10, null);
Node node17 = Node.makeNode(null, 17, null);
Node node15 = Node.makeNode(node10, 15, node17);
Node node03 = Node.makeNode(null, 3, null);
Node node05 = Node.makeNode(node03, 5, node15);
Node node40 = Node.makeNode(null, 40, null);
Node node30 = Node.makeNode(null, 30, node40);
Node node50 = Node.makeNode(node30, 50, null);
Node root = Node.makeNode(node05, 20, node50);
System.out.print("preOrder : ");
preOrder(root);
System.out.println();
System.out.print("inOrder : ");
inOrder(root);
System.out.println();
System.out.print("postOrder : ");
postOrder(root);
System.out.println();
}
public static void preOrder(Node node) {
// 재귀 종료 조건
if(node == null) {
return;
}
// 현재 노드 방문 - 값 출력
System.out.print(node.getData()+" ");
// 왼쪽 서브 트리 순회
preOrder(node.getLeft());
// 오른쪽 서브 트리 순회
preOrder(node.getRight());
}
public static void inOrder(Node node) {
// 재귀 종료 조건
if(node == null) {
return;
}
// 왼쪽 서브 트리 순회
inOrder(node.getLeft());
// 현재 노드 방문 - 값 출력
System.out.print(node.getData()+" ");
// 오른쪽 서브 트리 순회
inOrder(node.getRight());
}
public static void postOrder(Node node) {
// 재귀 종료 조건
if(node == null) {
return;
}
// 왼쪽 서브 트리 순회
postOrder(node.getLeft());
// 오른쪽 서브 트리 순회
postOrder(node.getRight());
// 현재 노드 방문 - 값 출력
System.out.print(node.getData()+" ");
}
}
📌 참고