개발자의 기록습관

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-3. Red-Black Tree 03 - DELETE, FIXUPDELETE보통의 BST에서처럼 DELETE한다.실제로 삭제된 노드 y가 red였으면 종료y가 black이었을 경우 RB-DELETE-FIXUP을 호출한다.pesudo code01 : 삭제할 노드 z의 왼쪽, 오른쪽 자식이 NULL이 아니라면 즉, 자식이 없다면02 : y에 z를 저장하고03 : 자식이 있다면, z의 Successor를 찾아서 y에 저장한다. BST에서 Successor찾는 과정과 동일04 : 01-03과정을 거치면 y는 자식이 하나이거나 없다. Successo..

인프런 - 부경대IT융합응용공학과 궘오흠 교수님의 '영리한 프로그래밍을 위한 알고리즘 강좌 '(링크)와 '쉽게 배우는 알고리즘 관계 중심의 사고법 - 문병로' 참조5-2. Red-Black Tree 02 - INSERT, FIXUPINSERT보통의 BST에서처럼 노드를 INSERT한다.새로운 노드 z를 red노드로 한다.RB-INSERT-FIXUP을 호출한다.1 : 또다른 포인터 y를 사용해서 y가 x의 한칸 뒤를 쫓아 내려오록 해야 새로운 노드를 insert할 자리를 관리할 수 있다. 레드블랙트리에서 특수하게 NIL 노드를 사용하지만, 실제로 구현할때는 null이 된다.3 - 7 : 새로운 노드 z가 들어갈 자리를 찾고,8 : z의 parent를 y로 설정해준다.9 - 10 : 예외적인 경우 y가 nu..

인프런 - 부경대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..