Найдите недостающее значение в полном BST, заполненном каждым числом от 1 до 2^K, где K — количество уровней
Пусть K — количество уровней в бинарном дереве поиска. Следовательно, максимальное количество узлов, которое я могу иметь, равно (2^K)-1. У меня есть полное двоичное дерево (т.е. можно сказать, что каждый уровень полностью заполнен), узлы которого заполнены каждым значением от 1 до (2^k), без дублирования. Поскольку имеется (2^K)-1 доступных узлов для заполнения, но доступных значений 2^K, в бинарном дереве поиска должно отсутствовать одно значение от 1 до (2^K). Помогите мне разработать алгоритм, позволяющий найти недостающее значение. Это должно быть с временной сложностью O (K). По сути, просто пройдя каждый уровень один раз.
Это одна из моих проблем с назначением DSA. У меня есть хорошая реализация, использующая обход по порядку, но это не O(K), а O(2^K)/O(n). Я просто не уверен, выполнимо ли это вообще при временной сложности O(K).
Например, для K=4 я заполняю двоичное дерево значениями от 1 до 2^4=16. Но узлов всего 15, поэтому один не учитывается. В приведенном ниже примере я не учитываю число 14. Как определить, что число 14 отсутствует за время O(K)?
8 k=1
/ \
4 12 k=2
/ \ / \
2 6 10 15 k=3
/ \ / \ / \ / \
1 3 5 7 9 11 13 16 k=4
Например, если отсутствует значение < 8, как вы думаете, возможно ли, что 8 является корнем?
Хм, хорошая зацепка. Позвольте мне попробовать!
Ответы 1
Следующий псевдокод не требует пояснений и явно работает в O(K):
findMissing(node)
if isLeaf(node) {
if node.value % 2 == 0
return node.value - 1
else
return node.value + 1
}
else {
if node.value % 2 == 0
return findMissing(node.rightChild)
else
return findMissing(node.leftChild)
}
Интуиция подсказывает, что при фиксированном K каждый узел дерева может иметь только два возможных значения. Например, когда K=4, корень может быть либо 8, либо 9, крайний левый лист может быть либо 1, либо 2 и т. д. Следовательно, мы можем использовать четность значения узла, чтобы угадать, какое поддерево является «несбалансированным».
Удивительный. Большое спасибо! Я понимаю большую часть этого, но меня просто смущает, почему (математически) мы добавляем 1, если %2!=1, но вычитаем, если %2==0, в базовом случае. Есть ли в этом математическая интуиция? Заранее спасибо!
@fan_fiesty Отличный вопрос! Например, подумайте о крайнем левом листе: он может быть либо 1, либо 2, поэтому, если он четный, вы получаете 1 путем вычитания, иначе вы получаете 2 путем сложения. С другой стороны, для крайнего правого листа у вас может быть либо 15, либо 16, поэтому, если он четный, вы получаете 15 путем вычитания, иначе вы получаете 16 путем сложения. Это свойство можно обобщить для каждого листа (обратите внимание, что «по умолчанию» их значениями являются все нечетные числа в дереве, и каждый лист можно заменить только своим преемником).
Я предлагаю нарисовать еще несколько деревьев с другим недостающим значением. Должен появиться шаблон того, что отображается в родительских узлах, когда нижний узел отсутствует.