BST1 Unity 개발자를 위한 C# BST(Binary Search Tree, 이진 탐색 트리) 구현 이진 탐색 트리(Binary Search Tree, 이하 BST)는 이진 트리 구조에 정렬 규칙을 더한 자료구조입니다. 각 노드는 최대 두 개의 자식을 가지며, 모든 노드에 대해 다음 조건을 만족합니다.어떤 노드 X에 대해, 왼쪽 서브 트리의 모든 키 (X의 왼쪽 자식들은 전부 X보다 작음)어떤 노드 X에 대해, 오른쪽 서브트리의 모든 키 > X의 키 (X의 오른쪽 자식들은 전부 X보다 큼)이 규칙 덕분에 BST는 탐색(Search), 삽입(Insert), 삭제(Remove)를 평균적으로 O(log n)에 수행할 수 있습니다. 다만 삽입과 삭제가 반복되면서 트리가 한쪽으로 심하게 치우치면, 높이가 커지면서 최악의 경우 O(n)까지 성능이 나빠질 수 있습니다. 이런 한계를 줄이기 위해 AVL(Adelso.. 2025. 12. 11. 이전 1 다음
