Quick links
Latest articles
Internship
Members
New...
Algorithms
Discrete Mathematics
Big data
Languages
C
C++
C++ STL
Java
Data Structure
C#.Net
Android
Kotlin
SQL
Web
PHP
Python
JavaScript
CSS
Ajax
Node.js
Web prog.
Programs
C
C++
DS
Java
C#
Python
Aptitude
C
C++
Java
DBMS
Interview
C
Embedded C
Java
SEO
HR
CS Subjects
CS Basics
O.S.
Networks
DBMS
Embedded Systems
Cloud Computing
Machine learning
CS Organizations
Linux
DOS
More...
Articles
Puzzles
News/Updates

Home » Algorithms

Tournament Tree and their properties



In this article we are going to learn about the tournament tree, types of tournament tree, application of tournament tree and their properties.
Submitted by Prerana Jain, on June 29, 2018

Tournament Tree

Tournament tree is a complete binary tree n external nodes and n-1 internal nodes. The external nodes represent the players and internal nodes represent the winner of the match between the two players.

Properties of Tournament Tree

  1. It is rooted tree i.e. the links in the tree and directed from parents to children and there is a unique element with no parents.
  2. The key value of the parent node has less than or equal to that node to general any comparison operators can be used as long as the relative values of parent-child are invariant throughout the tree. The tree is a parent ordering of the keys.
  3. Trees with a number of nodes not a power of 2 contain holes which is general may be anywhere in the tree.
  4. Tournament tree is a proper generalization of heaps which restrict a node to at most two children.
  5. The tournament tree is also called selection tree.
  6. The root of the tournament tree represents overall winner of the tournament.

Types of tournament Tree

There are mainly two type of tournament tree,

  1. Winner tree
  2. Loser tree

1) Winner tree

The complete binary tree in which each node represents the smaller or greater of its two children is called a winner tree. The smallest or greater node in the tree is represented by the root of the tree. The winner of the tournament tree is the smallest or greatest n key in all the sequences. It is easy to see that the winner tree can be computed in O(logn) time.

Example: Consider some keys 3, 5, 6, 7, 20, 8, 2, 9

We try to make minimum or maximum winner tree

Winner tree

Winner tree (minimum)

2) Loser Tree

The complete binary tree for n players in which there are n external nodes and n-1 internal nodes then the tree is called loser tree. The loser of the match is stored in internal nodes of the tree. But in this overall winner of the tournament is stored at tree [0]. The loser is an alternative representation that stores the loser of a match at the corresponding node. An advantage of the loser is that to restructure the tree after a winner tree been output, it is sufficient to examine node on the path from the leaf to the root rather than the sibling of nodes on this path.

Example: Consider some keys 10, 2, 7, 6, 5, 9, 12, 1

Step 1) We will first draw min winner tree for given data.

Loser tree

Step 2) Now we will store losers of the match in each internal nodes.

Loser tree 1

Application of Tournament Tree

  1. It is used for finding the smallest and largest element in the array.
  2. It is used for sorting purpose.
  3. Tournament tree may also be used in M-way merges.
  4. Tournament replacement algorithm selection sort is used to gather the initial run for external sorting algorithms.





Quick links:
C FAQ(s) C Advance programs C/C++ Tips & Tricks Puzzles JavaScript CSS Python Linux Commands PHP Android Articles More...

Featured post:
Introduction to Linux (Its modes, Safety, Most popular Applications)
Linux Best Distribution Software (Distros) of 2018

Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.

Comments and Discussions



Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing » Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates


© https://www.includehelp.com (2015-2018), Some rights reserved.