코딩 테스트 대비: 이진 탐색 트리를 이용한 데이터 검색 및 삽입 (C#)

안녕하세요, GameLabMaster입니다! 오늘의 코딩 테스트 대비 포스팅에서는 이진 탐색 트리(Binary Search Tree, BST)를 사용하여 데이터를 검색하고 삽입하는 방법을 다루겠습니다. 이진 탐색 트리는 자료구조 중 하나로, 데이터를 효율적으로 저장하고 검색할 수 있는 구조입니다. 이진 탐색 트리는 각 노드가 최대 두 개의 자식 노드를 가지며, 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값이 부모 노드의 값보다 큰 특징이 있습니다.

 

문제
이진 탐색 트리에 데이터를 삽입하고, 주어진 값을 검색하는 함수를 구현하세요.

 

풀이
먼저, 이진 탐색 트리의 노드를 나타내는 클래스를 작성해보겠습니다.

 

public class TreeNode {
    public int Value;
    public TreeNode Left;
    public TreeNode Right;

    public TreeNode(int value) {
        Value = value;
        Left = null;
        Right = null;
    }
}

 

이제 이진 탐색 트리를 구현하는 클래스를 작성해보겠습니다. 이 클래스에서는 데이터를 삽입하는 Insert 메소드와 데이터를 검색하는 Search 메소드를 구현합니다.

 

public class BinarySearchTree {
    private TreeNode _root;

    public BinarySearchTree() {
        _root = null;
    }

    public void Insert(int value) {
        if (_root == null) {
            _root = new TreeNode(value);
        } else {
            Insert(_root, value);
        }
    }

    private void Insert(TreeNode node, int value) {
        if (value < node.Value) {
            if (node.Left == null) {
                node.Left = new TreeNode(value);
            } else {
                Insert(node.Left, value);
            }
        } else {
            if (node.Right == null) {
                node.Right = new TreeNode(value);
            } else {
                Insert(node.Right, value);
            }
        }
    }

    public bool Search(int value) {
        return Search(_root, value);
    }

    private bool Search(TreeNode node, int value) {
        if (node == null) {
            return false;
        }

        if (node.Value == value) {
            return true;
        } else if (value < node.Value) {
            return Search(node.Left, value);
        } else {
            return Search(node.Right, value);
        }
    }
}

 

이제 주어진 데이터를 이진 탐색 트리에 삽입하고, 검색을 수행하는 예제를 작성해보겠습니다.

 

public static void Main(string[] args) {
    BinarySearchTree bst = new BinarySearchTree();
    int[] values = { 50, 30, 20, 40, 70, 60, 80 };

    foreach (int value in values) {
        bst.Insert(value);
    }

    Console.WriteLine($"Search for 40: {bst.Search(40)}"); // true
    Console.WriteLine($"Search for 90: {bst.Search(90)}"); // false
}

 

이 예제에서는 주어진 데이터를 이진 탐색 트리에 삽입한 후, 값을 검색해봤습니다. 40은 트리에 있으므로 true를 반환하고, 90은 트리에 없으므로 false를 반환합니다.

 

이상으로 오늘의 코딩 테스트 대비 포스팅을 마치겠습니다. 이진 탐색 트리는 검색, 삽입, 삭제 연산이 빠르게 수행될 수 있는 자료구조로, 알고리즘 문제에서 많이 활용됩니다. 다음 포스팅에서는 더 다양한 문제와 알고리즘에 대해 알아보겠습니다. 감사합니다!