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 노드부터..

IntroDynamic Set과 Binary Search Tree Dynamic set은 1. 크기가 동적으로 변화하면서, 2. 삽입/삭제/탐색 연산을 지원해야 한다. BST는 dynamic set 중 하나이다. 한편, 일반적인 tree는 1 조건은 만족하나, 2 조건은 만족하지 않으므로 dynamic set이라 하기 어렵다. Binary Search / Binary Tree / Binary Search Tree 셋은 전부 다른 것! 뒷단어에 유의해 보도록 한다.binary search : 이진 '탐색' 알고리즘binary tree : 이진 '트리' 자료구조binary search tree : 이진 '탐색' 조건을 만족하는 '트리' 자료구조 ($\subset$ binary tree)Binary Searc..