Пространственная сложность ширины первого поиска бинарного дерева?

Question

Какова будет пространственная сложность поиска в ширину в двоичном дереве? Поскольку он будет хранить только один уровень за раз, я не думаю, что это будет O (n).

Answer 1

Пространственная сложность на самом деле O(n), о чем свидетельствует совершенное двоичное дерево . Рассмотрим пример глубины четыре:

                  ____________________14____________________
                 /                                          \
         _______24_________                        __________8_________
        /                  \                      /                    \
     __27__             ____11___             ___23___              ____22___
    /      \           /         \           /        \            /         \
  _4        5        _13         _2        _17        _12        _26         _25
 /  \      / \      /   \       /  \      /   \      /   \      /   \       /   \
29   0    9   6    16    19    20   1    10    7    21    15   18    30    28    3

Обратите внимание, что количество узлов на каждой глубине задается как

depth num_nodes
0     1
1     2
2     4
3     8
4     16

В общем, на глубине d узлов *1013*. Общее количество узлов в идеальном двоичном дереве глубиной d составляет n = 1 + 2^1 + 2^2 + ... + 2^d = 2^(d+1) - 1. Когда d уходит в бесконечность, 2^d/n уходит в 1/2. Таким образом, примерно половина всех узлов находится на самом глубоком уровне. Начиная с n/2 = O(n), сложность пространства линейна по количеству узлов.

---

Кредит иллюстрации показан в пакете binarytree .