이진 탐색 트리
이진 탐색 트리
이진 탐색 트리(BST: Binary Search Tree)는 탐색을 위한 이진 트리 형식의 자료구조이다. 임의의 노드를 루트 노드로 하는 서브 트리에서 왼쪽 자식 노드는 루트 노드보다 작은 값이, 오른쪽 자식 노드는 루트 노드보다 큰 값이 들어간다. 이진 탐색 트리의 노드는 유일한 값을 가진다.
이진 탐색 트리 탐색연산
찾으려고 하는 데이터가 현재 노드의 데이터보다 작은 경우는 왼쪽 자식 노드로, 큰 경우는 오른쪽 자식 노드로 이동하면서 재귀적으로 탐색하면 된다. 현재 노드의 데이터와 찾는 데이터가 같다면 현재 노드를, 현재 노드가 null이라면 트리에 찾으려는 데이터가 없다는 뜻이므로 null을 반환한다.
이진 탐색 트리 삽입연산
삽입하려는 데이터가 현재 노드의 데이터보다 작은 경우, 현재 노드의 왼쪽 자식이 없다면 그대로 왼쪽 자식 노드로 삽입한다. 클 경우는 오른쪽 자식 노드로 삽입하면 된다. 왼쪽 또는 오른쪽 자식이 있을 경우에는 해당 자식 노드로 이동해서 위의 과정을 재귀적으로 반복하면 된다. 또한 이진 탐색 트리에는 같은 데이터가 없어야 하므로 현재 노드의 데이터와 삽입하려는 데이터가 같다면 더 이상 탐색을 진행하지 않고 메소드를 종료한다.
이진 탐색 트리 삭제연산
삭제하려는 노드가 리프 노드일 경우
22노드를 삭제한다고 생각해보자. 리프 노드이므로 부모 노드와의 링크를 끊어도 이진 탐색 트리가 유지된다. 따라서 리프 노드를 삭제할 때는 단순히 부모 노드와의 링크만 끊어주면 된다.
삭제하려는 노드의 서브 트리가 하나인 경우
32노드를 삭제한다고 생각해보자. 서브 트리가 있긴 하지만 삭제할 노드 자리에 서브 트리의 루트 노드를 대신 넣어도 이진 탐색 트리가 유지된다. 따라서 서브 트리가 하나인 노드를 삭제할 경우, 삭제할 노드의 자리에 서브 트리의 루트 노드를 대신 삽입하면 된다.
삭제하려는 노드의 서브 트리가 두개인 경우
16 노드를 삭제한다고 생각해보자. 16노드 대신 서브 트리의 노드 중 하나를 대신 삽입해야 하는데, 어떤 노드를 삽입해야 이진 탐색 트리의 형태를 유지할 수 있을까?
답은 왼쪽 서브트리의 노드 중 가장 오른쪽에 위치하는 노드 혹은 오른쪽 서브트리의 노드 중 가장 왼쪽에 위치하는 노드이다. 각각 삭제하려는 노드의 inorder predecessor, inorder successor이다. 그렇다면 왜 이 두 노드만 가능할까?
왼쪽 서브 트리의 노드 중 가장 오른쪽에 위치하는 노드가 아닌 다른 노드를 선택하는 경우를 생각해보자. 해당 노드를 삭제하려는 노드 위치에 삽입한다면, 왼쪽 서브트리의 노드는 전부 해당 노드보다 작아야 한다. 하지만 이 경우 왼쪽 서브트리에 루트 노드보다 큰 노드가 있을 수도 있다. 따라서 이진 탐색 트리가 유지되지 않는다. 위의 트리에서 11노드를 16노드 대신 삽입했다고 가정하면, 왼쪽 서브 트리에 11보다 큰 12와 13이 존재하게 된다. 오른쪽도 동일한 이유이다.
13노드를 루트 노드로 했을 때 이진 탐색 트리
21노드를 루트 노드로 했을 때 이진 탐색 트리
이진 탐색 트리 탐색, 삽입, 삭제연산 구현
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
class Node {
int data;
Node left, right;
Node(int data) {
this.data = data;
left = right = null;
}
}
class Tree {
private Node root;
public Node getRoot() {
return root;
}
public Node search(Node node, int data) {
if(node == null) {
return null;
}
if(data > node.data) {
return search(node.right, data);
}
else if(data < node.data) {
return search(node.left, data);
}
else {
return node;
}
}
public void insert(Node node, int data) {
if(root == null) {
root = new Node(data);
return;
}
if(data > node.data) {
if(node.right == null) {
node.right = new Node(data);
}
else {
insert(node.right, data);
}
}
else if(data < node.data) {
if(node.left == null) {
node.left = new Node(data);
}
else {
insert(node.left, data);
}
}
else {
return;
}
}
public Node delete(Node node, int data) {
if(node == null) {
return null;
}
if(data > node.data) {
node.right = delete(node.right, data);
}
else if(data < node.data) {
node.left = delete(node.left, data);
}
else {
if(node.right == null) {
Node ret = node.left;
node = null;
return ret;
}
else if(node.left == null) {
Node ret = node.right;
node = null;
return ret;
}
else {
Node newRoot = findSuccessor(node.right);
node.data = newRoot.data;
delete(node.right, node.data);
}
}
return node;
}
private Node findSuccessor(Node node) {
while(node.left != null) {
node = node.left;
}
return node;
}
}
이진 탐색 트리 순회
이진 탐색 트리는 순회별로 결과의 특징이 있다.
전위 순회 전위 순회의 결과대로 트리를 다시 구성하면 원본 트리를 얻을 수 있다.
중위 순회 중위 순회를 하면 정렬된 데이터를 얻을 수 있다.