학습목표
- Set이 무엇인지
- Queue가 무엇인지
- 왜 Set 을 써야하는지
- 왜 Queue를 써야하는지
- Set은 어디에 쓰이는지
- Queue는 어디에 쓰이는지
- Set의 다른 자료구조와의 차이점은 무엇인지
- Queue의 다른자료구조와의 차이점은 무엇인지
- Set을 구현한 구현체들은 무엇이 있고, 각 차이점은 ?
- Queue를 구현한 구현체들은 무엇이 있고, 각 차이점은?
TreeSet
- TreeSet은 무엇인지?
- TreeSet은 왜, 어디에 쓰이는지?
- TreeSet과 HashSet의 차이점?!
- TreeSet 클래스의 특징과, 구현원리
- 이진탐색트리
- Red-Black Tree
TreeSet을 파해쳐 보자
TreeSet은 JDK1.2부터 제공되고 있으며,HashSet과 마찬가지로 Set을 구현한 클래스다.
HashSet과 달리 TreeSet은
이진탐색트리(BinarySearchTree)
구조로 이루어져 있다. (더 개선된 Red-Black Tree구조로 구현되어있음) 이진탐색트리는 추가와 삭제에는 시간이 조금 더 걸리지만, 정렬, 검색에는 높은 성능을 보여주는 자료구조이다. 그렇기에 HashSet보다 데이터의 추가와 삭제는 더 느리지만, 검색과 정렬에는 유리하다. TreeSet은 데이터를 저장시 이진탐색트리의 형태로 데이터를 저장하기에, 기본적으로 nature ordering을 지원한다.
이진탐색트리(BinarySearchTree)
- 이진탐색트리란 무엇인가?
- 왜?? 어디에 쓰이는가?
- 이진탐색트리의 특징
- 이진탐색트리의 작동원리
이진탐색트리란 이진탐색과 연결리스트(LinkedList)를 결합한 자료구조다. 이진탐색의 효율적인 탐색능력(O(log N))을 유지하면서도, 자료의 입력과 삭제(O(1))를 가능하게끔 구현되었다.
- 이진탐색트리는 다음과 같은 4개의 조건을 만족해야한다.
- 모든 노드의 키는 유일하다. (중복데이터를 갖는 노드가 없다)
- 왼쪽 서브트리의 키들은 루트의 키보다 작다.
- 오른쪽 서브트리의 키들은 루트의 키보다 크다.
- 왼쪽과 오르쪽 서브트리도 이진 탐색트리이다.
https://mattlee.tistory.com/30
Tree Traversal - 트리 순회
트리 순회란 트리의 각 노드를 체계적인 방법으로 방문하는 과정을 말한다. 하나도 빠트리지 않고, 중복없이 정확히 한번만 방문해야한다. 이렇게 노드를 방문하는 순서에따라 3가지가 존재한다.
- 전위순회(preorder)루트노드에서 시작해서 노드-왼쪽 서브트리- 오른쪽 서브트리 순으로 순회한다. 깊이우선순회(dpth-forst-traversal)이라고도 불린다. 위 예시그림에 나온 트리를 전위순환 해보면
- 1-2-4-5-3
- 중위순회(inorder)왼쪽 마지막 자식노드에서 시작한다. 왼쪽 자식노드 - 부모노드 - 오른쪽 자식 노드 순으로 순회한다.
- 4-2-5-1-3
- 후위순회(postorder)중위 순회와 마찬가지로, 왼쪽 마지막 자식노드에서 시작한다.4-5-2-3-1
- 왼쪽 자식노드 - 오른쪽 자식노드 - 부모노드 순으로 순회한다.
사칙연산을 순회해보자!
(A+B)×(C+D)+2
이를 후위표기법으로 바꿀시
AB+CD×2+
전위표기법으로 바꿀시
+×+AB+CD2로 표현할수 있다. 전위표기법은 언어가 함수호출하는 순서와 똑같다!
이진탐색트리의 검색
찾고자하는 값X의 값이 루트노드보다 작으면 왼쪽 서브트리로, 크면 우측 서브트리로 이동하여 찾을때까지 수행한다. 자식노드가 없을때까지 수행했으나 X가 없다면 NULL을 반환한다. (이진탐색 알고리즘과 동일하다.)
``java
// 재귀적인 탐색
public static Node circularSearch(Node node, int key) {
if(node == null) {
return null;
}
if(key == node.data) {
return node;
} else if(key < node.data) {
return circularSearch(node.left, key);
} else {
return circularSearch(node.right, key);
}}
// 반복적인 탐색
public static Node repetitiveSearch(Node node, int key) {
while(node != null) {
if(key == node.data) {
return node;
} else if(key < node.data) {
node = node.left;
} else {
node = node.right;
}
}
return null; // 탐색 실패했을 경우 }
## 이진탐색트리에서의 삽입
원소를 삽입하기 위해서는 먼저 탐색을 수행한다. 이진탐색트리에서는 같은 키값을 갖는 노드가 없어야 하기 때문이다. 탐색을 하다가 탐색을 실패하게 된 위치(마지막 단말노드의 하위노드로)에 바로 삽입이 된다. 시간복잡도는 어떻게 될까??
탐색(O(H)) + 삽입(O(1))로 O(H)일까? 아니면 LinkedList처럼 순수 삽입연산만 생각해서 O(1)일까? 처음엔 LinkedList처럼 O(1)이라고 생각했다. 그러나 찾아본 결과 O(H)라고 한다. 삽입연산 자체가 결국 빈 위치를 찾는것에 해당되므로, 탐색 자체를 곧 삽입의 핵심로직으로 보기 때문인것 같다.
```java
// 노드 삽입
public Node insertNode(Node node, int key) {
if(node == null) {
return new Node(key); // 노드가 빈 경우, 새로운 노드 삽입후 반환
}
// 그렇지 않으면 순환적으로 트리를 내려감
if(key < node.data) {
node.left = insertNode(node.left, key);
} else if(key > node.data) {
node.right = insertNode(node.right, key);
}
// 삽입 완료 후, 루트 노드 반환하며 끝
return node;
}이진탐색트리에서의 삭제연산
이진탐색트리에서 가장 복잡한 연산이다.
삭제하기 위해서는 먼저 노드를 탐색해야한다.
이후 3가지 경우를 고려해야한다.
- 삭제하려는 노드가 단말노드일 경우
- 삭제하려는 노드가 하나의 서브트리만(왼쪽or오른쪽) 가지고있는 경우
- 삭제하려는 노드가 두개의 서브트리 모두를 가지고 있는 경우
삭제하려는 노드가 단말노드 일때
단말노드는 자식노드가 없으므로, 단말노드 자체만 지우면 된다. → 단말노드의 부모노드를 찾고, node.left || node.right 값을 null로 할당하면 된다. 탐색:O(H), 삭제: O(1)
삭제하려는 노드가 하나의 서브트리만 가지고 있을때
자기자신은 삭제하고, 서브트리는 자기자신의 부모노드에 붙여주면 된다. → 삭제하려는 부모노드를 찾고, node.left || node.right를 자기자신의 자식노드 주소값으로 할당한다!
탐색:O(H), 삭제:O(1)
삭제하려는 노드가 두개의 서브트리를 가지고 있을때
어떤 서브트리를 삭제할 노드의 위치로 가져오느냐가 중요하다. 삭제될 노드와 가장 값이 비슷한 노드를 후계자로 선택해야 이진 탐색트리가 유지된다.
- 가장 가까운 노드란??왼쪽 서브트리에서 가장 큰값이나 오른쪽 서브트리에서 가장 작은값이 삭제되는 노드와 가장 가깝다.
예를들어 노드18을 삭제할 경우, 후계자가 될수있는 노드는 12와 22이다. 여기서 어떤 노드를 선택해야 할까?? → 둘중 무엇을 선택하든 상관없다. 예제에서는 오른쪽 트리의 가장 작은값으로 선택해보자.
22 노드를 찾기위해 탐색을 진행한다.
최종적으로 22를 18의 자리로 옮기면 되겠다.
// 노드 삭제
public Node deleteNode(Node root, int key) {
if(root == null) {
return root;
}
if(key < root.data) { // 키가 루트보다 작다면, 왼쪽 서브 트리에 있는 것
root.left = deleteNode(root.left, key);
} else if(key > root.data) { // 키가 루트보다 크다면, 오른쪽 서브 트리에 있는 것
root.right = deleteNode(root.right, key);
} else { // 키가 루트와 같다면 이 노드가 바로 삭제할 노드
if(root.left == null) { // 1번, 2번의 경우 - 1. 단말 노드인 경우 / 2. 하나의 서브트리만 있는 경우
return root.right; // 널 값이면 널 반환 / 오른쪽 있으면 오른쪽 반환해서 이전의 if, else if에서의 왼쪽이든 오른쪽 노드에 붙여주는 것
} else if(root.right == null) {
return root.left; // left가 널인 경우와 동일
}
// 3번의 경우 - 3. 두개의 서브 트리가 있는 경우 (left, right 둘 다 null 아님
Node temp = minValueNode(root.right); // 오른쪽 서브 트리에서 가장 작은 값(가장 왼쪽 노드)가 후계 노드
root.data = temp.data; // 후계 노드 값 복사(삭제할 노드의 값을 후계 노드 값으로 변경
root.right = deleteNode(root.right, temp.data); // 후계 노드 삭제 - 오른쪽 노드에게 가장 작은 값을 가졌던 맨 왼쪽 단말노드를 다시 deleteNode를 호출해 삭제하라고 함
}
return root;
}
// 후계 노드 찾기 - 오른쪽 서브트리에서 가장 작은 값을 가지는 노드 반환
public Node minValueNode(Node node) {
Node currentNode = node;
while(currentNode.left != null) {
currentNode = currentNode.left; // 맨 왼쪽 단말 노드를 찾으러 내려감
}
return currentNode;
}결국 최종적으로 단말노드를 찾아야하므로 O(H)의 탐색시간과, 단말노드와 삭제될 노드의 위치를 바꿔주는 연산이 O(1)시행, O(H) + O(1) 의 시간이 소요되며, O(H)라고 보면 되겠다.
이진탐색트리 분석해보자.
위에서 알아본 이진탐색트리이 3가지 연산 탐색,삽입,삭제를 보면 결과적으로 트리의 높이H에 따라 시간복잡도가 결정되는 것을 볼수있다.
따라서 N개의 노드를 가지는 이진탐색트리 경우, '일반적'인 이진탐색트리의 높이는 log₂N이므로
평균적인 이진탐색트리의 연산은 O(log₂N) 이 되겠다.
그러나 위의 예시처럼, '일반적인' 이진탐색트리에 해당할뿐, 왼쪽 서브트리만 갖게되는 편향적인 이진트리에서는 N = H가 되어버려 O(N)이 될수있다. 따라서 이런 최악의 경우를 방지하기 위해, 트리의 높이를 log₂N으로 한정하는 균형기법이 필요해졌다.
그렇다면 TreeSet을 구현하고 있는 Red_Black Tree는 무엇인가?
- Red-Black 트리란?
- 왜? 어디에 쓰이는지?
- Red-Black 트리의 동작 방식
Red-Black 트리란?
Red-Black트리는 각각의 노드가 레드나 블랙인 색상 속성을 가진 이진탐색트리이다. 이진탐색트리가 가지는 조건에 대해 아래의 추가적인 조건을 만족해야한다.
Red-Black 트리의 조건
- 노드는 레드 혹은 블랙중 하나이다.
- 루트 노드는 블랙이다.
- 모든 리프노드(단말노드)들은 블랙이다.
- 레드노드의 자식노드 양쪽은 언제나 모두 블랙이다.
- 어떤 노드로부터 시작되어 그에 속한 하위 리프 노드에 도달하는 모든 경로에는 리프 노드를 제외하면 모두 같은 개수의 블랙노드가 있다.
왜? 그리고 어디에 Red-Black 트리를 써야하나??
N개의 노드를 가진 일반적인 이진탐색트리는 모든 연산에 대해서 O(log₂N)의 시간복잡도를 보장했다. 문제는 일반적이지 않은경우가 있다는 것이다. 편향적인 이진트리가 되면 최악의 경우 O(N)이 될수있다. 이런 문제점을 개선하기 위해서, 트리의 높이를 log₂N으로 한정할 수있는 Red_Black Tree가 나오게 되었다. 즉, Red-Black Tree는 최악의 상황에서도 일정한 실행시간을 보장할 수있다. 실시간 처리와 같은 실행시간이 중요한 경우와 일정실행시간을 보장하는 다른 자료구조를 만들때도 쓰일수 있다.
Red-Black 트리의 특성
위에서 설명한 Red-Black트리의 조건을 만족하면 매우 중요한 특성이 나타난다.
루트 노드부터 가장 먼 경로까지의 거리가 가장 가까운 경로까지의 거리의 두 배보다 항상 작다.
다시말해 Red-Black트리는 항상 개략적으로 균형이 잡혀있다. 즉 최악의 경우가 발생하지 않으므로, 일반적인 이진탐색트리보다 효율적이라고 할 수있다.
NIL은 데이터가 없는 Dummy노드로 색깔만 검정색이다. 2번째 규칙을 유지하기 위해 일부러 생성한것이다.
Red-Black트리의 연산
탐색
Red-Black트리의 탐색은 이진탐색트리의 탐색과 갖기 때문에 생략하도록 한다.
삽입
삽입연산을 알아보기 전에, 회전이라는 연산을 알아보자.
회전
회전이란 부모노드와 자식노드의 위치를 바꾸는것이다. 방향에 따라 우회전,좌회전으로 나눈다. 우회전은 왼쪽 자식과 위치를, 좌회전은 오른쪽 자식과 위치를 바꾸는 것을 말한다.
간단할듯 보이지만 그렇게 간단하지 않다. 아래의 그림을 보자
노드5와 노드8을 회전한다고 생각하자. 이진탐색트리의 특성상 왼쪽 자식노드는 부모노드보다 작은값이 들어가야 하는데, 노드5의 왼쪽 자식노드가 8이 되게된다. 이렇게 단순히 자식과 부모의 위치를 바꾸면 레드블랙트리 뿐 아니라 이진탐색트리의 규칙을 무너트린다. 그렇기때문에 '회전'에서는 특수한 처리가 같이 진행된다.
우회전을 할때에는 왼쪽 자식노드의 오른쪽 자식노드를 부모노드의 왼쪽 자식으로 연결 시켜준다. 위의 그림에서는 노드6이 노드8의 왼쪽 자식노드가 되는것이다.
좌회전을 해보자. 오른쪽 자식의 왼쪽 자식노드를 부모노드의 오른쪽 자식노드로 연결 시킨다. 위의 그림에서는 노드6이 노드5의 오른쪽 자식노드가 되겠다.
그럼 다시 삽입 연산에 대해서 알아보자.
레드블랙 트리에 노드가 삽입되고 나면, 이 노드를 빨간색으로 칠하고 양쪽 자식에 NIL노드를 붙여준다. 그 다음단계는 주의 노드의 색에 따라 달라진다. 여기서 삼촌노드 라는 개면이 나오는데, 이는 같은 높이에 잇는 옆 노드의 부모 노드를 뜻한다.
- 삼촌노드도 빨간색 일경우
- 삼촌노드가 검은색이며, 새로 삽입한 노드가 부모 노드의 오른쪽 자식인 경우
- 삼촌노드가 검은색이며, 새로 삽입한 노드가 부모 노드의 왼쪽 자식인 경우
삼촌노드가 빨간색 일경우에는 부모노드와 삼촌노드를 검정색으로 칠한후, 할아버지 노드를 빨간색으로 칠한다. 그후 노드G에 대해서 규칙검사를 똑같이 실행해서 루트노드까지 올라간다.
2번의 경우 삼촌노드가 검은색이고, 새로 삽입한 노드가 오른쪽 자식노드일 경우, 부모노드와 자식노드를 좌회전을 한다. 이렇게 되면 3번의 형태로 변한다. 즉 2번의 경우에는 자체적인 해결법이 없고, 3번의 형태로 변한후, 3번의 해결법을 따라간다.
3번의 경우 삼촌노드가 검은색이고, 삽입한 노드가 왼쪽 자식노드일때는 할아버지 노드를 빨간색으로 칠하고, 할아버지 노드를 기준으로 오르쪽으로 회전시킨다.
알게 된 점
- Set이 무엇인지
- Set은 Collection을 확장한 인터페이스로, 순서가 없으며 중복을 허용하지 않는 자료구조이다.
- Queue가 무엇인지
- 왜 Set 을 써야하는지
- 순서가 없고 중복을 허용하지 않기 때문에, 이런 작업에 있어서는 Set을 쓰는것이 성능상 이롭다.
- 왜 Queue를 써야하는지
- Set은 어디에 쓰이는지
- 순서가 관계없고 데이터가 존재하는지 없는지 여부만 중요할때 쓰인다.
- Queue는 어디에 쓰이는지
- Set의 다른 자료구조와의 차이점은 무엇인지
- 순서가 없고, 중복을 허용하지 않는다.
- Queue의 다른자료구조와의 차이점은 무엇인지
- Set을 구현한 구현체들은 무엇이 있고, 각 차이점은 ?
- HashSet
- HashSet은 내부적으로 HashMap을 호출, 구성관계를 가지고 있다.
- 순서가 없고, 정렬되어있지 않으며 HashMap을 사용하므로, 추가,삭제, contain등의 시간복잡도는 O(1)이다.
- TreeSet
- TreeSet은 이진탐색트리의 형태로 데이터를 저장 한다. 자바에서는 더 개선된 Red-BlackTree로 구현되어있다.
- 이진탐색트리란 이진탐색과 연결리스트(LinkedList)를 결합한 자료구조이다. 정렬된 탐색에서 큰 효율을 보이는 이진탐색과 추가와 삭제가 가능한 연결리스트를 결합했다.
- 이진탐색의 뜻은 찾고자하는 배열의 탐색범위가 단계를 거칠수록 반절로 줄어들기 때문에 붙여졌다.
- 이진탐색은 탐색하고자 하는 범위의 임의의 중간값 X를 선택, 찾고자 하는 값 Y와 비교하여 Y가 작으면 좌측으로, 크면 우측의 범위를 대상으로하여 동일한 탐색을 실행한다.(술게임 업다운에 적용됨)
- 이때 이진탐색의 시간복잡도는 O(logN)을 보장한다.
- 빅오표기법은 알고리즘의 효율성을 나타내는 지표로, 시간복잡도와 공간복잡도가 있다.
- 빅오표기법은 상수항을 무시하고, 가장 지배적인 항을 제외한 나머지 항은 무시한채 표기한다.
- N개의 노드를 가진 일반적인 이진탐색트리는 모든연산에 대해 O(log₂N)을 보장한다. 하지만 편향적인 이진탐색트리에서는 노드의 갯수 N = 높이 H 가 되는 일도 발생할 수있다. 즉 최악의 경우 O(N)이 되어버린다.
- 최악의 경우 O(N)의 시간복잡도를 갖게 되는 이진탐색트리를 개선한 것이 Red-Black트리이다. Red-Black트리는 높이를 log₂N으로 한정할수있다. 즉 모든 연산에 대해서 시간복잡도가 O(log₂N)을 보장한다.
- LinkedHashSet
- HashSet
- Queue를 구현한 구현체들은 무엇이 있고, 각 차이점은?
Reference
알고리즘 :: 이진트리와 순회 전위순회(preorder), 중위 순회(inorder), 후위 순회(postorder) C/C++ 구현
'프로그래밍 > Java' 카테고리의 다른 글
| Set과 Queue -Reboot(3) (2) | 2021.05.31 |
|---|---|
| Vector와 Hashtable은 왜 안쓰일까? (0) | 2021.05.30 |
| ArrayList VS LinkedList -addOn(1) (0) | 2021.05.27 |
| Set과 Queue -Reboot(1) (0) | 2021.05.27 |
| LRU 캐시 (0) | 2021.05.26 |