AVL 트리와 Red Black 트리란?

[bugoverdose]

AVL 트리

• 이진 탐색 트리 & 균형 이진 트리

• 삽입 순서에 따라 선형적인 트리로 구성될 수 있다는 문제점을 해결하기 위해 스스로 균형을 잡는 이진트리

  • balance factor를 통해 좌우 서브트리의 균형을 잡음
  • 삽입/삭제 작업을 수행할 때마다 매번 트리 균형을 확인하고, 트리 구조를 재조정함.

• Adelson-Velsky and Landis tree

• 파이썬 dictionary에서 사용.

노드의 balance factor

balance factor: 특정 노드(x)의 좌우 서브트리의 높이 차이

BF(x) = h(lSubtree(x)) - h(rSubtree(x))

핵심 특징

• AVL 트리의 모든 노드의 balance factor는 {-1, 0, 1}을 값으로 지님.

  • 즉, 항상 두 자식 서브트리의 높이 차이를 1 이하로 유지 => 항상 균형 잡힌(balanced) 트리로 만드는 것이 목적.
  • 루트노드도 포함. 루트노드 기준으로 좌우 서브트리의 높이까지 1이하로 지속적으로 유지.

• 탐색/삽입/삭제의 성능은 worst case, 평균 시간복잡도 모두 O(log n)

AVL 트리의 균형 잡기

1. 삽입 혹은 삭제 작업을 수행한 직후, 삽입/삭제가 발생한 위치에서 루트노드로 거꾸로 올라오면서 BF 값을 계산.
2. 만일 BF 값이 {-1, 0, 1}이 아닌 노드가 생겨났다면 균형을 맞추는 재조정 작업을 수행

트리 일부를 왼쪽/오른쪽으로 회전(rotate)시킴으로써 높이차 재조정

• 유튜브 - AVL 균형 잡는 세부 과정

장점

최악의 경우에도 삽입/삭제/검색의 시간복잡도는 O(log N)이 된다!

• 선형적인 트리가 되지 않으므로 최악의 상황이어도 O(n)이 되지 않음.

균형을 엄격하게 잡기 때문에 검색 성능은 RB 트리에 비해 미세하게 더 빠르다

• 한번 만들어놓으면 삽입/삭제가 거의 없고 검색 작업이 대부분인 상황에 유리

단점

• RB 트리에 비해 삽입/삭제 성능이 느리다.
• 트리의 균형을 엄격하게 유지하기 때문에 트리 구조 재조정 작업에서 시간이 많이 소요됨.
• 그렇기 때문에 red black 트리를 활용함.

---

레드 블랙 트리 (RB 트리)

• 자가 균형 이진 탐색 트리
• 변질 이진 트리, 즉 편향된 구조가 되지 않도록 스스로 균형을 조정.
  • 각 노드에 red 혹은 black이라는 색상을 나타내는 추가 비트를 저장하여, 삽입/삭제 중에 트리의 균형을 유지하는데 활용.
• map, set 내부 구현에 활용. Java TreeMap, TreeSet, HashMap 내부 등.

구조

• 균형 이진 트리(balanced)이므로 왼쪽-오른쪽 노드의 높이 차이가 1이하.

핵심 성질

1. 모든 노드는 red 혹은 black
2. 루트노드는 black
3. 모든 nil 노드(리프노드)는 black
4. red의 자녀들은 black. 즉, red는 연속적으로 존재 불가
5. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 개수는 같다. (자기 자신은 카운트에서 제외) => 이 동일한 개수가 노드의 black height
   • 실질적으로 균형을 맞추는 원칙
   • 5번 성질을 충족하고 있을 때, 두 자녀가 같은 색을 지니고 있다면 부모와 자녀의 색을 바꿔줘도 5번 성질은 여전히 충족된다.

nil 노드

• 데이터가 없지만 값이 있는 노드와 동등하게 취급되는 더미 노드 (일종의 null 객체 패턴)
• 자녀가 존재하지 않는 위치는 nil 노드로 표기
• RB 트리의 모든 leaf 노드는 nil 노드

삭제 후 대체된 위치에 nil 노드가 오는 경우, extra black을 배정하여 doubly black으로 만들어 재조정 작업을 거치기 위함.

노드의 black height

노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black의 개수

---

균형 재조정 원리

삽입/삭제시, RB 트리 위배 여부를 확인하고, RB 트리의 속성을 위반한 경우, 재조정 과정 진행.

구체적으로는 4번 성질 & 5번 성질에 위배되는 구조를 해결하기 위해 개별 노드의 색상 및 전체적인 구조를 변경하는 과정에서 트리의 균형을 어느 정도 잡을 수 있음.

• 4번 성질. red의 자녀들은 black. 즉, red는 연속적으로 존재 불가
  • ex) 삽입시, red 및에 red가 새롭게 추가됨.
• 5번 성질. 임의의 노드에서 자손 nil 노드들까지 가는 경로들의 black 개수는 같다. (자기 자신은 카운트에서 제외)

삽입 과정

