[C#] 이진 탐색 (Binary search) vs 균형 이진 트리 (Balanced Binary Search Tree) 속도 비교

C# 에서 65000 숫자 중 32500이라는 숫자를 찾을 때 빠른 알고리즘을 찾기 위해 테스트를 해보았습니다.

이진 탐색이라는 점과 같은 시간 복잡도를 가지고 있는 Binary Search와 Balanced Binary Search Tree를 비교 해보겠습니다.

시간복잡도 : O(logN)

알고리즘 : 이진 탐색 알고리즘 (탐색할 값과 중간 값을 비교하고, 탐색 범위를 반으로 줄이는 방식)

조건 : 이진 탐색은 정렬된 배열에서 찾고, 균형 이진 트리는 SortedSet 자료구조를 사용했습니다.

 

1. 소스

 

using System;
using System.Collections.Generic;
using System.Diagnostics;

class Program
{
    static void Main()
    {
        int size = 65000;
        int target = 32500;

        // 1. 균형 이진 트리
        SortedSet<int> balancedBinaryTree = new SortedSet<int>();
        for (int i = 1; i <= size; i++)
        {
            balancedBinaryTree.Add(i);
        }

        Stopwatch stopwatch = new Stopwatch();

        stopwatch.Start();
        bool foundInTree = balancedBinaryTree.Contains(target);
        stopwatch.Stop();
        Console.WriteLine($"균형 이진 트리에서 찾는 시간: {stopwatch.ElapsedTicks} ticks");

        // 2. 배열에 담아놓고 바이너리서치
        int[] array = new int[size];
        for (int i = 1; i <= size; i++)
        {
            array[i - 1] = i;
        }

        stopwatch.Restart();
        int index = Array.BinarySearch(array, target);
        stopwatch.Stop();
        Console.WriteLine($"배열에 담아놓고 바이너리서치에서 찾는 시간: {stopwatch.ElapsedTicks} ticks");

        // 찾은 결과 출력
        Console.WriteLine($"균형 이진 트리에서 찾음: {foundInTree}");
        Console.WriteLine($"배열에 담아놓고 바이너리서치에서 찾음: {index >= 0}");
    }
}

 

2. 결과

이진 탐색 (Binary search)가 빠르게 측정이 됐습니다.

균형 이진 트리에서 찾는 시간: 2967 ticks
배열에 담아놓고 바이너리 서치에서 찾는 시간: 2227 ticks
균형 이진 트리에서 찾음: True
배열에 담아놓고 바이너리 서치에서 찾음: True

3. 차이점

배열은 연속된 위치에 저장되어 있어 캐시 히트율이 높습니다. 이를 통해 더 빠른 접근이 가능했습니다. 트리는 노드가 메모리의 임의 위치에 저장될 수 있어, 포인터 참조로 인해 메모리 접근이 더 느릴 수 있습니다.
삽입과 삭제는 균형 이진 트리가 O(log n)의 시간 복잡도로 O(n)의 시간 복잡도에 비해 효율적입니다.

상황에 따라 선택 해서 사용하면 될 것 같습니다.

*캐시 히트율 : 배열이 캐시 메모리의 효율을 잘 활용