비선형 데이터구조, 트리(Tree) #8 이진 탐색 트리 삭제(Delete)

1. 이진 탐색 트리에서 노드가 삭제되는 3가지 상황

 

2. 이진 탐색 트리에서 Inorder Successor란 무엇인가?

• 이진 탐색 트리에서 Inorder Successor은 입력된 키 값보다 큰 값들중 제일 작은 수를 의미한다.
• Inorder Successor는 중위 순회(Inorder Traversal)에서 특정 노드를 기준으로 다음에 방문할 노드를 의미합니다.
• 이진 탐색 트리의 삭제(remove)에서 Inorder Successor 노드는 삭제될 노드를 기준으로 오른쪽 서브트리에서 가장 작은 값을 가진 노드에 해당됩니다. (minValue 메서드 참조)
• 아래 이진 탐색 트리에서 8의 inorder successor는 10이고 10의 경우에는 12, 14의 경우에는 20이 inorder successor 입니다.

 

 

3. 이진 탐색 트리 삭제(Delete) 구현

	public void remove(E obj)
	{
		root = remove(root, obj);
	}
	
	private Node<E> remove(Node<E> root, E obj)
	{
		// base case : tree is empty
		if(root==null)
		{
			return root;
		}

		// go to the left
		if(((Comparable<E>)obj).compareTo(root.data)<0)
		{
			root.left = remove(root.left, obj);			
		}
		// go to the right		
		else if(((Comparable<E>)obj).compareTo(root.data)>0)
		{
			root.right = remove(root.right, obj);
		}
		// equals root's data
		else if(((Comparable<E>)obj).compareTo(root.data)==0)
		{
			// 삭제할 노드가 하나의 자식 노드이거나 둘다 자식이 없는 경우
			if(root.left==null)
			{
				return root.right;
			}
			else if(root.right==null)
			{
				return root.left;
			}
			
			// 삭제할 노드가 왼쪽 자식, 오른쪽 자식 모두 있는 경우
			// inorder successor 탐색 (node의 값보다 큰수 중 제일 작은 값)
			// inorder successor 노드의 값을 복사하여 저장
			root.data = minValue(root.right).data;
			
			// inorder successor 노드를 제거
			root.right = remove(root.right, root.data);	
		}	
		return root;
	}

	@Test
	void removeTest() {
		BinarySearchTree<Integer> bst = new BinarySearchTree<Integer>();
		
		bst.add(10);
		bst.add(8);
		bst.add(20);
		bst.add(17);
		bst.add(9);
		
		bst.inorderTraversal();	// Expected Output : 8 9 10 17 20
		bst.remove(17);
		bst.inorderTraversal(); // Expected Output : 8 9 10 20
	}

Output
8 9 10 17 20
8 9 10 20

시간 복잡도(Time Complexity) : O(h), h는 이진 탐색 트리의 높이(height)로 가정합니다. 최악의 경우 삭제될 노드를 찾기 위해 루트 노드에서 가장 깊숙한 리프 노드로 순회를 해야 합니다. 탐색과 삭제의 연산이 n번 정도 걸릴 수 있습니다. 

 

References

source code : https://github.com/yonghwankim-dev/DataStruct/tree/main/Tree/BST/Implement
https://www.geeksforgeeks.org/binary-search-tree-set-2-delete/
[부스트코스] 자바로 구현하고 배우는 자료구조