센티널 노드를 사용하는 것과 사용하지 않는 것의 차이를 설명해주세요. {red black tree}

• 0012 Career 💼
• CSLR Chapter 13 Red-Black Trees
• 사용하지 않으면 단말노드를 NULL로 표시. NULL 체크를 매번 해줘야 함. 단말에 이르렀다는 것을 확인하기 위해 센티널 노드를 사용함.

---

CSLR Ch.13에서 발췌함

Why use the sentinel? The sentinel makes it possible to treat a NIL child of a node x as an ordinary node whose parent is x . An alternative design would use a distinct sentinel node for each NIL in the tree, so that the parent of each NIL is well defined. That approach needlessly wastes space, however. Instead, just the one sentinel T: nil represents all the NILs - all leaves and the root’s parent. The values of the attributes p , left, right , and key of the sentinel are immaterial. The red-black tree procedures can place whatever values in the sentinel that yield simpler code.

센티널 노드를 사용하는 이유는 코드의 간결성을 확보하기 위해서임이며, 매번 NULL 체크를 하지 않고도 리프 노드에 도달했음을 알 수 있고, 또한 같은 타임의 node를 사용하기에 블랙 노드의 개수를 확인하는데에도 편리하다는 이점이 있다.