선택트리는 승자트리(Winner Tree)와 패자트리(Loser Tree)로 구분된다. 승자트리 (Winner Tree) n개의 외부 노드(external node)와 n-1개의 내부 노드(internal node)를 가지는 완전 이진 트리(Complete Binary Tree) 이다. 외부 노드는 토너먼트의 플레이어라고 생각하면되고 내부 노드는 플레어이 간의 경기라고 생각하면 된다. 가장 작은 수가 우승한다. 이 트리의 루트는 최종 승자이다. 승자트리를 이용한 정렬 n개의 수를 정렬하려고 할때, Winner Tree를 가장 작은 수가 우승하는 트리라고 정하면, n개의 수를 트리의 외부 노드레 넣고 승자를 찾는다. 정렬된 숫자들을 넣은 배열을 sortedArr이라 한다면, 승자는 가장 작은수 이므로 승자..

이진탐색트리(Binary Search Tree) 란? 이진탐색트리의 정의는 다음과 같다. 이진트리(Binary Tree)이다. 각 노드는 (key, value)쌍을 가지고 있다. 임의의 노드 x에 대해서 x의 왼쪽 서브트리에 있는 노드들의 key는 모두 x보다 작고 오른쪽 서브트리에 있는 노드들의 key는 모두 x보다 크다. 이진탐색트리의 연산 이진탐색트리는 탐색, 삽입, 수정, 삭제의 연산을 가진다. IsEmpty() Get(key) -> 탐색 Insert(key, value) -> 삽입, 수정 Delete(key) -> 삭제 Get : 탐색 시간복잡도: O(n) (n은 Tree의 원소수) T Get(T item) { TreeNode ptr; ptr = root; while(ptr != null) { ..