Data Structure

Red-BlackTree, AVL Tree

후후후하하하 2024. 4. 24. 16:52

레드-블랙 트리

  • 자가 균형 이진 트리.
  • 모든 노드는 빨간색 또는 검은색이다.
  • 루트 노트든 검은색이다.
  • 모든 리프노드들은 검은색이다.(NIL : Null Leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드)
  • 빨간색 노드의 자식은 검은색이다. = 빨간색 노드가 연속으로 나올 수 없다.
  • 모든 리프노드에서 Black Depth는 같다. = 리프노드에서 루트노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다.
  • Java의 HashMap 사이즈가 64가 넘을 때에 레드 블랙트리를 사용하고 TreeMap 또한 레드 블랙트리를 사용

레드-블랙 트리 삽입 과정

  1. 새로운 노드는 항상 빨간색으로 삽입한다. = 빨간색 노드가 연속으로 2번 나타날 수 있다.
  2. 삼촌 노드가 검은색이라면 -> Restructuring
    1. N, P, G를 오름차순으로 정렬한다.
    2. 셋 중 중간값을 부모로 만들고 나머지 둘을 자식으로 만든다.
    3. 새로 부모가 된 노드를 검은색으로 만들고 나머지 자식들을 빨간색으로 만든다.
  3. 삼촌 노드가 빨간색이라면 -> Recoloring
    1. N의 부모(P)와 삼촌(U)을 검은색으로 바꾸고 G를 빨간색으로 바꾼다.
      1. -1. G가 루트 노드라면 검은색으로 바꾼다.
      2. -1. G을 빨간색으로 바꿨을 때 또다시 Double Red가 발생한다면 또다시 Restructuring 혹은 Recoloring을 진행 반복한다.
  4. 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 중 하나여야 한다. 이를 벗어나면 균형이 깨졌다는 것을 의미하고 회전 필요.
  • 우회전
    1. y노드의 오른쪽 자식 노드를 z노드로 변경한다.
    2. z노드 왼쪽 자식 노드를 y노드의 오른쪽 서브트리(T2)로 변경한다.
  • 좌회전
    1. y노드의 왼쪽 자식 노드를 z노드로 변경한다.
    2. 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.

  1. 레드블랙트리의 기본적인 특성과 규칙
  2. 레드블랙트리에 노드를 삽입, 삭제하는 과정
  3. 레드블랙트리와 AVL 트리의 주요 차이점
    1. 균형 유지 방식 : AVL 트리는 노드의 높이 정보를 사용하여 균형을 유지한다. 각 노드에 대해, 그 노드의 왼쪽 자식과 오른쪽 자식의 높이 차이가 최대 1이 되도록 균형을 유지한다. 반면 레드블랙트리는 노드의 색깔과 특정 규칙을 사용하여 균형을 유지한다. 이러한 규칙은 트리의 깊이가 일정한 범위 내에서 유지되도록 보장한다.
    2. 회전 연산 : AVL 트리는 높이 차이를 유지하기 위해 더 많은 회전이 필요할 수 있다. 삽입이나 삭제 후에 최대  두 번의 회전으로 균형을 잡을 수 있는 레드-블랙 트리와 달리, AVL 트리는 경우에 따라 더 많은 회전을 수행해야 할 수 있다.
    3. 작업의 효율성 : AVL 트리는 검색 작업에 있어 레드-블랙 트리보다 약간 더 효율적일 수 있다. AVL 트리가 더 엄격하게 균형을 유지하기 때문이다. 그러나 삽입과 삭제 작업에서는 레드블랙 트리가 더 효율적일 수 있다. 균형을 유지하는 데 필요한 회전 수가 일반적으로 더 적기 때문.
    4. 메모리 사용량 : AVL 트리는 각 노드에 대한 높이 정보를 저장해야 하므로, 레드블랙트리에 비해 약간 더 많은 메모리를 사용할 수 있다. 레드블랙트리는 각 노드에 대해 색상 정보만 저장하면 되므로, 추가적인 메모리 사용량이 더 적다.
  4. 레드블랙트리, AVL트리 각각 시간복잡도

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

레드블랙트리는 정렬이 되나?

안되다면 트리맵에서는 왜 쓰는거고 

트리맵은 어떻게 정렬이 되는거지?

 

Comparator vs Comparable

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고 : 

https://code-lab1.tistory.com/61

https://code-lab1.tistory.com/61