삭제할 노드가 자식을 2개 갖고 있는 경우

<aside>

// 삭제할 노드가 자식 노드를 두 개 가진 경우
else {
	// 후보 초기화 과정
	succ_parent = p;
	succ = p->left;
	// 왼쪽에서 가장 큰 노드 찾기
	// 왼쪽 자식의 오른쪽 끝까지 내려감 -> 가장 큰 값
	while (succ->right != NULL)
	{
		succ_parent = succ;
		succ = succ->right;
	}
	// succ이 succ_parent의 왼쪽 자식인지 오른쪽 자식인지 구분하여 포인터 조정
	// succ가 부모의 왼쪽 자식인 경우
	if (succ_parent->left == succ)
	{
		succ_parent->left = succ->left;
	}
	else
	{
		succ_parent->right = succ->left;
		p->key = succ->key;
		p = succ;
	}
}

</aside>

설명

<aside>

        50(p)
       /  \\
     30    70
    /  \\
  20    40(succ) ===> 삭제할 노드 왼쪽 자식의 오른쪽까지 이동
        /
      35

        40   ← p->key = 40 ===> succ를 root로 이동
       /  \\
     30    70
    /  \\
  20    35   ← 30->right = 35 ===> succ_parent->right = succ->left로 이동한 노드(succ)의 부모(succ_parent)의 자식 노드 자리에 이동한 노드의 자식 노드(succ)를 연경

</aside>