균형 잡힌 이진 검색 트리 개요

  균형 잡힌 이진 검색 트리 개요 

이진 검색 트리의 문제점

이진 검색 트리의 경우 저장과 검색에 평균 Θ(logn) 시간이 소요되지만 운이 좋지 않아 트리의 균형이 깨지게 된 경우엔 Θ(n)에 가까운 시간이 소요되게 된다.

이러한 문제를 극복하기 위해 이진 검색 트리를 구성할 때 균형을 유지할 수 있도록 해야 하며 대표적으로 레드 블랙 트리와 AVL 트리가 존재한다.

 

이진 검색 트리의 균형 유지를 위한 각 트리의 특성은 다음과 같다.

• AVL 트리 높이 균형 성질을 만족한다.
  • 높이 균형 성질 트리 내부의 모든 노드는 자식과의 높이 차이가 1 이하가 되어야 한다.
• 레드 블랙 트리 노드에 색상 정보를 추가하여 다음의 특성이 만족되도록 해야 한다.
  • 루트는 블랙이다.
  • 모든 리프(NIL)는 블랙이다.
  • 노드가 레드이면 그 노드의 자식은 반드시 블랙이다.
  • 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.

 

※ 리프 노드는 NIL이라는 이름의 존재하는 노드로 색상을 블랙으로 표현하여 일관된 알고리즘을 적용할 수 있게 한다.
※ NIL 노드는 하나만 생성한 뒤 리프 노드를 가리킬 때 포인터로 이 NIL노드를 가리키는 것으로 메모리를 절약할 수 있다.

 

NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소 (github.com)

GitHub - NadanKim/Algorithm: 알고리즘 학습 및 예제 코드 작성을 위한 저장소

 

참고문헌

한빛아카데미.문병로.(2016.07.24).쉽게 배우는 알고리즘

위키백과.AVL 트리