BST: анализ с учетом ссылки найти предыдущий

Question

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

public static TreeNode findPredecessor(TreeNode node) {
    if (node == null)
        return null;

    if (node.getLeft() != null)
        return findMaximum(node.getLeft());

    TreeNode parent = node.getParent();

    TreeNode y = parent;
    TreeNode x = node;
    while (y != null && x == y.getLeft())
    {
        x = y;
        y = y.getParent();
    }


    return y;
}

Мне было просто интересно, что делает эта часть кода.

TreeNode y = parent;
TreeNode x = node;
while (y != null && x == y.getLeft())
{
    x = y;
    y = y.getParent();
}

return y;

что именно происходит в середине цикла while?

Спасибо!

Answer 1

При поиске предшественника есть два случая.

1. Если у узла есть ненулевое левое поддерево, его предшественник будет самым большим узлом в левом поддереве.
2. Если у него нет левого поддерева, найдите первый узел, который является правым потомком , если его его родитель (перемещение вверх, начиная с интересующего узла).Затем родительский узел является предшественником.

---

TreeNode y = parent; //parent is node.getParent(); i.,e parent of node.
TreeNode x = node; //assigns node to x
while (y != null && x == y.getLeft()) 
{
    x = y; //the parent becomes the current node 
    y = y.getParent(); //the parent is the parent of the parent
}

return y;

Условие while (y != null && x == y.getLeft()) говорит, что продолжение продолжается до тех пор, пока

• parent не являетсяnull и

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

• Возвращает родительский узел как результат.

Давайте рассмотрим это на примере

    40
 30    50
          60
        55
      54
    53

Обход по порядку дает

30 40 50 53 54 55 60

Предшественник 55 - самый большой узел в его левом поддереве - 54

Предшественник 53 - узел, при переходе вверх, то есть правый потомок его родителя - 60 - его родитель 50 - это результат.