Data Structure
Red-BlackTree, AVL Tree
후후후하하하
2024. 4. 24. 16:52
레드-블랙 트리
- 자가 균형 이진 트리.
- 모든 노드는 빨간색 또는 검은색이다.
- 루트 노트든 검은색이다.
- 모든 리프노드들은 검은색이다.(NIL : Null Leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
- 빨간색 노드의 자식은 검은색이다. = 빨간색 노드가 연속으로 나올 수 없다.
- 모든 리프노드에서 Black Depth는 같다. = 리프노드에서 루트노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.
- Java의 HashMap 사이즈가 64가 넘을 때에 레드 블랙트리를 사용하고 TreeMap 또한 레드 블랙트리를 사용
레드-블랙 트리 삽입 과정
- 새로운 노드는 항상 빨간색으로 삽입한다. = 빨간색 노드가 연속으로 2번 나타날 수 있다.
- 삼촌 노드가 검은색이라면 -> Restructuring
- N, P, G를 오름차순으로 정렬한다.
- 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
- 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.
- 삼촌 노드가 빨간색이라면 -> Recoloring
- N의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 G를 빨간색으로 바꾼다.
- -1. G가 루트 노드라면 검은색으로 바꾼다.
- -1. G을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행 반복한다.
- N의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 G를 빨간색으로 바꾼다.
-
Q. 레드-블랙 트리에 순서대로 8, 7, 9, 3, 6, 4, 5, 12를 삽입한 후의 상태를 그리시오.
8(검)
6(빨) 9(검)
4(검) 7(검) 12(빨)
3(빨) 5(빨)
AVL Tree
- 이진 탐색 트리의 속성을 가진다.
- 왼쪽 오른쪽 서브 트리의 높이 차이가 최대 1이다.
- 높이 차이가 1보다 커지면 회전(Rotation)을 통해 균형을 맞춰 높이 차이를 줄인다.
- 삽입, 검색, 삭제의 시간복잡도가 O(log N)이다.
- BF(Balance Factor)
- BF(K) : K의 왼쪽 서브트리 높이 - K의 오른쪽 서브트리 높이
- AVL Tree는 모든 노드의 BF가 -1, 0, 1 중 하나여야 한다. 이를 벗어나면 균형이 깨졌다는 것을 의미하고 회전 필요.
- 우회전
- y노드의 오른쪽 자식 노드를 z노드로 변경한다.
- z노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.
- 좌회전
- y노드의 왼쪽 자식 노드를 z노드로 변경한다.
- z노드 오른쪽 자식 노드를 y노드의 왼쪽 서브트리(T2)로 변경한다.
- LL(Left Left) Case
- BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 왼쪽 노드가 존재.
- 해당 노드를 기준으로 우회전 적용하면 불균형 해소
- RR(Right Right) Case
- BF가 -1~1을 벗어난 노드를 기준으로 오른쪽, 오른쪽 노드가 존재.
- 해당 노드를 기준으로 좌회전 적용하면 불균형 해소
- LR(Left Right) Case
- BF가 -1~1을 벗어난 노드를 기준으로 왼쪽, 오른쪽 노드가 존재.
- 먼저 BF에 이상이 있는 노드의 왼쪽 자식노드를 기준으로 좌회전 진행
- BF에 이상이 있는 노드를 기준으로 우회전 진행하면 불균형 해소
- RL(Right Left) Case
- BF가 -1~1을 벗어난 노드를 기준으로 오른쪽, 왼쪽 노드가 존재.
- 먼저 BF에 이상이 있는 노드의 오른쪽 자식노드를 기준으로 우회전 진행
- BF에 이상이 있는 노드를 기준으로 좌회전 진행하면 불균형 해소
QA.
- 레드블랙트리의 기본적인 특성과 규칙
- 레드블랙트리에 노드를 삽입, 삭제하는 과정
- 레드블랙트리와 AVL 트리의 주요 차이점
- 균형 유지 방식 : AVL 트리는 노드의 높이 정보를 사용하여 균형을 유지한다. 각 노드에 대해, 그 노드의 왼쪽 자식과 오른쪽 자식의 높이 차이가 최대 1이 되도록 균형을 유지한다. 반면 레드블랙트리는 노드의 색깔과 특정 규칙을 사용하여 균형을 유지한다. 이러한 규칙은 트리의 깊이가 일정한 범위 내에서 유지되도록 보장한다.
- 회전 연산 : AVL 트리는 높이 차이를 유지하기 위해 더 많은 회전이 필요할 수 있다. 삽입이나 삭제 후에 최대 두 번의 회전으로 균형을 잡을 수 있는 레드-블랙 트리와 달리, AVL 트리는 경우에 따라 더 많은 회전을 수행해야 할 수 있다.
- 작업의 효율성 : AVL 트리는 검색 작업에 있어 레드-블랙 트리보다 약간 더 효율적일 수 있다. AVL 트리가 더 엄격하게 균형을 유지하기 때문이다. 그러나 삽입과 삭제 작업에서는 레드블랙 트리가 더 효율적일 수 있다. 균형을 유지하는 데 필요한 회전 수가 일반적으로 더 적기 때문.
- 메모리 사용량 : AVL 트리는 각 노드에 대한 높이 정보를 저장해야 하므로, 레드블랙트리에 비해 약간 더 많은 메모리를 사용할 수 있다. 레드블랙트리는 각 노드에 대해 색상 정보만 저장하면 되므로, 추가적인 메모리 사용량이 더 적다.
- 레드블랙트리, AVL트리 각각 시간복잡도
레드블랙트리는 정렬이 되나?
안되다면 트리맵에서는 왜 쓰는거고
트리맵은 어떻게 정렬이 되는거지?
Comparator vs Comparable
참고 :