⭐⭐⭐ 중요 !!

📌6주차 문제1번. BST 연산

✅ 문제

✅ 아이디어

⚠️ delete Case3에서 rightmost로 대체되는 경우, leftmost로 대체되는 경우 둘 다 고려해야함

⚠️ 제거할 node랑 rightmost,leftmost 중에 차이가 적은 것을 노드 자리에 대체해야함

• rightmost : 왼쪽 서브트리에서 제일 큰 값 (왼쪽 서브트리 가장 오른쪽)
• leftmost : 오른쪽 서브트리에서 제일 작은 값 (오른쪽 서브트리 가장 왼쪽)

⚠️ inorder 함수 구현해주기

✅ Case 3 delete 전체 코드(rightmost & leftmost)

⭐ succp_lm, succ_lm, succp_rm, succ_rm 포인터 변수 선언하기

BinaryNode* succp_lm = node;
BinaryNode* succ_lm = node->getRight();
BinaryNode* succp_rm = node;
BinaryNode* succ_rm = node->getLeft();

⭐ leftmost, rightmost 각각 탐색하기

// leftmost
		while (succ_lm->getLeft() != NULL) {
			succp_lm = succ_lm;
			succ_lm = succ_lm->getLeft();
		}
		// rightmost
		while (succ_rm->getRight() != NULL) {
			succp_rm = succ_rm;
			succ_rm = succ_rm->getRight();
		}

⭐ 제거할 노드 node와 leftmost, rightmost의 차이 구하기

⚠️ BST 특성 이용해서 차이가 양수값이 나오도록 제거할 노드 node 와 rightmost, leftmost 각각의 차이 구해주기

// leftmost와 rightmost 차이 비교
		int leftmost = succ_lm->getData() - node->getData();
		int rightmost = node->getData() - succ_rm->getData();

⭐ leftmost로 대체하는 경우 (node - leftmost) < (node - rightmost)

// leftmost로 대체하는 경우
		if (leftmost < rightmost) {
			if (succp_lm->getLeft() == succ_lm)
				succp_lm->setLeft(succ_lm->getRight());
			else
				succp_lm->setRight(succ_lm->getRight());

			node->setData(succ_lm->getData());
			node = succ_lm;
		}

⭐ rightmost로 대체하는 경우 (node - leftmost) > (node - rightmost)

// rightmost로 대체하는 경우
else{
	if (succp_rm->getRight() == succ_rm)
		succp_rm->setRight(succ_rm->getLeft());
	else
		succp_rm->setLeft(succ_rm->getLeft());

	node->setData(succ_rm->getData());
	node = succ_rm;
}
delete node;

✅ 메인 함수

int main() {
	BinSrchTree tree;
	int N, n;
	char input;

	cin >> N;

	for (int i = 0; i < N; i++) {

		cin >> input >> n;
		if (input == 'I') {
			tree.insert(new BinaryNode(n));
		}
		if (input == 'D') {
			tree.remove(n);
		}
	}

	tree.inorder(tree.getRoot());
	return 0;
}

📢 주의해야할 점

⚠️ char형 문자 I,D인지 판별할때 알파벳에 ' ' 작은 따음표 써주기
⚠️ I인지 D인지 판별할때 등호 부호 (==) --> = 하나만 쓰면 안됨!!