Warning: session_write_close(): write failed: No space left on device (28) in /var/www/joomleague/dokuwiki/doku.php on line 116

Warning: session_write_close(): Failed to write session data (files). Please verify that the current setting of session.save_path is correct (/var/lib/php5/sessions) in /var/www/joomleague/dokuwiki/doku.php on line 116
doc:math - JoomLeague

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 binary trees (t) about depth h
(recurency equation):


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 = 210066380001

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)

Solution

Algorithm for selecting one of 210066380001 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 4 depth brackets:

  1. (soon)

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