Числа в двоичном дереве поиска (BST) добавляются к определенному значению

Question

Учитывая BST, возможно ли найти два числа, которые складываются до заданного значения, за O (n) время и мало дополнительной памяти. Из-за небольшого количества дополнительной памяти подразумевается, что вы не можете скопировать весь BST в массив.

Answer 1

Это может быть выполнено за O (n) время и O (1) дополнительную память, если у вас есть как дочерние, так и родительские указатели.Вы сохраняете два указателя, x и y, и начинаете x с минимального элемента, а y с максимума.Если сумма этих двух элементов слишком мала, вы перемещаете x к его преемнику, а если он слишком высок, вы перемещаете y к его предшественнику.Вы можете сообщить об ошибке, если x указывает на элемент большего размера, чем y.Каждое ребро в дереве пересекается не более двух раз для общего количества O (n) обходов ребер, и ваше единственное использование памяти - это два указателя.Без родительских указателей вам нужно запомнить последовательность предков до корня, которая, по крайней мере, Omega (log n) и, возможно, выше, если дерево не сбалансировано.

Чтобы найти преемника, вы можете использовать следующеепсевдокод (аналог кода для предшественника):

succ(x) {
  if (x.right != null) {
    ret = x.right;
    while (ret.left != null) ret = ret.left;
    return ret;
  } else {
    retc = x;
    while (retc.parent != null && retc.parent < x) retc = retc.parent;
    if (retc.parent != null && retc.parent > x) return retc.parent;
    else return null;
  }
}

Answer 2

Я думаю, что jonderry очень близок, но родительские указатели требуют памяти \ Omega (n), то есть они существенно увеличивают использование памяти. То, что он делает, - это два скоординированных обхода в противоположных направлениях (от малого к большому и виверса), пытающихся держать сумму всегда близко к цели, и вы можете управлять этим с помощью двух стеков, и стеки могут расти только до глубины дерева и это O (log n). Я не знаю, если это «маленькая» дополнительная память, но, конечно, это меньше дополнительной памяти и o (n). Так что это точно так же, как в собственном комментарии jonderry, но штраф за время выполнения отсутствует, потому что обход бинарного дерева с использованием только стека является хорошо известной и эффективной операцией, которая, безусловно, O (n). Таким образом, у вас есть увеличивающийся итератор ii и убывающий итератор di.

x = ii.next()
y = di.next()
while (true) {
  try:
    if x + y > target {y = di.next()}
    if x + y < target {x = ii.next()}
    if x + y == target {return (x,y)}
  except IterError:
    break
}
return None

Я только что столкнулся с той же проблемой в контексте вычисления псевдомедиана, медианы всех попарных средних в выборке.

Answer 3

Да, если вы проанализируете его как отсортированный массив.