doc/MISC.md

   1 # Mathematical background
   2
   3 The main data structure is a full binary tree.
   4
   5 A binary tree is *full* if each of its node has either two or zero children.
   6
   7 If a node has two children it is an internal node, otherwise a leaf.
   8
   9 Fundamental theorem:
  10 Let I be the number of internal nodes and L the number of leaves, then:
  11         L = I + 1
  12
  13 (It can be proved by induction on the number of internal nodes.)
  14
  15 This means that when we add a leaf to the tree (when a window is created), we must also add one internal node.