개발자의 기록습관

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