자료구조...69

이진 탐색 트리 삭제 메서드 구현

 

BinarySearchTree.cpp

/// <summary>
/// BinarySearchTree에서 지정된 값을 가진 노드를 제거한다.
/// </summary>
/// <param name="value">제거할 값</param>
void BinarySearchTree::Delete(int value)
{
	if (m_root == nullptr)
	{
		return;
	}

	Node* target{ m_root };
	Node* parent{ nullptr };
	while ((target != nullptr) && (target->m_data != value))
	{
		parent = target;
		if (target->m_data > value)
		{
			target = target->m_left;
		}
		else
		{
			target = target->m_right;
		}
	}

	if (target == nullptr)
	{
		return;
	}

	if (target->m_left == nullptr && target->m_right == nullptr)
	{
		if (parent == nullptr)
		{
			m_root = nullptr;
		}
		else if (parent->m_left == target)
		{
			parent->m_left = nullptr;
		}
		else
		{
			parent->m_right = nullptr;
		}
	}
	else if (target->m_left != nullptr && target->m_right == nullptr
		 || target->m_left == nullptr && target->m_right != nullptr)
	{
		Node* child{ target->m_left != nullptr ? target->m_left : target->m_right };
		
		if (parent == nullptr)
		{
			m_root = child;
		}
		else if(parent->m_left == target)
		{
			parent->m_left = child;
		}
		else
		{
			parent->m_right = child;
		}
	}
	else
	{
		parent = target;
		Node* successor{ target->m_left };
		
		while (successor->m_right != nullptr)
		{
			parent = successor;
			successor = successor->m_right;
		}

		if (parent->m_left == successor)
		{
			parent->m_left = successor->m_left;
		}
		else
		{
			parent->m_right = successor->m_left;
		}

		target->m_data = successor->m_data;
		target = successor;
	}

	PushNode(target);
}

 

main.cpp

#include <iostream>
#include "BinarySearchTree/BinarySearchTree.h"

// 생성한 자료구조 테스트용 메인
int main()
{
	BinarySearchTree bst;

	bst.Insert(5);

	bst.Insert(3);

	bst.Insert(1);

	bst.Insert(0);

	bst.Insert(4);

	bst.Insert(8);

	bst.Insert(7);

	bst.Insert(9);
	bst.PrintInfo();

	bst.Delete(5);
	bst.PrintInfo();
}

 

실행 결과

----------------------
└  5
  └  3
    └  1
      └  0
    └  4
  └  8
    └  7
    └  9
----------------------

----------------------
└  4
  └  3
    └  1
      └  0
  └  8
    └  7
    └  9
----------------------