본 글은 신찬수 교수님의 자료구조 강의를 듣고 참조하여 작성하였다.
레드블랙트리
- 레드-블랙 트리(Red-black tree)는 자가 균형 이진 탐색 트리(self-balancing binary search tree)로서, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조이다. (https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC)
- v의 서브트리의 내부 노드 개수 >= 2^bh(v)-1
( bh(v): v부터 리프 노드까지 v 제외 한 블랙노드의 개수)
- black 노드 수 >=h/2
- h=O(lgn)
레드블랙트리의 특성
- 노드는 블랙 또는 레드색이다.
- 루트 노드는 블랙이다.
- 모든 리프(NIL) 노드는 블랙이다.
- 노드가 레드이면 그 노드의 자식은 반드시 블랙이다. (No Double Red)
- 루트 노드에서 임의의 리프 노드에 이르는 경로에서 만나는 블랙 노드의 수는 모두 같다.
레드블랙트리의 삽입(insert)
- 기본적으로 신규 생성 노드의 색은 레드
- 신규노드가 삽입되고 나서 parent가 black인 경우는 상관 X
- but double red일 때는 문제 발생. 해결방안은 2가지이다.
- 부모 노드가 레드, uncle이 블랙 -> Restructring
(1) 3 12 5 노드들 오름차순 정렬
(2) 가운데 있는 값은 부모, 나머지는 자식노드
(3) 부모 값을 black, 두 자식을 red로 만든다.
- 부모 노드 레드, uncle이 red-> Recoloring (부모노드의 컬러를 블랙, 조부모의 칼라를 레드로. but 조부모가 루트노드면 다시 블랙으로 칠해줘야 함.)
(출처: https://m.blog.naver.com/min-program/221231697752)
공부방