최블랙의 개발로그 최블랙의 개발로그

RB Tree

• [Data Structure] Red-Black Tree

  CS/Data Structure 2021. 10. 8. 08:00

  Red-Black Tree Red-Black Tree는 이진 탐색 트리(Binary Search Tree)기반 트리 형식의 자료구조이다. 이진 탐색 트리는 저장, 삭제, 탐색 시 O(logN)의 시간 복잡도를 갖지만, 한 쪽으로 편향될 경우(최악의 경우) 시간 복잡도가 O(N)이 될 수 있다. 👉 이러한 단점을 보완하기 위해 스스로 높이 균형을 유지하는 Red-Black Tree가 고안됨. 특징 탐색, 삽입, 삭제에 대해 Binary Search Tree의 특성을 사용한다. 각 노드는 Red or Black 색상이 할당된다. Rotation과 Recoloring을 통해 균형을 유지한다. 탐색, 삽입, 삭제 시 O(logn)의 시간복잡도를 가진다. 삽입, 삭제 시 Red-Black Tree의 5가지 조건을..

  Read More