(미완)Red-Black Tree 만들어보기

Make an RB Tree

Initiate an RB Tree

rbtree *new_rbtree(void) {
  rbtree *p = (rbtree *)calloc(1, sizeof(rbtree)); 
  node_t *sentinel = (node_t *)calloc(1, sizeof(node_t));
  sentinel->color = RBTREE_BLACK;
  p->nil = sentinel; 
  p->root = p->nil; 
  return p;
}

(나머지 내용은 천천히 추가..)

내가 궁금했던 것들

왜 sentinel은 한개만 정의되는지?

(생각해보면 당연한건데 아직 C언어에 적응을 못해서 그런지 머릿속이 복잡하다)

The sentinel node is a single node that is used as a placeholder in the RBTree to represent the absence of a node. This sentinel node is often referred to as the "nil" node because it serves as a null pointer to indicate that a node does not exist.

In the implementation of the RBTree, it is common to use a single sentinel node for both the left and right sides of the tree. This is because the sentinel node's purpose is to act as a placeholder for a node that does not exist, and so having two sentinel nodes (one for the left and one for the right) would be redundant.

Instead, the single sentinel node is used as a placeholder for all null pointers in the tree, and the tree's internal algorithms and functions are written to treat the sentinel node in a special way so that it acts as a placeholder for both the left and right sides of the tree.