차마시는 개발자

레드 블랙 트리 삭제 삭제하는 node(x)가 Black일 때 실행 이중 흑색 노드일 경우 Case 파악 이중 흑색 노드: 검은색 node를 다시 검은색으로 칠하는 경우 그냥 삭제 합니다. (무조건 실행) 이진 검색 트리 삭제 이용 자리를 대체하는 node를 검정색으로 변환 Red -> Black : 괜찮다 Black -> Black : 이중 흑색 노드 Case change) x의 형제가 Red 1. x의 형제 Red -> Black 2. x의 부모 * -> Red 3. x의 부모를 기준으로 왼쪽 회전 4. 다른 Case 이동 Case 1) x의 형제가 Black x..

레드 블랙 트리 (Red-Black Tree) https://ko.wikipedia.org/wiki/%EB%A0%88%EB%93%9C-%EB%B8%94%EB%9E%99_%ED%8A%B8%EB%A6%AC 조건 1. Root는 Black이다 2. 모든 리프(NIL)는 Black이다. 3. node가 Red -> node의 자식은 반드시 Black 연속된 Red node X 4. Root에서 임의의 리프 node까지 만나는 Black node의 수는 같다. 레드 블랙 트리 삽입 삽입한 node는 무조건 Red node 입니다. Red node - Red node 겹칠 때 Case 파악 Red node의 부모 node도 Red일 경우 맨 밑의 Red node가 기준 입니다. Restructuring 삽입된 no..