목록Predecessor (1)

미새문지

크래프톤 정글 week04, day27 - RB트리 개념

레드-블랙 트리(Red-Black Tree) 자가 균형 이진 탐색 트리(Self Balance Binary Search Tree) RB트리를 만족하기 위한 조건 모든 노드는 빨간색 혹은 검은색이다. 루트 노드는 검은색이다. 모든 리프 노드(NIL)들은 검은색이다. (NIL : null leaf, 자료를 갖지 않고 트리의 끝을 나타내는 노드) 빨간색 노드의 자식은 검은색이다. 빨간색 노드가 연속으로 나올 수 없다. 모든 리프 노드에서 Black Depth는 같다 리프 노드에서 루트 노드까지 가는 경로에서 만나는 검은색 노드의 개수가 같다. 조건 5번 속성을 만족해야 성립하는 개념 노드 x의 black height 노드 x에서 임의의 자손 nil 노드까지 내려가는 경로에서의 black 수(자기 자신은 카운트..
크래프톤 정글/TIL 2024. 2. 20. 12:54
이전 Prev 1 Next 다음