여기에서 토너먼트 트리, 승자 및 패자 트리를 볼 수 있습니다. 토너먼트 트리는 n개의 외부 노드와 n – 1개의 내부 노드가 있는 완전한 이진 트리입니다. 외부 노드는 플레이어를 나타내고 내부 노드는 두 플레이어 간의 경기 승자를 나타냅니다. 이 트리는 선택 트리라고도 합니다.
토너먼트 트리에는 몇 가지 속성이 있습니다. 다음과 같습니다 -
-
이 나무는 뿌리가 있습니다. 따라서 트리의 링크와 부모에서 자식으로의 경로를 지정하고 부모가 없는 고유한 요소가 있습니다.
-
부모 값은 모든 비교 연산자에 대해 해당 노드보다 작거나 같으며, 부모와 자식의 상대 값이 트리 전체에서 변하지 않는 한 사용할 수 있습니다.
-
노드 수가 2의 거듭제곱이 아닌 트리에는 구멍이 있습니다. 구멍은 나무의 어느 곳에나 있을 수 있습니다.
-
이 트리는 바이너리 힙의 적절한 일반화입니다.
-
루트는 토너먼트의 전체 승자를 나타냅니다.
토너먼트 트리에는 두 가지 유형이 있습니다 -
-
우승자 트리
-
느슨한 나무
승자 트리
승자 트리는 각 노드가 두 자식 중 더 작거나 더 큰 것을 나타내는 완전한 이진 트리이며 승자 트리라고 합니다. 루트는 트리의 가장 작거나 큰 노드를 보유하고 있습니다. 토너먼트 트리의 승자는 모든 시퀀스에서 가장 작거나 큰 n 키입니다. 위너 트리가 O(log n) 시간에 형성될 수 있음을 쉽게 알 수 있습니다.
예 − 3, 5, 6, 7, 20, 8, 2, 9와 같은 키가 있다고 가정합니다.
느슨한 나무
느슨한 트리는 n개의 외부 노드와 n – 1개의 내부 노드가 있는 n명의 플레이어에 대한 완전한 이진 트리입니다. 일치하는 쪽이 더 느슨한 쪽이 내부 노드에 저장됩니다. 그러나 이 전체 승자는 tree[0]에 저장됩니다. 느슨한 사람은 해당 노드에서 일치의 느슨한 사람을 저장하는 대체 표현입니다. 루저의 장점은 승자 트리가 출력된 후 트리를 재구성하려면 이 경로에 있는 노드의 형제가 아닌 리프에서 루트로 경로의 노드를 검사하는 것으로 충분하다는 것입니다.
예 − 더 느슨한 트리를 만들려면 먼저 승자 트리를 만들어야 합니다.
10, 2, 7, 6, 5, 9, 12, 1과 같은 키가 있다고 가정합니다. 따라서 먼저 최소 승자 트리를 만듭니다.
이제 각 내부 노드에 더 루즈한 경기를 저장할 것입니다.
