[자료구조] AVL 트리, Red-Black 트리

AVL 트리

AVL트리는 발명가 Adelson-Velsky, Landis 이름 앞글자에서 따온 균형이진탐색트리이다. 스스로 균형을 잡는 트리로 처음 고안됐으며 말단 노드의 레벨 차이가 항상 1이하로 나는 트리이다. 노드 삽입, 삭제 시 균형이 깨진다면 스스로 조절하기 때문에 높이는 항상 logN이 보장된다.

 

 

Red-Black 트리

아래 다섯 조건을 만족하는 트리를 레드블랙트리라고 한다. 마찬가지로 균형이진탐색트리이므로 높이는 logN이다.

• 모든 노드는 Red / Black 의 색을 가져야 한다.
• 루트 노드는 항상 블랙이다.
• NIL 노드는 항상 블랙이다. (value가 없는 말단 노드를 항상 가진다. NIL == Null Leaf)
• 레드 노드의 자식 노드는 항상 블랙이다. (블랙 노드는 상관 없다)
• 각 노드에서 말단 노드로 가는 블랙 노드의 수는 항상 같아야 한다.
  → 이게 무슨 의미냐
  이 속성을 만족하는 서브트리있고, 자식 노드가 같은 색이라면, 부모 노드와 자식 노드의 색이 바뀌어도 속성을 계속 만족한다는 뜻

 

삽입 연산
1. BST의 insert 방식으로 원소 x를 삽입한다.

2. 처음 x의 color를 레드로 지정한다.

3. 4가지 경우로 나눠 조정한다.

• x가 루트일 때
  1. x의 색을 블랙으로 바꾼다.
• x의 부모 노드가 블랙일 때
  do nothing
• x의 부모 노드가 레드일 때
  •  부모의 형제 노드(삼촌 노드)가 레드일 때
  • 삼촌 노드가 블랙일 때
    • 조부모-부모-x 노드가 linear 일 때
      회전 한 번
    • 조부모-부모-x 노드가 triangle 일 때
      회전 두 번

(위) linear (아래) triangle

오.. 모르겠어...

 

 

결론

AVL 트리보다 Red-Black 트리가 효율성이 더 좋다. 레드 블랙 트리는 최대 3회 회전만으로 연산을 수행할 수 있다. 

단점. 구현이 복잡하다.

 

 

 

https://www.youtube.com/watch?v=eAUbCgJBtcQ&ab_channel=Chan-SuShin