이진 탐색 트리 (C#)

using System;
 
public class BinarySearchTree<T> where T : IComparable<T>
{
    public class Node
    {
        public T Data;
        public Node Left;
        public Node Right;
 
        public Node(T data)
        {
            Data = data;
            Left = null;
            Right = null;
        }
    }
 
    private Node root;
 
    public BinarySearchTree()
    {
        root = null;
    }
 
    //데이터를 이진 탐색 트리에 삽입.
    public void Insert(T data)
    {
        root = InsertRecursive(root, data);
    }
 
    //재귀적으로 노드를 삽입.
    private Node InsertRecursive(Node current, T data)
    {
        if (current == null)
            return new Node(data); //삽입할 위치에 도달하면 새로운 노드를 생성하고 반환한다.
 
        if (data.CompareTo(current.Data) < 0)
        {
            current.Left = InsertRecursive(current.Left, data); //데이터가 현재 노드의 데이터보다 작으면 왼쪽 자식트리로 이동하여 삽입한다.
        }
        else
        {
            current.Right = InsertRecursive(current.Right, data); //데이터가 현재 노드의 데이터보다 크거나 같으면 오른쪽 자식트리로 이동하여 삽입한다.
        }
 
        return current;
    }
 
    //주어진 데이터가 이진 탐색 트리에 포함되어 있는지 확인한다.
    public bool Contains(T data)
    {
        return ContainsRecursive(root, data);
    }
 
    //노드를 탐색하여 데이터 포함 여부를 확인
    private bool ContainsRecursive(Node current, T data)
    {
        if (current == null)
            return false; //탐색할 위치에 도달하면 데이터를 찾지 못한 것이므로 false를 반환한다.
 
        if (data.CompareTo(current.Data) == 0)
        {
            return true; //데이터를 찾은 경우 true를 반환한다.
        }
 
        if (data.CompareTo(current.Data) < 0)
        {
            return ContainsRecursive(current.Left, data); //데이터가 현재 노드의 데이터보다 작으면 왼쪽 서브트리로 이동하여 탐색한다.
        }
        else
        {
            return ContainsRecursive(current.Right, data); //데이터가 현재 노드의 데이터보다 크면 오른쪽 서브트리로 이동하여 탐색한다.
        }
    }
 
    //주어진 데이터를 이진 탐색 트리에서 제거
    public void Remove(T data)
    {
        root = RemoveRecursive(root, data);
    }
 
    // 재귀적으로 노드를 제거
    private Node RemoveRecursive(Node current, T data)
    {
        if (current == null)
            return null;
 
        if (data.CompareTo(current.Data) == 0)
        {
            // 제거할 노드를 찾은 경우
            if (current.Left == null && current.Right == null)
            {
                return null;
            }
            else if (current.Left == null)
            {
                return current.Right; // 왼쪽 서브트리가 없는 경우 오른쪽 서브트리를 반환하여 해당 노드를 제거한다.
            }
            else if (current.Right == null)
            {
                return current.Left; // 오른쪽 서브트리가 없는 경우 왼쪽 서브트리를 반환하여 해당 노드를 제거한다.
            }
            else
            {
                // 왼쪽 서브트리와 오른쪽 서브트리가 모두 있는 경우
                T smallestValue = FindSmallestValue(current.Right); // 오른쪽 서브트리에서 가장 작은 값을 찾는다.
                current.Data = smallestValue; // 찾은 가장 작은 값을 현재 노드에 복사한다.
                current.Right = RemoveRecursive(current.Right, smallestValue); // 오른쪽 서브트리에서 가장 작은 값을 제거한다.
                return current;
            }
        }
 
        if (data.CompareTo(current.Data) < 0)
        {
            current.Left = RemoveRecursive(current.Left, data); // 데이터가 현재 노드의 데이터보다 작으면 왼쪽 서브트리로 이동하여 제거한다.
        }
        else
        {
            current.Right = RemoveRecursive(current.Right, data); // 데이터가 현재 노드의 데이터보다 크면 오른쪽 서브트리로 이동하여 제거한다.
        }
 
        return current;
    }
 
    //가장 작은 값을 찾으려면 왼쪽 노드를 계속 찾으면 된다.
    private T FindSmallestValue(Node node = null)
    {
        Node current = node == null ? root : node;
 
        while (current.Left != null)
            current = current.Left; 
 
        return current.Data; 
    }
 
    //가장 작은 값을 찾으려면 오른쪽 노드를 계속 찾으면 된다.
    public T FindMaxValue(Node node = null)
    {
        Node current = node == null ? root : node;
 
        while (current.Right != null)
            current = current.Right; 
 
        return current.Data;
    }
}