6~8주차 - 이진 검색 트리 및 레드 블랙트리

이진 검색 트리

관련 용어

• 레코드
  • 개체에 대한 모든 정보를 포함하고 있는 저장 단위
    • 예시) 사람의 레코드: 주민번호, 이름, 주소, 휴대폰 번호….
• 필드
  • 레코드에서 각각의 정보를 나타내는 부분
• 검색키(키)
  • 다른 레코드와 중복되지않는 각 레코드를 대표하는 필드
  • 2개 이상의 필드로도 이루어 질 수 있음
• 검색 트리
  • 각 노드가 규칙에 맞게 하나씩 키를 가지고 있는것
  • 이 키를 통해서 레코드가 저장된 위치를 알 수 있음

특징

• 이진검색트리의 각 노드는 키 값을 전부 가지고 있고, 각 노드의 키 값은 달라야 함

• 최상위 레벨에 루트 노드가 있고, 각 노드는 최대 2개의 자식 노드를 보유 가능함

• 각 노드는 왼쪽 자식 노드의 키 값보다 크고, 오른쪽 자식 노드의 키 값보다 작음

• 시간 복잡도는 트리의 높이에 의해 결정됨

  ​ \(O(height)\)의 시간 복잡도를 가짐

  수식으로 계산하는 경우 \(n = 2^{h+1}-1\)임

사용되는 목적

• 계층적인 관계의 표시
• 가계도, OS의 파일 시스템….

삽입

• 선택된 해당 트리의 루트 노드가 존재하지 않을 경우, 해당 루트의 위치에 키를 삽입 후, 해당 루트의 왼쪽 자식노드와 오른쪽 자식 노드를 NIL로 설정해 준다
• 선택된 해당 트리의 루트 노드가 존재하는 경우, 해당 노드의 키와 삽입할 키의 크기를 비교하여, 작은 경우 왼쪽 자식 노드에 삽입하며, 큰 경우 오른쪽 자식 노드에 삽입함

삭제

• 삭제는 3가지 경우에 따라서 처리함

• 처리의 경우

  1. 삭제하려는 노드가 리프 노드인 경우
  2. 삭제하려는 노드의 자식 노드가 1개인 경우
  3. 삭제하려는 노드의 자식 노드가 2개인 경우

삭제하려는 노드가 리프 노드일 경우

• 그냥 노드를 삭제함

노드의 자식 노드가 1개인 경우

• 삭제하려는 노드 r의 부모 노드와 자식 노드를 연결해 준다

노드의 자식 노드가 2개인 경우

• 삭제하려는 노드 r의 오른쪽 서브트리의 최소원소 노드 s를 삭제 및, r자리에 s를 놓는다

레드 블랙 트리

• 이진 검색 트리의 모든 트리에 블랙이나 레드의 색을 칠하는 것

  • 단, 다음의 레드 블랙 특성을 만족해야 함

    1. 루트는 블랙이여야 함
    2. 모든 리프는 블랙이여야 함
    3. 노드가 레드이면 그 노드의 자식은 반드시 블랙이다
    4. 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 동일함

레드블랙트리에서의 삽입

• 새로운 노드를 삽입할 때는 항상 빨간색으로 삽입함
  • 새 노드를 삽입했을 때, 부모 노드의 색 블랙이라면 문제가 없지만 레드라면 레드블랙 트리의 특성 3이 깨진다