AVL 트리(Adelson-Velsky and Landis tree)
- BST 트리의 경우 최악의 경우 O(n)의 시간 복잡도를 보이는데 이것을 방지하고자 스스로 균형을 잡는 이진 탐색 트리
- 두 자식 서브 트리의 높이는 항상 최대 1만큼 차이 난다.
- 레드 블랙트리와 비슷하나 BF(balance Factor)를 통해 균형을 잡는다.
레드-블랙 트리(red-black tree)
- 각 노드가 레드 혹은 블랙(노드에 저장하는 데이터 X)
- 그냥 1비트 짜리 정보
- 스스로 균형을 잡는(self-balancing) 트리
- 최소한의 트리 높이를 보장
- 균형을 잡는 시점-> 삽입, 삭제
- 그 외 연산은 BST와 동일( 탐색 속도는 더 빠르다)
- C++ STL의 set, multiset, map, and multimap 이 이 레드 블랙 트리를 이용하여 구현
레드-블랙 트리(red-black tree)의 특성
- 모든 노드는 레드 혹은 블랙이다(Nil 노드 포함)
- 루트 노드는 언제나 블랙
- 모든 리프 노드(Nil)는 블랙이다. 즉 Nil 노드가 리프노드임.
- 레드 노드의 자식은 모두 블랙이다
- 어떤 노드와 리프 사이에 있는 블랙 노드 수는 동일하다(중요).
- 이를 통해 블랙과 레드 노드의 수의 균형 맞음
- 리프 노드는 데이터를 담지 않음(Nil)
- 블랙 깊이(black depth): 루트와 어떤 노드 사이에 있는 블랙 노드 수
- 블랙 높이(black height): 어떤 노드와 리프 사이에 있는 블랙 수
- 가장 큰 리프 깊이가 가장 작은 것의 2배를 넘지 않는다.
- 트리가 한쪽으로 쏠리는 것을 방지 -> O(logn) 보장
레드-블랙 트리(red-black tree)의 연산
탐색
삽입&삭제
- 무작정 삽입하거나 삭제 ->특성이 망가짐
- 망가진 특성을 고치려 트리 구조 재배치(회전) 혹은 노드 색 변환
- 삽입 삭제 O(logn) 고정
