추가. Red-black 트리 (레드블랙트리)

2025. 2. 7. 21:36·SW개발/면접을 위한 CS 전공지식 노트
목차
  1. 개요
  2. 삽입 과정
  3. Restructuring (재구축)
  4. Recoloring (재색칠)
  5. 예제 삽입 수행
  6. 레드-블랙 트리 시뮬레이터
반응형

레드-블랙 트리

개요

자가 균형 이진 탐색 트리. 다음과 같은 조건을 만족.

  1. 모든 노드는 빨간색 혹은 검은색.
  2. 루트 노드는 검은색.
  3. 모든 리프 노드(NIL)는 검은색.
  4. 빨간색 노드의 자식은 검은색. (No Double Red)
  5. 모든 리프 노드에서 Black Depth는 같음.

삽입 과정

  1. 새로운 노드는 항상 빨간색으로 삽입.
  2. 삽입 후 Double Red 문제 발생 가능.
  3. 해결 방법:
    • 삼촌 노드가 검은색: Restructuring 수행.
    • 삼촌 노드가 빨간색: Recoloring 수행.

Restructuring (재구축)

  1. 새로운 노드(N), 부모 노드(P), 조상 노드(G)를 오름차순으로 정렬.
  2. 중간값을 부모 노드로 설정, 나머지 둘을 자식 노드로 변경.
  3. 새 부모 노드를 검은색으로, 자식들을 빨간색으로 변경.

예제

초기 상태:        재구축 후:
    G (검)           P (검)
   / \              /   \
  P  U(검)        N(빨) G(빨)
 /
N(빨)

Recoloring (재색칠)

  1. 부모(P)와 삼촌(U)을 검은색으로 변경.
  2. 조상(G)을 빨간색으로 변경.
  3. 조상이 루트라면 검은색으로 유지.
  4. 조상이 Double Red를 유발하면 다시 Restructuring 또는 Recoloring 수행.

예제

초기 상태:        재색칠 후:
    G (검)          G (빨)
   / \            /   \
  P(빨) U(빨)    P(검) U(검)
 /
N(빨)

예제 삽입 수행

삽입 순서: 8, 7, 9, 3, 6, 4, 5, 12

초기 상태:       최종 상태:
      8(검)          6(검)
     /   \         /     \
   4(빨)  9(검)  3(검)   8(검)
  /   \         /   \      \
 3(검) 6(검)   NIL 5(빨)  12(검)
        /
      5(빨)

레드-블랙 트리 시뮬레이터

레드-블랙 트리의 삽입 과정을 시각적으로 확인 가능.

🔗 레드-블랙 트리 시뮬레이터

반응형
저작자표시 비영리 변경금지 (새창열림)

'SW개발 > 면접을 위한 CS 전공지식 노트' 카테고리의 다른 글

5.3 비선형 자료 구조 (Non-Linear Data Structures)  (1) 2025.02.05
5.2 선형 자료 구조 (Linear Data Structures)  (0) 2025.02.05
5.1 복잡도  (1) 2025.02.05
참고. 데이터베이스 관련 면접 질문 리스트  (0) 2025.01.24
4.7 조인의 원리  (1) 2025.01.22
  1. 개요
  2. 삽입 과정
  3. Restructuring (재구축)
  4. Recoloring (재색칠)
  5. 예제 삽입 수행
  6. 레드-블랙 트리 시뮬레이터
'SW개발/면접을 위한 CS 전공지식 노트' 카테고리의 다른 글
  • 5.3 비선형 자료 구조 (Non-Linear Data Structures)
  • 5.2 선형 자료 구조 (Linear Data Structures)
  • 5.1 복잡도
  • 참고. 데이터베이스 관련 면접 질문 리스트
코코도롱
코코도롱
    반응형
  • 코코도롱
    도롱이의 전자공학소
    코코도롱
  • 전체
    오늘
    어제
    • 분류 전체보기 (60)
      • AI (16)
        • 데이터 분석과 모델 학습 (4)
        • 모델별 정리 (7)
        • (PJT)음성 화자 분류 (4)
      • SW개발 (38)
        • C++ (9)
        • 면접을 위한 CS 전공지식 노트 (24)
        • Django+Vue.js (0)
        • 이런저런 개발이야기 (1)
        • 갑자기 C코테를 봐야할때 (2)
        • RPI5 프로젝트 (1)
        • 트러블슈팅 (1)
      • ESG (2)
        • 내가 쓰는 Assay (1)
        • 뉴스 스크랩 (1)
      • 반도체 (4)
        • 반도체 (3)
        • 슬기로운 학부생활 (1)
        • 회로 (0)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    요약본
    MySQL
    페이징 기법
    CS지식
    word 수식
    메시지큐
    면접을 위한 CS 전공지식 노트
    입출력관리
    데이터분석 #머신러닝 #딥러닝 #데이터사이언스 #알고리즘 #데이터전처리
    파일입출력 #DataFrame불러오기
    공백포함입력받기
    데이터분석 #데이터전처리 #결측치 #머신러닝 #딥러닝 #Pandas #DataFrame
    반도체 물성
    홉바이홉통신
    멀티프로세스
    면접을 위한 cs전공지식 노트
    ios7계층
    보고서 수식
    os구조
    운영체제
    c io
    데이터전처리 #데이터분석 #딥러닝 #머신러닝 #Pandas #Numpy #Python
    전공 지식
    ESG
    홉바이홉
    LAN
    반도체 소자 공학
    정리본
    반도체 공학
    c언어 입출력
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
코코도롱
추가. Red-black 트리 (레드블랙트리)
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.