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

Question

Я хочу найти узел - V, в бинарном дереве поиска, которое соответствует одному (и только один) из следующих условий: левое поддерево

• Ви включает по меньшей мере, одно значение, которое меньше, чем против
• правое поддерево V включает в себя по меньшей мере одно значение, которое больше, чем против

Я знаю, что именно один узел v существует в моем дереве - T, и я хотел бы Найди это.

Я думал об этом алгоритме, учитывая дерево T:

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

Итак, мой первый вопрос: правильно ли алгоритм? делает ли это то, что, как предполагается? Во-вторых, мне нужно, чтобы это было во временной сложности O(n), это происходит?

Если я ошибаюсь, я хотел бы получить правильный алгоритм для этой задачи

Answer 1

Ваш алгоритм не делает то, что он должен. Рассмотрим следующее дерево:

 3 
    /\ 
    2 5 
    /\ 
    1 4 

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

Answer 2

Вы можете реализовать алгоритм вполне буквально, переводя состояние в код:

boolean hasValueSmallerThan(Vertex startFrom, int value) { 
    return 
     this.value < value 
    || (startFrom.left != null && hasValueSmallerThan(startFrom.left, value)) 
    || (startFrom.right != null && hasValueSmallerThan(startFrom.right, value)); 
} 
boolean hasValueGreaterThan(Vertex startFrom, int value) { 
    return 
     this.value > value 
    || (startFrom.left != null && hasValueGreaterThan(startFrom.left, value)) 
    || (startFrom.right != null && hasValueGreaterThan(startFrom.right, value)); 
} 
Vertex findInvalid(Vertex startFrom) { 
    if (startFrom.left == null && startFrom.right == null) { 
     return null; 
    } 
    // v's right subtree includes at least one value that is bigger than v 
    if (startFrom.left == null) { 
     boolean checkRight = hasValueGreaterThan(startFrom.right, this.value); 
     return (checkRight) ? this : findInvalid(startFrom.right); 
    } 
    // v's left subtree includes at least one value that is smaller than v 
    if (startFrom.right == null) { 
      boolean checkLeft = hasValueSmallerThan(startFrom.left, this.value); 
      return (checkLeft) ? this : findInvalid(startFrom.left); 
    } 
    // If we are here, both subrtees are non-null 
    boolean leftIsInvalid = hasValueSmallerThan(startFrom.left, this.value); 
    boolean rightIsInvalid = hasValueGreaterThan(startFrom.right, this.value); 
    // Return XOR of the two checks, which means "one of the two is true, but not both" 
    if (leftIsInvalid^rightIsInvalid) { 
     return this; 
    } 
    Vertex leftFind = findInvalid(startFrom.left); 
    if (leftFind != null) return leftFind; 
    return findInvalid(startFrom.right); 
} 

Эта реализация очень проста: она имеет два рекурсивных хелперы, hasValueSmallerThan и hasValueGreaterThan, которые используются при рекурсивном findInvalid.

Большая часть кода содержит ситуации, когда одно из двух поддеревьев пуст. Помимо этого, это простой перевод требований в код.