How do you count the number of balanced binary search trees with N nodes? Balanced as in the left subtree size and the right subtree size differ by at most 1.
Thanks!
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3985 |
| 2 | jiangly | 3814 |
| 3 | jqdai0815 | 3682 |
| 4 | Benq | 3529 |
| 5 | orzdevinwang | 3526 |
| 6 | ksun48 | 3517 |
| 7 | Radewoosh | 3410 |
| 8 | hos.lyric | 3399 |
| 9 | ecnerwala | 3392 |
| 9 | Um_nik | 3392 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 169 |
| 2 | maomao90 | 162 |
| 2 | Um_nik | 162 |
| 4 | atcoder_official | 161 |
| 5 | djm03178 | 158 |
| 6 | -is-this-fft- | 157 |
| 7 | adamant | 155 |
| 8 | awoo | 154 |
| 8 | Dominater069 | 154 |
| 10 | luogu_official | 150 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.12.2024 17:40:14 (i1).
Десктопная версия, переключиться на мобильную.
При поддержке
If I am not wrong, then this number series might help — It is the number of possible balanced binary search tree with $$$N$$$ unique nodes
I don't think that is correct. 4 nodes has 4 trees N<=1e18 by the way
I think your mean was to deal with the problem of counting such balanced tree with exact $$$N$$$ nodes
Lets take a subtree $$$G_0$$$ with $$$N$$$ nodes, including root. Since the subtree construction depend on left and right subsubtree, we have:
Lets $$$f(x) = $$$ numbers of balanced tree with $$$N$$$ nodes, from above observation, we have
$$$f(0) = 1$$$
$$$f(1) = 1 = f(0)^2$$$
$$$f(2) = 2 = 2 \times f(1) \times f(0)$$$
$$$f(3) = 1 = f(1)^2$$$
$$$f(4) = 4 = 2 \times f(2) \times f(1)$$$
$$$f(5) = 4 = f(2)^2$$$
$$$f(6) = 4 = 2 \times f(3) \times f(2)$$$
$$$ f(0) = 1$$$
$$$ f(1) = 1$$$
$$$ f(2) = 2$$$
$$$ f(3) = 1$$$
$$$ f(4) = 4$$$
$$$ f(5) = 4$$$
$$$ f(6) = 4$$$
$$$ f(7) = 1$$$
$$$ f(8) = 8$$$
$$$ f(9) = 16$$$
$$$ f(10) = 32$$$
$$$ f(11) = 16$$$
$$$ f(12) = 32$$$
$$$ f(13) = 16$$$
$$$ f(14) = 8$$$
$$$ f(15) = 1$$$
$$$ f(16) = 16$$$
$$$ f(17) = 64$$$
$$$ f(18) = 256$$$
$$$ f(19) = 256$$$
$$$ f(20) = 1024$$$
$$$ f(21) = 1024$$$
$$$ f(22) = 1024$$$
$$$ f(23) = 256$$$
$$$ f(24) = 1024$$$
$$$ f(25) = 1024$$$
$$$ f(26) = 1024$$$
$$$ f(27) = 256$$$
$$$ f(28) = 256$$$
$$$ f(29) = 64$$$
$$$ f(30) = 16$$$
$$$ f(31) = 1$$$
$$$ f(32) = 32$$$
$$$ f(33) = 256$$$
$$$ f(34) = 2048$$$
$$$ f(35) = 4096$$$
$$$ f(36) = 32768$$$
$$$ f(37) = 65536$$$
$$$ f(38) = 131072$$$
$$$ f(39) = 65536$$$
$$$ f(40) = 524288$$$
$$$ f(41) = 1048576$$$
$$$ f(42) = 2097152$$$
$$$ f(43) = 1048576$$$
$$$ f(44) = 2097152$$$
$$$ f(45) = 1048576$$$
$$$ f(46) = 524288$$$
$$$ f(47) = 65536$$$
$$$ f(48) = 524288$$$
$$$ f(49) = 1048576$$$
$$$ f(50) = 2097152$$$
$$$ f(51) = 1048576$$$
$$$ f(52) = 2097152$$$
$$$ f(53) = 1048576$$$
$$$ f(54) = 524288$$$
$$$ f(55) = 65536$$$
$$$ f(56) = 131072$$$
$$$ f(57) = 65536$$$
$$$ f(58) = 32768$$$
$$$ f(59) = 4096$$$
$$$ f(60) = 2048$$$
$$$ f(61) = 256$$$
$$$ f(62) = 32$$$
$$$ f(63) = 1$$$
$$$ f(64) = 64$$$
$$$ f(65) = 1024$$$
$$$ f(66) = 16384$$$
$$$ f(67) = 65536$$$
$$$ f(68) = 1048576$$$
$$$ f(69) = 4194304$$$
$$$ f(70) = 16777216$$$
$$$ f(71) = 16777216$$$
$$$ f(72) = 268435456$$$
$$$ f(73) = 1073741824$$$
$$$ f(74) = 4294967296$$$
$$$ f(75) = 4294967296$$$
$$$ f(76) = 17179869184$$$
$$$ f(77) = 17179869184$$$
$$$ f(78) = 17179869184$$$
$$$ f(79) = 4294967296$$$
$$$ f(80) = 68719476736$$$
$$$ f(81) = 274877906944$$$
$$$ f(82) = 1099511627776$$$
$$$ f(83) = 1099511627776$$$
$$$ f(84) = 4398046511104$$$
$$$ f(85) = 4398046511104$$$
$$$ f(86) = 4398046511104$$$
$$$ f(87) = 1099511627776$$$
$$$ f(88) = 4398046511104$$$
$$$ f(89) = 4398046511104$$$
$$$ f(90) = 4398046511104$$$
$$$ f(91) = 1099511627776$$$
$$$ f(92) = 1099511627776$$$
$$$ f(93) = 274877906944$$$
$$$ f(94) = 68719476736$$$
$$$ f(95) = 4294967296$$$
$$$ f(96) = 68719476736$$$
$$$ f(97) = 274877906944$$$
$$$ f(98) = 1099511627776$$$
$$$ f(99) = 1099511627776$$$
$$$ f(100) = 4398046511104$$$
Since every value is the power of 2, we also have this generator for a funny graph
It is A110316 OEIS
Wow! Thanks! That helped a lot!
Then give me contribution UwU
Just kidding, by the way, since there is $$$O(log_2(n))$$$ solution by matrix multiplication and $$$O(log_2^2(n))$$$ solutions by recursive-dp, do you think there is an $$$O(1)$$$ solution by combinatoric or something ?