이진 탐색 트리-(2)

노은서·2024년 10월 11일
C++자료구조

📌 이진탐색 트리 연산 - delete

✅ BST delete 연산

  • delete 연산 : remove(n)
  • 이진탐색트리의 특성을 유지하면서 노드 n을 트리에서 delete (왼쪽 서브트리 < 루트 노드 < 오른족 서브트리)

📢 노드 삭제의 3가지 경우

  1. 삭제하려는 노드가 단말(리프) 노드일 경우
  2. 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우
  3. 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우
    ** 여전히 BST 특성을 만족하는지 확인

⭐ Case를 3가지로 잘 구분하고, 각각의 Case 안 에서도 또 나뉘는 경우를 잘 구분할 줄 알아야함.

✅ Case 1 : 삭제하려는 노드가 단말 노드일 경우

여기서도 3가지 케이스로 나뉨

🏷️ 0) 제거 노드가 루트 노드인 경우,
🏷️ 1) 제거 노드가 부모 노드의 왼쪽 자식인 경우, 부모 노드의 왼쪽 링크 NULL
🏷️ 2) 제거 노드가 부모 노드의 오른쪽 자식인 경우, 부모 노드의 오른쪽 링크 NULL

void remove(BinaryNode* parent, BinaryNode* node){
   if(node->isLeaf()) { // case 1 : 제거 노드가 단말인 경우
         if(parent == NULL) root  = NULL; // 제거 노드가 root인 경우(0)
         // 부모 노드가 있는 경우 
         else{ // 제거 노드가 left child(1)
             if(parent->getLeft() == node)
                parent->setLeft(NULL);
             else // 제거 노드가 right child(2)
                 parent->setRight(NULL);
           }
     }

📢 코드 설명

  • parent : 삭제할 노드의 부모 노드를 가리키는 포인터
  • node : 실제로 삭제될 노드를 가리키는 포인터
    ⭐ 부모 노드를 알아야 삭제 후 부모와 나머지 트리의 연결을 유지할 수 있기 때문에, parent,node를 모두 전달받음
    ** 노드가 부모의 왼쪽 자식인 경우
  • parent->getLeft()==node; : 부모 노드의 왼쪽 자식이 삭제할 노드와 주소가 같은지 확인함.
  • parent->setLeft(NULL); : 부모의 왼쪽 자식 포인터를 NULL로 설정해 연결을 끊는다.

✅ Case 2 : 삭제하려는 노드가 왼쪽이나 오른쪽 서브 트리 중 하나만 가지고 있는 경우

여기서도 3가지 케이스로 나뉨

🏷️ 0) 제거 노드가 루트 노드인 경우,
🏷️ 1) 부모 노드의 왼쪽 자식인 경우, 부모 노드의 왼쪽에 제거 노드의 child 연결
🏷️ 2) 부모 노드의 오른쪽 자식인 경우, 부모 노드의 오른쪽에 제거 노드의 child 연결 


