👀 finalfrontier

Red Black Tree 1. Concept [revisited] 다음과 같은 성질을 만족하는 이진 검색 트리 BST 모든 노드는 red or black root 노드는 black leaf (nil)노드는 black red 노드의 자식은 black 한 노드에서 leaf(nil)로 가는 각 경로에 포함된 black 노드의 개수는 모두 같다. 2. Operations typedef enum {RBTREE_BLACK, RBTREE_RED} color_t; typedef int key_t; typedef struct node_t { key_t key; color_t color; struct node_t* parent; struct node_t* left; struct node_t* right; } typede..

Red Black Tree 다음과 같은 성질을 만족하는 이진 검색 트리 모든 노드는 레드나 블랙 루트는 블랙 리프(NIL)는 블랙 레드 노드의 자식은 모두 블랙 한 노드로부터 그 자손인 리프 노드로까지 가는 경로에 포함된 블랙 노드의 개수가 같음 레드 블랙 트리는 이진 검색 트리로서, 각 노드 당 한 비트의 추가 메모리에 노드의 색깔(레드, 블랙)을 저장한다. 루트에서 리프까지의 경로에 나타나는 노드의 색을 제한함으로써 그러한 경로 중 어떠한 것도 다른 것보다 두 배 이상 길지 않음을 보장할 수 있다. 이로써 근사적으로 균형을 이룬 트리 가 된다. 경계노드 sentinel 각 노드마다 리프노드를 모두 NIL로 붙여주는 대신, 이를 표현하는 하나의 노드만을 사용할 수 있는데 이를 경계노드(sentinel)..