5

Есть задачка. Имеется бинарное дерево. Требуется определить, является ли это дерево бинарным деревом поиска. Желательно представить решение на языке С++ или С. Оцениваются временная и пространственная сложность алгоритма, а так же универсальность подхода.

3 ответа 3

6

UPD: моя неправда, исправляю.

Предположим, что дерево определено так:

struct BinaryTreeNode {
    BinaryTreeNode(int val) : leftChild(NULL), rightChild(NULL), 
        parent(NULL), value(val) {}

    BinaryTreeNode * leftChild;
    BinaryTreeNode * rightChild;
    BinaryTreeNode * parent;
    int value;
};

Тогда алгоритм проверки будет следующим:

bool isBST(BinaryTreeNode * root)
{
    return isBST_(root, 0, 0);
}

bool isBST_(BinaryTreeNode * node, BinaryTreeNode * minParent, BinaryTreeNode * maxParent)
{
    if (minParent && minParent->value >= node->value)
        return false;
    if (maxParent && maxParent->value <= node->value)
        return false;
    if (node->leftChild != 0 && !isBST_(node->leftChild, minParent, node))
        return false;
    if (node->rightChild != 0 && !isBST_(node->rightChild, node, maxParent))
        return false;
    return true;    
}

Временная сложность O(n), где n — количество узлов в дереве. Пространственная сложность O(h), где h — глубина дерева.

3
  • 1
    Не катит. Это мы проверили относительно значения в корне дерева, а между элементами инвариант не проверяется, если я не ошибаюсь. 6 янв 2011 в 19:51
  • Хм, а 2 рекурсивных вызова isBST там зачем стоят? Эта функция обходит все элементы дерева, проверяя инвариант в каждом.
    – ofitserov
    6 янв 2011 в 21:29
  • 2
    Это не так. Вы проверите все значения относительно корня, но не относительно друг друга. Инвариант должен выполняться между всеми узлами дерева. 6 янв 2011 в 22:13
4

Обходим дерево по правилу ЛКП, по дороге проверяем, получается ли возрастающая последовательность (или убывающая, можно определить по первым двум неравным значениям). Если не получается - то не дерево поиска. Как то так.

3

http://www.structur.h1.ru/derevo.htm - тут написанна структура дерева по сути ваша задача хорошо решается рекурсией рекурсивно идете вниз по дереву если при проверке оказывается что это не дерево - throw SomeError; если все нормально - то никаких исключений кидать не надо рекурсия развернется свернется и говорите что все ОК

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими условиями использования и подтверждаете, что прочитали и поняли наши политику конфиденциальности и нормы поведения.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.