Mathematic Introduction

Binary Tree

A binary tree is a tree data structure in which each node has at most two child nodes, usually distinguished as “left” and “right”. Nodes with children are parent nodes, and child nodes may contain references to their parents. Outside the tree, there is often a reference to the “root” node (the ancestor of all nodes), if it exists. Any node in the data structure can be reached by starting at root node and repeatedly following references to either the left or right child.

Types of binary trees

  • A rooted binary tree is a tree with a root node in which every node has at most two children.
  • A full binary tree (sometimes proper binary tree or 2-tree or strictly binary tree) is a tree in which every node other than the leaves has two children.
  • A perfect binary tree is a full binary tree in which all leaves are at the same depth or same level. (This is ambiguously also called a complete binary tree.)
  • A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.

Count of trees

Number of rooted binary trees (t) about depth h
(recurency equation):

t(0) = 1
t(1) = 2
t(2) = 5
t(3) = 26
t(4) = 677
t(5) = 458330

Trees about depth 2: t(2) = 5

Max depth (level) of tree was arbitrary set to 6.
This lead us to number of trees could be used in tournament (joomleague) :

t(6) = 2,1 * 10^11 = 210066388901

Why depth 6?

Choosing depth 6 as a max level in joomleague mean:
Maximum number of teams participated in tournament are 64.
Adding at least 1 team causes incrased depth to value 7 and number of possible brackets to:
t(7) = 4,41 * 10^22 = 44127887000000000000001
So, maybe in next release… :-)

Selection problem

So, joomleague could (automaticaly) generate those terrible number of tree brackets.
The only problem is:
How user select the proper one?
Of course most popular could be grouped in lists, eg:
simple_ko: 2, 4, 8, 16, 32, 64

but problem occurs with (for example) 9 teams simple_ko

User could said: I wanna those 2 teams at the bottom:
Another said: In my league 9 teams played like this: (still 9 teams)

Global Solution

Algorithm for selecting one of 210066388901 brackets:
1. Determine depth (level) of Your bracket.
(theoretical options are: 0, 1, 2, 3, 4, 5, 6, but make sense only one of: 2, 3, 4, 5, 6 )
here are example of depth 4 brackets:


Detiled instructions but with another tree …


In Other Languages
Translations of this page:
QR Code
QR Code doc:math (generated for current page)