Верификация двоичного дерева поиска

Иногда у нас уже есть двоичное дерево, и нам нужно определить, является ли оно BST (Binary Search Tree, двоичное дерево поиска). Эта проблема имеет простое рекурсивное решение.

Свойство BST - каждый узел в правом поддереве должен быть больше текущего узла, а каждый узел в левом поддереве должен быть меньше текущего узла - является ключом к выяснению, является ли дерево BST или нет. Жадный (greedy) алгоритм - просто обход дерева, на каждом узле проверка, содержит ли узел значение, большее, чем значение у левого дочернего элемента и меньше, чем значение у правого дочернего элемента, - не работает во всех случаях. Рассмотрим следующее дерево:

     20
    /  \
   10   30
       / \
      5   40

В приведенном выше дереве каждый узел удовлетворяет условию, что узел содержит значение, большее, чем его левый дочерний элемент, и меньше, чем его правый дочерний элемент, и все же это не BST: значение 5 находится в правом поддереве узла, содержащего 20 , нарушение свойства BST.

Вместо того, чтобы принимать решение, основанное исключительно на значениях узла и его дочерних элементов, нам также нужна информация, исходящая от родителя. В случае дерева выше, если бы мы могли помнить об узле, содержащем значение 20, мы увидели бы, что узел со значением 5 нарушает контракт свойства BST.

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

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

Рекурсивное решение в C++ может объяснить это дальше:

struct TreeNode {
    int key;
    int value;
    struct TreeNode *left;
    struct TreeNode *right;
};

bool isBST(struct TreeNode *node, int minKey, int maxKey) {
    if (node == NULL) return true;
    if (node->key < minKey || node->key > maxKey) return false;
    
    return isBST(node->left, minKey, node->key-1) && isBST(node->right, node->key+1, maxKey);
}

node->key+1 и node->key-1 сделаны для разрешения только отдельных элементов в BST.

Если мы хотим, чтобы одни и те же элементы также присутствовали, тогда мы можем использовать только node->key в обоих местах.

Первоначальный вызов этой функции может быть примерно таким:

if (isBST(root, INT_MIN, INT_MAX)) {
    puts("This is a BST.");
} else {
    puts("This is NOT a BST!");
}

По сути, мы продолжаем создавать допустимый диапазон (начиная с [MIN_VALUE, MAX_VALUE]) и продолжаем уменьшать его для каждого узла, пока мы рекурсивно снижаемся.

Обход по порядку двоичного дерева поиска возвращает отсортированные узлы. Таким образом, нам нужно только сохранить последний посещенный узел при обходе дерева и проверить, меньше ли его ключ (или меньше/равен, если дубликаты должны быть разрешены в дереве) по сравнению с текущим ключом.

---

Читайте также:

• Структуры данных: двоичное дерево поиска
• Операции с двоичным деревом поиска: поиск
• Операции с двоичным деревом поиска: обход