Не умею я объяснять
zabivator — 10.02.2010 http://zabivator.livejournal.com/386470.htmlПростая вещь - задали вопрос "Как запихать дерево из миллиарда чисел к 4 гектара?".
Если в ответ идёт уточнения про вид дерева, распределение чисел, требования к операциям - это одна ситуация.
Если в ответ идёт утверждение "дерево так разместить нельзя, всю память у нас займут значения, а связи будет хранить негде" - это совсем другая ситуация. Для второй ситуации логичным возражением является контр-пример с массивом, адресуемым как бинарное сбалансированое дерево высоты 30.
Тогда путь в этом дереве от корня вида Left-Left-Right-Left-Right-Right... превратится в 0 * 2^0 + 0 * 2^1 + 1 * 2^2 + 0 * 2^3 + 1 * 2 ^ 4 + 1 * 2 ^ 4 + ... и так далее.
Мне кажется, что если человек знает про бинарную кучу, то он никогда не заявит, что дерево ЯВНО должно хранить свои связи.
Правда логично?