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