blob: b2eecc3380adb1ea44392afd7443d93edf01227d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
|
Prove that a binary tree with `k` leaves has height at least `log k`.
```plaintext
tree = h(k)
assert(height(tree) == log k)
for each positive natural number this is true.
```
```c
BTree *h(int k)
{
BTree *tree = rb_tree_initialize();
// assert(true == true);
// generate k leaves with random data
return tree;
}
for (int k = 0; k < 1000; k++) {
assert(height(h(k)) >= log(k))
}
```
```plaintext
n: 3
h: 3
(x)
\
(y)
\
(z)
n: 3
k: 2
h: 2
(y)
/ \
(x) (z)
2^x == 2
```
|
