개발자의 기록습관

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-1. Red-Black Tree 01 - 개요앞서 배운 BST의 search, insert, delete 세 가지 연산모두 O(h)의 시간복잡도를 가진다. (h는 트리의 높이)여기서 문제는, 트리의 높이 h가 최악의 경우 n이 될 수 있다. n은 노드의 총 수.그러나, 이것은 실제 최악의 경우에 해당한다. BST에 데이터들이 random하게 구성된다고 가정했을때, 평균 트리의 높이는 O(logn)이 된다.그럼에도 불구하고, 최악의 경우 O(n)이 되는 경우는 좋은 알고리즘은 아니다. 그리고, 현실에서 이미 정렬된 데이터가 BST에 inser..