CH06 : Dynamic Sets and Searching 3 - Red-Black Tree
Balanced Binary Search Tree의 대표적 예 중 하나인 Red-Black Tree를 알아보려 한다. (BST에 대한 설명은 다음 링크를 참고 : https://malangdubu-tech.tistory.com/29)Red-Black Tree란? 이름처럼, 각 노드가 Red 혹은 Black의 색깔을 가지게 된다. 다음의 특징을 만족하는 BST이다.root property : root는 blackexternal property : 모든 leaf는 blackinternal property : red 노드의 자식은 blackblack의 자식은 red, black 둘 다 가능depth property : 모든 leaf는 같은 black depth를 가짐.black depth : root 노드부터..
2025.04.18