Red Black tree의 카테고리 및 정의.
red–black tree is a kind of self-balancing binary search tree.
Each node stores an extra bit representing "color" ("red" or "black"),
used to ensure that the tree remains balanced during insertions and deletionsself-balancing binary search tree 에서,
BST(binary search tree) : 모든 임의의 노드에서, 왼쪽 자식노드의 모든 값들은 오른쪽 자식노드의 모든 값보다 작은 이진 트리.
self-balancing : 모든 임의의 노드에서, 왼쪽 depth와 오른쪽 depth가 2이상 차이가 나지 않는 트리를 만드는 자료구조의 앞에 붙이는 접두사.
r-b트리는 self-balancing binary tree의 일종이다.
r-b tree란?
이제 r-b 트리는 이 self-balancing binary tree가 되기 위해, 모든 노드에 1비트짜리 property를 넣어주는데, 이 값이 balance를 충족시켜주는 키포인트가 되는 것이다.
이 1비트는 두가지 값을 나타 낼 수 있으니, 하나는 red, 하나는 black을 나타나게 하여 r-b tree 가 된 것이다.
r-b tree 장점
worst case guarantees
- 어떤 method에 대해 최대시간을 보장해준다. 그리고, 이 속도가 꽤 빠른편(logN)이다.
r-b트리를 만족하기 위해 1bit만 노드마다 추가되면 되서, 무겁지 않다.
r-b vs avl tree
다른 self-balancing binary tree 의 대표인 AVL과 비교가 자주된다.
대표적인 비교점으로
AVL은 look-ups에 있어 효율적이다.
rb-tree는 insert,delete에서 더 효율적이다.
을 볼 수 있다.
사용
- c++ std에서 map.
사용시 팁
데이터 구조 사용시, search가 필요한가(즉, 정렬이 필요한가)에 따라 어떤 걸 쓸지 생각해볼수 있다. c++에서 이름이 비슷한 unordered_map 과 비교해보면,
unordered_map은 해쉬테이블 기반으로 만들어져 있어서, key(이름)을 알면 접근이 가능해서 평균 O(1)로 해결이 가능하다. 이 경우에는 데이터를 search하는 부분이 없으므로, 데이터를 저장하고 원하는 데이터의 이름을 바로 알 수 있는 상황이면 이 unordered_map이 적절하다.
단, search가 필요하면(그에 맞는 데이터가 있는지 없는지 모든 데이터에 대해 효율적인 탐색이 필요한 경우)는 map이 더좋다.
