Winner tree in Data Structures
Tree Data structure
A tree is a hierarchical and non-linear data structure with nodes. Each node in the Tree contains a message value and stores the name passed to another ("child") node. Organizing these files is a great way to collect your information and make it easy to reference on your computer. The tree data structure consists of sub-nodes, structural nodes, and a central node connected by the edges, and this data structure also has leaves, branches, and roots attached.
The data in the Tree is plotted so that it is not linear. But they are organized differently, or we can say hierarchically. The trees are considered non-linear as they are hierarchical. Tree data structures differ from queues, stacks, arrays, and linked lists. A tree is a hierarchical structure; data structures have nodes representing and supporting the process. Asynchronous Data Warehouse Tree types collect different levels of information together in a data structure called a root node. All data types are stored in the root location. Each line has a message. We call the branches of the data structure at the bottom of the Tree.
There are many types of trees, and one of them includes the tournament trees, and the winner tree is a type of tournament tree. To understand a tournament tree, we must first know what a complete binary tree is.
Binary tree
It is used for the same data storage purposes and is a unique data structure. This data structure is a particular tree as it can have only a maximum number of two children, i.e., a binary tree can either have 0, 1, or 2 children at any stage. This allows the binary Tree to provide the benefits of an ordinary linked list and array, making searching an element stored easy (as they are sorted data structures).
- Full binary tree – In this binary tree type, each parent node has either two or zero children, respectively. This means that a given node in the binary Tree either has two child nodes or it is itself an external node or leaf node.
- In a full binary tree, we can say that all the nodes, excluding the external or leaf nodes, possess precisely two children.
- In a complete binary tree, we can calculate the number of leaf nodes from the number of internal nodes using the following formula.
L = I + 1
Where 'I' represents the number of internal nodes while 'L' means the number of leaf nodes or external nodes.
- Perfect binary tree - This is another type of binary Tree. The number of nodes in a perfect binary tree can be calculated from the given height or depth of the binary Tree using the following formula
n = 2h – 1
where 'n' represents the number of nodes while 'h' represents the height of the given perfect binary tree.
- Balanced binary tree - If the height of a given binary tree is given by O(logN), when 'N' represents the number of nodes in the Tree, then this binary Tree is treated as a balanced binary tree. The left and right subtree derived from each node in a balanced binary tree are varied by a height of at most one. Examples of Balanced binary trees are the Red-Black Tree, AVL tree (Adelson, Velskii, and Landis tree), etc.
- Degenerate Binary tree – These trees are also called Pathological binary trees, and degenerate binary trees are similar to linked lists in performance.
- Complete binary tree – A binary tree that entirely resides on the left side is also known as a complete binary tree.
- Tournament trees are one of the forms of the complete binary tree.
Tournament Trees
Tournament trees are one of the forms of the complete binary tree. In these Trees, each node is denoted by a player. The last level of the Tree has an 'n-1' number of external nodes representing all the players, and the internal nodes represent either the winner or loser players. Tournament trees are also called Selection trees.
Properties of tournament trees:
- Every internal node's value always equals one of its child nodes.
- If a player or team is absent, their place in the Tournament tree is treated as a hole. If a tournament tree contains less than 2(n + 1) – 1 node, then we can conclude that it has holes.
- A unique path exists between any two selected nodes in a given tournament tree.
- We need 'N – 1' comparisons to find out either the loser or winner of the match.
- A tournament tree is a type of binary heap. (Max or min heap).
Note:
A Binary heap is one of the forms of a complete tree, which means that the Tree has all the levels filled and aligned as left as possible. Thus, a binary heap can be sorted in an array as a complete tree. Binary banks are classified into two types:
- Min heap - If the value of the root node is the minimum value among all the keys present in the binary bank, and this property is recursively actual for all the possible subtrees that can be formed from the given binary heap, then it is treated as a Min heap.
- Max heap – If the root node's value is the maximum value among all the keys present in the binary heap, this property is recursively true for all the possible subtrees that can be formed from the given binary heap. It is treated as a Max heap.
Types of tournament trees:
We have both a winner and a loser in every match. We know that the internal nodes of a tournament tree represent either the winner or loser at each level. Tournament trees are classified based on this criterion. Hence there are two types of tournament trees. They are:
- Loser tree
- Winner tree
Winner Tree
If the internal nodes of a tournament tree represent the winner at each level of the tree data structure, then such type of Tree is treated as a winner tree. Depending on the winning criteria, the greatest or most minor of the child nodes are stored in each internal node. Winner trees are classified into two types, which are
- Maximum winner tree – When the internal nodes of a winner tree represent the greatest value among its child nodes, it is treated as a maximum winner tree.
- Minimum winner tree - When the internal nodes of a winner tree represent the smallest value among its child nodes, it is treated as a maximum winner tree.
The tournament's winner can always be found either as the greatest or smallest among all the other values or players. The time complexity in finding a winner using a winner tree is given by 'O(1)'. The time required to create a winner tree equals 'O(LogN)' when N is the total number of players.
Example of winner tree:
Twelve players participate in a tournament. The players are represented by the numbers 1 to 12, respectively. The players are paired as shown:
Group X: 1, 3, 5, 7, 9, 11 (Matches: 1 -11, 3 – 9, 5 – 7)
Group Y: 2, 4, 6, 8, 10, 12 (Matches: 2 -12, 4 -10, 6 – 8)
Winning criteria: The player with the greatest value is the winner. We shall represent the tournament tree's winner tree (maximum winner tree).
The above Tree represents a Max heap. We can observe that the values of each internal node are either larger than or equal to its child nodes. The largest of all nodes in the tournament tree, the root node of the formed Tree, is considered the winner in the winner tree. In the above case, the winner is '12'.
It can be observed from the above example that every tournament tree is a binary tree. But not all binary trees are tournament trees. But in a binary tree, the parent node can be equal to or greater than any child node.
Applications of Winner tree:
- Winner trees are used for sorting purposes, and winner trees are used to find the largest element in a given array.
- Winner trees can also be used in M-way merges.
Difference Between the Tournament Tree and the Winner Tree
Tournament trees and winner trees both do not mean precisely the same. The winner tree is a type of tournament tree, which means that all winner trees are tournament trees, but all tournament trees are not winner trees. If the internal nodes of a tournament tree represent the winner at each level of the tree data structure, then such type of Tree is treated as a winner tree.