자료구조...68

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

 

BinarySearchTree.cpp

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

	while (*target != nullptr)
	{
		if ((*target)->m_data == value)
		{
			break;
		}

		if ((*target)->m_data > value)
		{
			parent = *target;
			target = &((*target)->m_left);
		}
		else
		{
			parent = *target;
			target = &((*target)->m_right);
		}
	}

	if (parent == nullptr)
	{
		parent = m_root;
	}

	Node* deleteNode{ *target };

	if (target != nullptr && *target != nullptr)
	{
		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->m_left == (*target))
			{
				parent->m_left = child;
			}
			else if (parent->m_right == (*target))
			{
				parent->m_right = child;
			}
		}
		else if ((*target)->m_left != nullptr && (*target)->m_right != nullptr)
		{
			parent = *target;
			Node* child{ (*target)->m_left };
			while (child->m_right != nullptr)
			{
				parent = child;
				child = child->m_right;
			}

			(*target)->m_data = child->m_data;
			target = &child;
			deleteNode = *target;

			if (child->m_left != nullptr)
			{
				if (parent->m_left == child)
				{
					parent->m_left = child->m_left;
				}
				else if (parent->m_right == child)
				{
					parent->m_right = child->m_left;
				}
			}
		}
		else
		{
			
			if (parent->m_left == (*target))
			{
				parent->m_left = nullptr;
			}
			else if (parent->m_right == (*target))
			{
				parent->m_right = nullptr;
			}
		}

		PushNode(deleteNode);
		m_count--;
	}
}

 

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
    └  4
  └  8
    └  7
    └  9
----------------------

 

4가 제거되지 않고 트리에 남아있다. 아마 제거 로직에 문제가 있는 것 같다. 내일 책을 참고해서 재작성해야 할 것 같다.