Найти преемника без использования родительского указателя

Преемником элемента в BST является преемник элемента в порядке сортировки, определяемом неупорядоченным обходом. Поиск преемника, когда каждый узел имеет указатель на его родительский узел, представлен в учебнике по алгоритмам CLRS (Introduction to Algorithms by MIT Press).

Идея найти преемника здесь такова: если правое поддерево узла x не пусто, преемник x является минимальным элементом в правом поддереве. В противном случае преемник является младшим предком x, чей левый потомок также является предком x (при условии, что узел является предком самого себя).

Можем ли мы найти преемника, не используя указатель на родительский узел?

Иногда наш узел дерева не имеет этого указателя. Я боролся пару часов, но не могу написать правильный код.


algorithm binary-search-tree
person szli    schedule 25.09.2010    source источник
comment
Закрыт как дубликат In Order Successor in Binary Search Tree, хотя этот пост не имеет ограничения на его поиск без использования родителя указатели, в некоторых ответах не используются родительские указатели (пример).   -  person Bernhard Barker    schedule 31.12.2017

Ответы (5)


arrow_upward
4
arrow_downward

Это должно работать:

TREE-SUCCESSOR(T, x)
  if right[x] != NIL
    return TREE-MINIMUM(right[x])
  else
    return FIND-TREE-SUCCESSOR(root[T], x, NIL)

FIND-TREE-SUCCESSOR(y, x, c)
  if y = x
    return c
  if key[x] < key[y]
    return FIND-TREE-SUCCESSOR(left[y], x, y)
  else
    return FIND-TREE-SUCCESSOR(right[y], x, c)

FIND-TREE-SUCCESSOR сохраняет в c (кандидата) последний узел, в котором мы повернули налево.

person Sheldon L. Cooper    schedule 26.09.2010
comment
Ваш ответ очень хороший, и я думаю, что он правильный. Я пытался сделать то же самое здесь, т. е. начать с корня и отслеживать кандидата, но мне не удалось придумать красивую рекурсивную форму, как вы здесь показываете. Спасибо. - person szli; 26.09.2010
comment
@Sheldon, последнее утверждение должно быть вне if, а then должно быть удалено. - person Hank; 03.10.2013
comment
Этот алгоритм неверен. Во-первых, он не проходит простой тест: если x = root, он всегда возвращает null. Во-вторых, представьте, что у вас есть дерево с самым левым узлом, у которого есть родственный правый узел с левым дочерним элементом. Алгоритм всегда неправильно возвращал родительский узел как преемник самого левого узла. - person Shital Shah; 14.08.2014

arrow_upward
7
arrow_downward

Вдохновленный решением Шелдона, это нерекурсивная версия решения.


if (right[x]  != NIL)
    return min(right[x]);
else
{
    candidate = NIL;
    y = root; 
    while  (y!= x) // y is used as a probe

        if (key[x] < key[y])
            {
            candidate = y;
            y = y ->left;

             }
        else
            y = y->right;
}
return candidate;
Если кандидат == NIL, x является максимальным в дереве и не имеет преемника.

person szli    schedule 26.09.2010

arrow_upward
2
arrow_downward

Я нашел элегантное решение для преемника по порядку без родительского указателя здесь -> http://www.geeksforgeeks.org/archives/9999

Идея

1. Если узел имеет правое поддерево, то его преемник является наименьшим элементом в правом поддереве.

  1. Если правое поддерево узла пусто, то его преемником является один из его предков, которого можно найти сверху вниз без родительского указателя по следующему алгоритму:

пусть изначально current_node будет корневым, succ_node = null;

case1: если элемент поиска меньше, чем current_node, то текущий элемент является потенциальным преемником — поместите succ_node в current_node и переместите current_node в его левый узел (поскольку элемент поиска находится в левом поддереве)

case2: если элемент поиска больше, чем current_node, это не потенциальный преемник (как меньший элемент может быть преемником?). Так что не нужно размещать succ_node здесь, а переместите current_node вправо.

продолжайте повторять процесс, пока не достигнете нуля или самого элемента и не вернете succ_node.

person Balaji    schedule 13.09.2012

arrow_upward
0
arrow_downward

Если у вас нет доступа к указателю на родительский узел, вам нужно знать, кто является отцом. Если вы этого не знаете, как вы могли взобраться на дерево?

person Loïc Février    schedule 25.09.2010
comment
Мы можем предположить, что у нас есть «корень», доступный для метода, который находит преемника по порядку. Вместо того, чтобы подниматься по дереву от узла «X», мы будем спускаться по дереву, используя «корень», и, прежде чем мы сможем достичь «X», мы будем продолжать отмечать «вероятного» преемника по порядку. В конце мы можем вернуть результат. - person user1639485; 22.11.2014

arrow_upward
0
arrow_downward

Рекурсивное Java-решение может выглядеть следующим образом:

public Integer successor(Integer value) {
    Node n = succ(root, value, null);
    if (null != n) {
       return n.value;
    }
    return null;
}

private Node succ(Node n, Integer x, Node p) {
    if (null == n) {
        return null;
    }

    if (x < n.value) {
        return succ(n.left, x, n);
    } else if (x > n.value) {
        return succ(n.right, x, p);
    }
    if (null != n.right) {
        return min(n.right);
    }
    return p;
}

Как клиент, мы просто передаем значение узла, от которого мы хотим узнать преемника. Затем мы начинаем поиск с корня, пока не найдем искомое значение. Теперь есть два случая:

  1. Если у текущего узла есть правый дочерний элемент, то преемником является наименьший элемент в правом поддереве текущего узла.
  2. В противном случае это был узел p (родительский указатель), который обновлялся только тогда, когда мы шли влево в дереве.
person nastra    schedule 09.09.2013