핵심: 새롭게 삽입되는 노드는 언제나 red

• 항상 red 노드를 삽입하는 이유는, 삽입 이후에도 5번 성질을 만족하기 위함.
• 즉, nil 노드(black) 위치에 red를 삽입하고, red가 nil 노드(black)을 자식으로 지니게 되면, black height 유지 가능.

삽입 후 재조정

삽입 후 red가 연속되어 4번 성질에 위배되더라도 무조건 좌우 균형이 깨진 것은 아님.

색상 변경만이 아니라, AVL 트리처럼 문제가 생긴 부분을 순차적으로 회전시켜서 해결.

부분적/전체적으로 회전시키는 과정에서 트리의 전체적인 depth, level을 줄여나갈 수 있음.

1. BST 특징(대소 관계)도 유지하면서 균형을 재조정하기 위해 회전시킴.
2. red와 black 색상을 적절하게 조정하여 RB 트리의 성질 충족시킴.

삭제 과정

삭제 전 RB 트리 조건 충족하는 상태에서, 일반적인 BST 방식으로 삭제 후, RB 트리 위배 여부를 확인하여 재조정 과정 거침.

삭제 후 RB 트리 성질 위반 여부 확인

핵심: 실질적으로 삭제되는 색이 무엇인가에 따라 RB 트리의 성질 위배 여부 확인 가능.

• 삭제하려는 노드의 자녀가 없거나 하나인 경우, 삭제되는 노드의 색
• 삭제하려는 노드의 자녀가 두 개인 경우, 삭제되는 노드의 후임자(successor)의 색, 즉 삭제하려는 노드 다음으로 큰 노드.
  • 후임자가 삭제되는 위치와 색상을 대체하게 되므로, 사실상 후임자의 기존 색상이 없어지는 것.

1. 삭제되는 색이 red라면 RB 트리의 조건에 위배되지 않음. (사라진 자리에 후임자가 대체되든, 부모와 자식 모두 black이든) red는 여전히 연속되지 않으며, black height는 불변.

2. 삭제되는 색이 black인 경우 RB 트리 조건에 위배될 수도 있음. 즉, 루트노드(black)가 삭제되었거나, 특정 서브트리의 black height가 변경되거나, red끼리 연속될 수 있음.

삭제 후 재조정

2번 성질 위배시 재조정: 루트 노드가 삭제된 경우, 새로운 루트노드의 색상만 black으로 수정해주기만 하면 됨.

5번 성질 위배시 재조정: 삭제된 색의 위치를 대체한 노드에 extra black을 부여하고, 이로 인해 생겨난 doubly black 혹은 red-and-black의 extra black를 제거하는 방식으로 해결

• extra black: 추가적인 black 노드로 계산되어 감소한 black height를 다시 증가시킴.
• red-and-black: extra black이 부여된 red 노드.
  • red-and-black이 생겨난 경우, red 노드에서 black 노드로 변경하여 간단히 해결 가능.
• doubly black: extra black이 부여된 black 노드
  • doubly black이 생겨난 경우, 형제의 색과, 형제의 자녀들의 색에 따라 extra black 제거 방식이 달라짐. 형제 및 자녀들의 색상 변경과 회전 작업.

시간복잡도

• 평균, worst case 모두 탐색/삽입/삭제 모두: O(log n)

장점

• AVL 트리에 비해 삽입/삭제 성능이 빠르다.
  • AVL 트리는 매번 balance factor를 계산하여 엄격하게 균형을 잡음.
  • RB 트리는 상황에 따라 재조정 작업이 덜 발생.

단점

검색 성능은 AVL 트리에 비해 약간 느리다. 균형이 덜 잡히기 때문.

[tonic523]

• AVL 트리가 뭔가요?
  • 이진 검색 트리의 일종
  • 균형을 맞추기 위해 등장했습니다.
• AVL 트리에서 삽입이 일어날 때 재조정하는 과정을 간단하게 그림으로 설명해주세요.
• 그래프가 주어졌을 때 트리인지 알 수 있나요?
• 트리의 성질
  • 계층적
  • 사이클 존재 x
  • 간선이 정점보다 1개 작다.
• 이 그래프에서 사이클이 존재하는지에 대한 코드를 작성할 수 있나요?
  • 간선으로 순회했을 때 방문 여부를 저장함에 따라 찾아보려고 한다.
• 레드 블랙 트리는 어떤게 다른건가요?
  • 노드마다 색상이 부여된다.
  • nil이라는 노드를 넣어준다.
  • 균형 이진 트리를 만든다.
• mst는 무슨 트리인가요? 최소 신장 트리
• 레드 블랙 트리의 장점
  • 삽입과 삭제를 할 때 bit를 위주로 연산할 수 있어 효율적이다.
  • 판단하는 비용이 적다.
  • AVL 트리는 빡빡하게 재조정한다.
  • AVL보다 미세하게 성능이 낮다.
• python에는 왜 레드 블랙 트리가 없을까요?
  • python에 dictionary는 avl 트리이다.