void remove(BinaryNode* parent, BinaryNode* node){
  if(node->isLeaf()) {Case:1}
  // Case 2 : 삭제하려는 노드가 서브트리 중 하나만 갖고 있는 경우
  else if(node->getLeft()==NULL || node->getRight()==NULL){
  // 삭제 노드의 child가 left child인지, right child인지 child에 저장
  BinaryNode* child = (node->getLeft() != NULL) ? 
                       node->getLeft() : node->getRight();
  if(node==root) root=child; // (0)삭제 노드가 root면, root 삭제하고 child를 root로!
  else{
       if(parent->getLeft()==node) // (1)부모 노드의 왼쪽에 제거 노드가 있는 경우,
          parent->setLeft(child); // 부모 노드의 왼쪽에 child 연결 
       else{
          parent->setRight(child);} // (2)부모 노드의 오른쪽에 child 연결 
   }
}

📢 코드 설명

  • 왼쪽 자식 또는 오른쪽 자식이 없는지 확인, 둘 중 하나만 BULL이면, 즉 한쪽에만 자식이 있는 경우!
else if(node->getLeft()==NULL || node->getRight()==NULL)
  • 삭제하려는 node의 자식, child 포인터 변수를 정의
BinaryNode* child = (node->getLeft() != NULL) ? 
                    node->getLeft() : node->getRight();

** child 노드를 저장하는 이유
= 삭제하려는 노드의 자리를 자식 노드(child)가 대신 차지해야 하기 때문에 (왼쪽/오른쪽 나눠져서 저장을 해야함)

  • root 노드를 삭제하면, 트리의 새로운 root는 삭제된 노드의 자식 노드(child)가 되어야함
// 자식 노드를 루트로 지정
if(node==root) root=child;
  • 부모 노드의 왼쪽 자식이 삭제하려는 노드이면 (1), 부모 노드의 왼쪽 자식을 child노드로 삭제
parent->setLeft(child);

✅ Case 3 : 삭제하려는 노드가 두 개의 서브 트리 모두 가지고 있는 경우

⭐가장 어렵고 복잡함⭐

  • 해당 노드를 삭제하고, 삭제 후보 중 가장 차이가 적은 노드를 삭제 노드 위치로 가져옴

  • 후보 2개
    --> 왼쪽 서브트리에서 제일 큰 값 : rightmost node(왼쪽 서브트리에서 가장 오른쪽에 있음)

    --> 오른쪽 서브트리에서 제일 작은 값 : leftmost node(오른쪽 서브트리에서 가장 왼쪽에 있음)

  • 삭제하려는 노드 20을 삭제한 후 이진탐색트리
    --> rightmost : 14, leftmost : 24 중에서 20이랑 차이가 작은 24를 20이 있는 자리로 대체

📝 leftmost node로 대체되는 경우

= leftmost 노드의 위치에 따라 2가지 경우로 나눠짐

(1) 제거 노드의 오른쪽 노드 하위에, 왼쪽 서브트리에 leftmost 노드가 있는 경우
✔️(1-1) leftmost 노드가 리프 노드인 경우
✔️(1-2) leftmost 노드가 오른쪽 child를 가지는 경우
(왼쪽 child를 가지는 경우는 X --> 그럼 그 노드가 leftmost 였어야함!!!)
(2) 제거 노드의 오른쪽 노드가 leftmost 노드인 경우

❔ Case1,2와 달리 Case3에선 parent 노드가 없는 이유

  • Case1,2에선 삭제할 노드를 제거하고 child이랑 parent에 바로 연결해줘야 하니깐 parent가 반드시 있어야함
  • Case 3는 삭제할 노드(=5) 그 자체를 제거하는 대신에, 그 노드를 대체할 후계자 노드(leftmost=6)를 찾고, 그 데이터를 copy(5자리에 6을 복사함)해준다. 그리고 leftmost 자리를 제거해줌 --> 이 방법이 더 효율적이고 복잡하지 않음!!

⭐ Case3 : 노드 5 삭제 과정

** 삭제하려는 노드를 그 자리로 대체할 노드 --> leftmost 

void remove (BinaryNode* parent, BinaryNode* node){
        if() {//case 1}
        else if {//case 2}
        // case 3
        else { // 삭제 노드에서 한번 오른쪽으로 가서 계속 왼쪽으로 가면 leftmost node
                BinaryNode* succp = node;
                BinaryNode* succ = node->getRight();
1) leftmost 찾기 
                while(succ->getLeft() != NULL){  
                    succp = succ; /
                    succ = succ->getLeft(); // find leftmost node, succ 
  
2) 연결         if(succp->getLeft()==succ)
                    succp->setLeft(succ->getRight()); // 이 코드로 (1-1), (1-2) 다 커버가능!!
                else // (2) 경우, 제거 노드의 오른쪽 노드가 leftmost 노드인 경우 
                    succp->setRight(succ->getRight());
 
3) 복사          node->setData(succ->getData());

4) 삭제          node = succ; // 노드를 삭제해주기 위해
                }
                delete node;
            }

📢 코드 설명

(0) succp,succ 포인터 변수 선언

  • succp : 후계자 노드(=leftmost)의 부모 노드를 가리키는 포인터
    --> 후계자 노드의 부모를 추적하여 후계자 노드를 삭제할 때 부모 노드와의 연결을 끊어야 하기 때문에 필요함
  • succ : 후계자 노드(=leftmost)를 가리키는 포인터
    --> 처음에는 삭제할 노드의 오른쪽 자식으로 시작함!!
    --> 후계자 노드를 찾은 후(6), 그 데이터를 삭제할 노드(5)에 복사해야함
    (1) leftmost 찾기
  • succ가 왼쪽 자식을 가지고 있는 한, 계속 왼쪽으로 이동하며, 그때 succp도 같이 이동함
  • while(succ->getLeft() != NULL) : 포인터가 왼쪽 자식을 가리키고 있는 동안 계속 반복, 리프노드에 도달하면 종료
  • succp = succ; : 현재 후계자 노드를 부모로 업데이트함. 즉, 후계자 노드가 될 수 있는 succ의 부모를 기억하기 위함입니다.
  • succ = succ->getLeft(); : succ를 왼쪽 자식으로 이동시키면서 트리의 오른쪽 서브트리에서 가장 작은 노드를 찾습니다.
    (2) 연결
    = leftmost 노드를 제거한 후에도 BST 유지하려면 leftmost의 자식이 오른쪽 자식이 부모 노드랑 연결되어야함
  • if(succp->getLeft() == succ) : Case 3-(1), Case 3-(2) 현재 후계자 노드가 부모 노드(succp)의 왼쪽 자식인지 확인
  • succp->setLeft(succ->getRight()); : 후계자 노드가 부모 노드의 왼쪽 자식이면, 후계자 노드의 오른쪽 자식을 부모 노드의 왼쪽 자식으로 업데이트
  • else : 후계자 노드가 부모의 오른쪽 노드인 경우Case 3-(2)
  • succp->setRight(succ->getRight()); : 후계자 노드가 부모의 오른쪽 자식이라면 , 후계자 노드의 오른쪽 자식을 부모 노드의 오른쪽 자식으로 업데이트 함
    (3) 복사
  • node->setData(succ->getData()); : 삭제하려는 노드(node)에 후계자 노드(succ)의 데이터를 복사함 --> 삭제할 노드가 후계자 노드의 값으로 대체됨
    (4) 삭제
  • node = succ; : node 포인터가 후계자 노드를 가리키도록 설정
  • delete node; : 후계자 노드(leftmost) 노드를 메모리에서 삭제
    ** 삭제하는 이유 : leftmost 값은 삭제할 노드(node)에 복사되었으므로, 더 이상 leftmost node가 필요 없음

