자료구조 - 이진검색트리(ALV, RED-BLACK)

Balanced Binary Search Tree

---

AVL트리란?

• 균형잡힌 이진검색 트리이다.
• 오른쪽 서브트리와 왼쪽 서브트리의 높이 차를 1까지만 허용한다.
• 1보다 큰 경우 tree modification연산을 진행해여 재배열 한다.
• 트리의 높이는 항상 logn으로 연산에 대한 시간복잡도도 O(logn)이 된다.

 

Red-Black Tree란?

• 균형잡힌 이진검색 트리이다.
• 트리의 모든 노드에 블랙 또는 레드 색을 칠하되 레드블랙 특성을 만족해야한다. 특성은 다음과 같다.
  1. 루트는 블랙이다.
  2. 모든 리프는 블랙이다.
  3. 레드 노드는 연속으로 올 수 없다.
  4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
• 여기서 리프 노드는 일반적인 의미의 리프노드와 다르다. 모든 NIL포인터가 NIL이라는 리프 노드를 가리킨다고 가정한다. 그림으로 이해하자.

• 삽입
  • 이진검색트리의 삽입 규칙에 따른다.
  • 삽입한 노드는 레드로 색칠한 후 레드블랙 트리 규칙을 만족하도록 회전을 반복한다.
• 삭제
  • 이진검색트리의 삭제 규칙에 따른다.
  • 삭제 노드가 레드 노드였다면 추가 작업이 일어나지 않는다.
  • 삭제 노드가 블랙 노드였다면 삭제 위치에 올 대체 노드를 블랙으로 색칠한다.

 

reference