[Data Structure] Red Black Tree

Red Black Tree

RBT는 이진 탐색 트리를 기반으로 하는 트리 형식의 자료구조이다. 

 

시간복잡도

• Search : O(log n)
• Insert : O(log n)
• Delete : O(log n)

동일한 노드의 개수일 때 depth를 최소화하여 시간 복잡도를 줄인다. 동일한 노드의 개수일 때 depth가 최소가 되는 경우는 tree가 완전 이진 트리인 경우이다.

 

정의

Red-Black Tree는 다음의 성질을 만족하는 이진 탐색 트리이다.

• 각 노드는 Red 또는 Black이라는 색을 가진다.
• Root는 Black이다.
• 각 leaf는 Black이다.
• 어떤 노드가 red라면 두 개의 자식은 모두 black이다.
• 각 노드에 대해서 해당 노드를 루트로 보는 서브 트리가 있을 때, 서브트리의 루트에서 각 리프까지가는 모든 경로의 black의 개수가 같다. 이때 black의 개수를 Black-Height라고한다.

 

특징

• BST의 모든 특징을 갖는다.
• 루트에서 리프까지는 모든 경로에 대해서 최대 경로와 최소 경로의 크기 비율은 2보다 크지않다. -> balanced
• 노드의 자식이 없을 때 자식을 가리키는 포인터 NIL값을 저장한다. 즉 NIL이 리프이다.
• RBT는 BST의 삽입, 삭제 과정에서 발생하는 문제점을 해결하기 위해 만들어진 자료구조이다.

 

삽입

• 삽입된 노드는 항상 Red이다. 단 루트는 Black이다.
• 기본적으로 BST의 삽입법을 따르되 규칙에 어긋나면 조정한다. 조정 방법은 크게 2가지이다.
  • 회전 : 부모 노드가 Red인데 부모의 형제가 없거나 Black일 때
  • 색상 변환 : 부모 노드가 Red인데 부모의 형제가 Red일 때
• 회전과 색상 변환을 통해 height를 관리한다. 

 

삭제

• 기본적으로 BST의 삭제법을 따른다.
• 삭제되는 노드의 자식 수에 따라 방법이 다르다.
  • 삭제 노드가 Black이라면 Black-Height가 1 감소한 경로에 노드가 추가되도록 회전하고 색상 변환을 한다.
  • 삭제 노드가 Red라면 그대로 유지한다.

 

자바 컬렉션의 ArrayList도 내부적으로 RBT로 이루어져있다.