✅ remove 연산 전체 code

⭐ void remove (int key)
: key값을 갖는 노드를 탐색하는 역할 --> 노드 제거(두 번째 함수)
: while 루프를 통해 root부터 시작해 key 값이 있는 노드를 찾음 

//삭제할 키 값을 입력받아, 이 키 값을 가진 노드를 트리에서 찾아 삭제함. 
void BinSrchTree::Remove(int key){
 if(isEmpty()) return; // 트리가 비어 있으면 작업X, 함수 바로 종료

 BinaryNode* parent = NULL; // 처음에는 부모 노드는 null
 BinaryNode* node = root; // root에서 시작

 while(node!=NULL && node->getData()!=key){ // key값을 갖는 노드 탐색
    parent = node;
    node = (key < node->getData()) ? node->getLeft() : node->getRight();
  }
  if(node==NULL){
    cout << "Error key is not in the tree\n";
    return;
  }
  else remove(parent,node); // key값을 갖는 노드 제거
}

📢 코드 설명

✔️ BinaryNode* parent = NULL;
: 삭제할 노드를 찾는 과정에서, 부모 노드를 추적하기 위한 포인터 parent를 초기화. 처음에는 부모 노드를 알 수 없으므로 NULL
✔️BinaryNode* node = root;
: 루트 노드에서 탐색을 시작. 삭제할 노드를 찾기 위해선 트리를 root부러 내려가면서 탐색
✔️ while(node!=NULL && node->getData()!=key){
: loop가 실행되며, 트리에서 해당 key값을 가진 노드를 탐색.
--> node가 NULL이 아닌 동안, 그리고 현재 노드의 데이터가 찾는 key값이 아닌 동안 계속 탐색을 진행
✔️node = (key < node->getData()) ? node->getLeft() : node->getRight();
: key 값을 기준으로 왼쪽 또는 오른쪽 자식으로 이동함 (BST 특성)
--> 현재 node가 key보다 크면 왼쪽 자식으로 이동하고, 작으면 오른쪽 자식으로 이동
✔️if(node==NULL){ : 탐색을 끝나고도 node가 null이면, 탐색 실패!!
✔️ else remove(parent, node);
: 삭제할 node를 찾았을 경우, 두 번째 remove 함수를 호출해 실제로 노드를 삭제해줌!! --> 이때 부모 노드 parent이랑 삭제할 노드 node를 넘겨줌

❓ 왜 search 함수를 안쓰고 따로 탐색을 정의하는 이유

- 이유 1 : 부모 노드 추적이 필요함
--> 일반적인 search 함수는 트리에서 노드만을 찾는 역할을 함.
--> 삭제할 노드를 찾은 후, 삭제하려면 부모 노드와의 연결을 끊거나, 자식 노드를 부모 노드에 연결해줘야함!!!
- 이유 2 : search 함수는 부모 노드를 반환하지 않음
--> search 함수만을 사용하면, key는 찾을 수 있지만, 그 부모 노드를 알 수 없음.

⭐ void remove(BinaryNode* parent, BinaryNode* node)
: remove : case1,case2,case3, 실제 삭제 로직을 구현하는 함수

void BinSrchTree:: remove (BinaryNode *parent, BinaryNode *node) {

  // case 1
  if( node->isLeaf() ) {
  	if( parent == NULL ) root = NULL;
  	else {
	    if( parent->getLeft() == node )
	    	 parent->setLeft(NULL);
	    else
	    	parent->setRight(NULL);
  	}
  }
  // case 2
  else if( node->getLeft()== NULL|| node->getRight()==NULL ) {
	BinaryNode *child = (node->getLeft() != NULL )
			? node->getLeft() : node->getRight();
	if( node == root )
	    root = child;
	else {
	    if( parent->getLeft() == node )
		parent->setLeft(child); 
	    else 
		parent->setRight(child); 
	}
  }
    // case 3
  else {
	BinaryNode* succp = node;
	BinaryNode* succ = node->getRight();
	while (succ->getLeft() != NULL) { // find leftmost node
	    succp = succ;
	    succ = succ->getLeft();
	}

	if( succp->getLeft() == succ ) // (1)노드 연결
	    succp->setLeft(succ->getRight());
	else
	    succp->setRight(succ->getRight());

	node->setData(succ->getData()); // (2)데이터 복사
	node = succ;  //(3)노드 삭제
  }
  delete node;
}
profile
노은서
개발 & 공부 기록
이전 포스트

모두의 딥러닝 4장

다음 포스트

[자료구조실습] 트리 순회하기

0개의 댓글