RedBlack Tree

• 모든 노드는 RED or BLACK
• root 와 leaf(NIL)은 BLACK
• 노드가 RED이면 자식은 모두 BLACK (No Double Red)
• 각 노드로부터 그 노드의 자손인 리프로 가는 경로들은 모두 같은 수의 BLACK 노드를 포함
• NIL을 하나의 객체로 고나리하면 하나의 노드로 관리하기에 메모리 절야 까능

삽입 시 연속된 RED 해결

• Recoloring:  삽입된 노드의 부모의 형제 색깔이 RED
• Restructing : 삽입된 노드의 부모의 형제 색깔이 BLACK인 경우,  NULL인 경우

삭제 시

• RED는 그냥 삭제
• BLACK의 경우 삭제 연산으로 트리 속성을 깨지 않도록

복잡도

• Space : O(n)
• 삽입, 삭제, 검색 : O(logn)

AVL vs RB

• 검색 : AVL > RB (AVL가 더 엄격)
• 삽입, 삭제 : AVL < RB (RB가 더 느슨함)
• 공간 : AVL < RB (색깔 저장을 위해)
• 사용
  • AVL : DB (조회속도가 빠른)
  • RB : map, multimap, multiset

References

https://nesoy.github.io/articles/2018-08/Algorithm-RedblackTree

RedBlack Tree에 대해