Red Black Tree

Home /
Tags /
Red Black Tree

Data structure
2020년 10월 23일

BST (이진 탐색 트리)를 기반으로 둔 Tree. Tree의 Rebalancing 방법 중 하나로 balanced한 트리이다. 각 노드는 값(key)말고도 색을 갖고 있으며, 색은 레드 or 블랙 2종류이다. 1. Red Black Tree가 갖는 특성 Root Property : 루트(root)노드는 블랙(black)이다. External Property : 모든 외부 노드 (external node)는 블랙이다. Depth Property : 모든 단말 노드(leaf node)의 경우 루트부터 외부 노드 까지 방문하는 블랙 노드의 수가 같다. Internal Property : 빨강 노드의 자식은 블랙이다. == No Double Red : 레드 노드는 두개가 연속해서 올 수 없다....