Complexity Of ReplayOne match at each level that has a match node.
O(log n)
More precisely (log n).
Tournament Trees Winner trees.
Loser Trees.
Tennis ladder.
Winner Trees Complete binary tree with n external nodes and n - 1 internal nodes.
External nodes represent tournament players.
Each internal node represents a match played between its two children; the winner of the match is stored at the internal node.
Root has overall winner.
Winner Tree For 16 Players
player match node
See text for case when number of players is not a power of 2.
O(1) time to play match at each match node.
n - 1 match nodes.
O(n) time to initialize n player winner tree.
Representation
A winner tree of n players requires n-1 internal nodes t[1:n-1]
The players(or external nodes) are represented as an array e[1:n]
t[i] is an index into the array e, t[i] gives the winner of the match played at node i of the winner tree
Applications Sorting.
Put elements to be sorted into a winner tree.
Repeatedly extract the winner and replace by a large value (eg. +).
Comments