[Algorithm] TreeSet
★TreeSet이 사용하는 Red-Black Tree는 이진 탐색 트리의 성능을 향상시킨 것이다. 하지만 RBTree는… 그냥 한번 구현해 보기에는 굉장히 복잡하고 어렵고 개빡치므로 이진 탐색 트리로 먼저 구현해 보고, 이후 Red Black Tree로 개선해 보도록 하자.
★이진 트리란 트리 구조 중 한 노드의 서브 노드가 최대 2개인 것을 의미한다.
★이진 탐색 트리란 다음의 조건을 만족하는 이진 트리 구조이다.
- 모든 노드의 키(데이터를 말한다)는 유일하다.
- 왼쪽 서브트리의 키들은 루트의 키보다 작다.
- 오른쪽 서브트리의 키들은 루트의 키보다 크다.
- 모든 부분 트리도 이진 탐색 트리이다.
★이진 탐색 트리는 탐색 작업을 효율적으로 하기 위해 사용하고, 탐색에 사용되는 각 노드들의 고유의 값을 key라고 한다. 노드들의 값이 고유해야 하기 때문에 중복된 key는 허용되지 않는다.
★중위 순회로 조회하면 크기 순으로 정렬 된 배열을 얻을 수 있다.
★이진 탐색 트리 탐색 알고리즘은 이진 탐색과 유사하다. 재귀함수나 반복문 등으로 처리할 수 있다.
- 루트의 key와 검색key를 비교한다. 같다면 탐색을 종료한다.
- 검색값이 루트보다 크다면 오른쪽, 작다면 왼쪽 서브트리로 가서 다시 1의 과정을 진행한다.
★이진 탐색 트리 삽입 알고리즘
- 먼저 탐색 알고리즘을 수행한다. 탐색이 성공했다면 중복 데이터가 있다는 의미이므로 삽입하지 않고 종료한다.
- 탐색이 실패지점에 도착하면 데이터를 삽입한다.
★이진 탐색 트리 삭제 알고리즘
- 먼저 삭제할 노드를 탐색한다. 이때 3가지 경우로 나뉜다. 삭제될 노드의 자식 노드가 없을 때(리프 노드일 때), 자식 노드가 하나일 때, 자식 노드가 둘 일때.
- 자식 노드가 없는 리프 노드라면 부모 노드를 찾아 참조를 끊는다.
- 자식 노드가 하나라면 부모노드의 자신 참조를 자신의 자식 참조로 바꾼다.
- 자식 노드가 둘이라면 부모노드의 자신 참조를 자신의 왼쪽 서브트리의 최대노드나 오른쪽 서브트리의 최소노드 중 하나로 대체한다. 이를 위해 먼저 대체노드를 찾고, 대체 노드의 키를 삭제할 노드로 카피한 후 대체노드를 원본 트리에서 삭제한다. 삭제하는 원리는 위 3번과 같다. 이 대체노드는 반드시 리프 노드이거나 자식이 하나뿐이기 때문이다.
★알고리즘의 시간 복잡도
- 탐색 : 탐색 알고리즘은 맨 위의 루트 노드에서부터 한칸씩 아래 층으로 내려오는 모양새를 보인다. 따라서 최악의 경우에 맨 아래층(리프 노드)까지 탐색하게 되므로 트리의 높이를 h라고 할 때 O(h)의 시간이 걸린다.
- 삽입 : 탐색과 같은 알고리즘으로 진행되므로 마찬가지의 O(h)의 시간 복잡도를 갖는다.
- 삭제 : 삭제의 경우도 삭제할 노드를 탐색(O(h)))하는 것으로 시작한다. 삭제할 노드의 자식 노드가 둘인 경우도 마찬가지로 대체할 노드를 찾는데에도 O(h)의 시간이 걸리므로 결국 O(h)의 시간 복잡도를 갖는다.
★이진 탐색 트리가 균형 잡혀 있을 경우 h = log n이므로 세 연산 모두 O(log n)의 시간이 걸리지만 이진 탐색 트리는 균형이 잡혀있다는 전제가 없다. 그래서 한쪽으로만 치우쳐 h가 n에 가까운 모양이 될 수도 있는데, 이 경우가 연산의 최악의 경우가 되어 O(n)의 시간 복잡도를 갖게 된다.
★TreeSet을 구현 해보자. 구현을 간단히 하기 위해 Set에 입력되는 데이터를 int로 했다. 객체를 넣기 위해서는 일치 여부와 대소 관계를 구분할 수 있도록 해주어야 한다.
public class MyTreeSet implements Set {
private Node root = null;
public MyTreeSet() {
this.root = null;
}
@Override
public boolean contains(int key) {
Node cur = root;
while (cur != null) {
if (cur.key == key) return true;
else if (cur.key > key) {
cur = cur.left;
} else {
cur = cur.right;
}
}
return false;
}
@Override
public boolean insert(int key) {
Node newNode = new Node(key);
if (root == null) {
root = newNode;
return true;
}
Node parent = null;
Node cur = root;
while (true) {
if (cur.key == key) {
throw new RuntimeException("Key Redundent Exception");
}
else if (cur.key > key) {
parent = cur;
cur = cur.left;
if (cur == null) {
parent.left = newNode;
return true;
}
} else {
parent = cur;
cur = cur.right;
if (cur == null) {
parent.right = newNode;
return true;
}
}
}
}
@Override
public boolean remove(int key) {
Node parent = null;
Node cur = root;
boolean isLeftChild = false;
while (true) {
if (cur == null) return false;
if (cur.key == key) { // 탐색 종료
break;
}
else if (cur.key > key) { // 좌측 트리 탐색
parent = cur;
cur = cur.left;
isLeftChild = true;
} else { // 우측 트리 탐색
parent = cur;
cur = cur.right;
isLeftChild = false;
}
}
// cur : 삭제할 노드
// parent : 삭제할 노드의 부모 노드
// isLeftChild : 삭제할 노드가 부모노드의 좌측 자식이면 true
// 자식 노드가 없을 때
if (cur.left == null && cur.right == null) {
if (cur == root) {
root = null;
} else if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
}
// 왼쪽에만 자식 노드가 있을 때
else if (cur.left != null && cur.right == null) {
if (cur == root) {
root = cur.left;
} else if (isLeftChild) {
parent.left = cur.left;
} else {
parent.right = cur.left;
}
}
// 오른쪽에만 자식 노드가 있을 때
else if (cur.left == null && cur.right != null) {
if (cur == root) {
root = cur.right;
} else if (isLeftChild) {
parent.left = cur.right;
} else {
parent.right = cur.right;
}
}
// 양쪽에 자식 노드가 있을 때
else {
// 대체할 노드를 찾고 트리에서 제거.
// 삭제 노드의 왼쪽 서브트리의 최대노드를 대체 노드로 하기로 한다.
// 대체 노드는 반드시 자식이 하나 뿐이므로 위의 알고리즘으로 삭제할 수 있다.
Node replace = detachReplacementNode(cur);
if (cur == root) {
root = replace;
} else if (isLeftChild) {
parent.left = replace;
} else {
parent.right = replace;
}
replace.left = cur.left;
replace.right = cur.right;
}
return true;
}
// 대체할 노드를 찾아 트리에서 제거
private Node detachReplacementNode(Node root) {
Node parent = root;
Node node = root.left;
while (node.right != null) {
parent = node;
node = node.right;
}
if (parent == root) {
parent.left = node.left;
} else {
parent.right = node.left;
}
return node;
}
public void print() {
if (root == null) {
System.out.println("empty");
return;
}
print(root);
System.out.println();
}
private void print(Node node) {
if (node == null) return;
print(node.left);
System.out.print(node.key + " ");
print(node.right);
}
private class Node {
private int key;
private Node left;
private Node right;
public Node(int key) {
this.key = key;
}
}
}