이진 탐색 트리(Binary Search Tree)의 검색, 삭제, 순회 연산 이해와 C# 예제 코드

안녕하세요! 오늘의 기술 면접 지식은 이진 탐색 트리(Binary Search Tree, BST)의 추가 연산에 관한 것입니다. 이 포스팅에서는 이진 탐색 트리의 검색, 삭제, 순회 연산에 대한 개념과 C#을 사용한 구현 예시에 대해 알아봅니다.

이진 탐색 트리의 검색 연산

이진 탐색 트리에서 검색 연산은 트리를 순회하며 값을 찾는 작업입니다. BST의 구조를 활용하면 효율적으로 검색할 수 있습니다.

이진 탐색 트리의 삭제 연산

이진 탐색 트리에서 노드를 삭제하는 연산은 세 가지 경우를 고려해야 합니다.

 

• 삭제할 노드가 잎 노드인 경우: 해당 노드를 그냥 삭제합니다.
• 삭제할 노드가 하나의 자식 노드만 가지는 경우: 해당 노드를 삭제하고 자식 노드를 부모 노드에 연결합니다.
• 삭제할 노드가 두 개의 자식 노드를 가지는 경우: 오른쪽 서브트리의 가장 작은 값 또는 왼쪽 서브트리의 가장 큰 값으로 대체하고, 해당 값을 가진 노드를 삭제합니다.

이진 탐색 트리의 순회 연산

이진 탐색 트리를 순회하는 방법은 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder) 등이 있습니다. 중위 순회를 사용하면 오름차순으로 정렬된 값을 얻을 수 있습니다.

C#을 사용한 이진 탐색 트리의 추가 연산 구현 예시

이전 포스팅에서 작성한 이진 탐색 트리 클래스에 검색, 삭제, 순회 연산을 추가하겠습니다.

 

// 검색 연산
public bool Search(int value)
{
    return SearchRecursively(Root, value) != null;
}

private Node SearchRecursively(Node node, int value)
{
    if (node == null || node.Value == value)
    {
        return node;
    }

    if (value < node.Value)
    {
        return SearchRecursively(node.Left, value);
    }

    return SearchRecursively(node.Right, value);
}

// 삭제 연산
public void Delete(int value)
{
    Root = DeleteRecursively(Root, value);
}

private Node DeleteRecursively(Node node, int value)
{
    if (node == null)
    {
        return node;
    }

    if (value < node.Value)
    {
        node.Left = DeleteRecursively(node.Left, value);
    }
    else if (value > node.Value)
    {
        node.Right = DeleteRecursively(node.Right, value);
    }
    else
    {
        if (node.Left == null)
        {
            return node.Right;
        }
        else if (node.Right == null)
        {
            return node.Left;
        }

        node.Value = FindMinValue(node.Right);
        node.Right = DeleteRecursively(node.Right, node.Value);
    }

    return node;
}

private int FindMinValue(Node node)
{
    int minValue = node.Value;
    while (node.Left != null)
    {
        minValue = node.Left.Value;
        node = node.Left;
    }
    return minValue;
}

// 순회 연산
public void InorderTraversal()
{
    InorderTraversalRecursively(Root);
    Console.WriteLine();
}

private void InorderTraversalRecursively(Node node)
{
    if (node != null)
    {
        InorderTraversalRecursively(node.Left);
        Console.Write($"{node.Value} ");
        InorderTraversalRecursively(node.Right);
    }
}

 

위 코드는 이진 탐색 트리 클래스에 검색, 삭제, 순회 연산을 추가한 예시입니다. 검색과 삭제 연산은 재귀적으로 구현되어 있으며, 순회 연산은 중위 순회를 사용해 구현했습니다.

 

이상으로 이진 탐색 트리의 추가 연산과 C#을 사용한 구현 예시를 살펴봤습니다. 이진 탐색 트리는 검색, 삽입, 삭제 연산이 빠른 자료 구조로, 다양한 분야에서 활용됩니다. 기술 면접 준비에 도움이 되길 바랍니다. 다음 포스팅에서 또 다른 주제로 찾아뵙겠습니다!