проверка двоичного дерева поиска на корректность
проверить его на корректность, т.е. все ли элементы из левых поддеревьев меньше текущего узла, а из правого — больше. Я написал следующие ф-ции (в main вызывается только walk ):
bool proverka_l (struct node *nNode, int be) < bool rez = true; if (nNode->value >= be) return false; if (nNode->left) rez = proverka_l (nNode->left, be); if (rez && nNode->right) rez = proverka_l (nNode->right, be); return rez; > bool proverka_r (struct node *nNode, int be) < bool rez = true; if (nNode->value left) rez = proverka_r (nNode->left, be); if (rez && nNode->right) rez = proverka_r (nNode->right, be); return rez; > bool walk (struct node *nNode) < bool rez = true; if (nNode->left) rez = proverka_l (nNode->left, nNode->value); if (rez && nNode->right) rez = proverka_r (nNode->right, nNode->value); if (rez && nNode->left) rez = walk (nNode->left); if (rez && nNode->right) rez = walk (nNode->right); return rez; > Но в случае, если дерево является вырожденным (для каждой ноды имеется только один потомок), то затраты времени оказываются слишком большими. Как ускорить проверку?
Алгоритмическая сложность этой проверки никак не зависит от структуры дерева вообще. Поэтому если в вашем случае вы наблюдаете зависимость от структуры дерева — это именно расходы от «тяжелой» реализации. В данном случае я вижу какую-то странную двойную рекурсию по proverka_ и по walk . Зачем это понадобилось? Все можно сделать за один проход по дереву.
2 ответа 2
Вы реализовали проверку слишком «буквально», т.е. для каждого узла дерева целиком проверяете его поддеревья на неравенство со значением в этом узле. Это очень нерациональный квадратичный (!) подход, который делает много проходов по одним и тем же узлам и много раз проверяет одно и то же, т.е. «генерирует больше тепла, чем света».
Другими словами, данный подход не пользуется транзитивными свойствами сравнения и расплачивается за это ужасной неэффективностью. Уже проверив, что a < b и b < c , ваш алгорим еще рвется "на всякий случай" проверить, что a < c , хотя никакой необходимости в этом нет.
- Алгоритм снизу-вверх
Реализовать рекурсивную функцию, которая возвращает диапазон значений, хранящихся в [под]дереве. На обратном ходе рекурсии для каждого узла проверять, что диапазон значений левого поддерева целиком лежит «слева» от значения узла, а диапазон значений правого поддерева целиком лежит «справа» от значения узла. Если хоть где-то в дереве эти условия не выполняются — дерево составлено некорректно.
bool get_and_check_tree_range(const struct node *root, int *lo, int *hi) < assert(root != NULL && lo != NULL && hi != NULL); *lo = *hi = root->value; if (root->left != NULL) < int left_lo, left_hi; if (!get_and_check_tree_range(root->left, &left_lo, &left_hi)) return false; assert(left_lo root->value) return false; *lo = left_lo; > if (root->right != NULL) < int right_lo, right_hi; if (!get_and_check_tree_range(root->right, &right_lo, &right_hi)) return false; assert(right_lo value) return false; *hi = right_hi; > return true; > int full_lo, full_hi; if (root == NULL || get_and_check_tree_range(root, &full_lo, &full_hi)) /* Все в порядке */; else /* Дерево не упорядочено */; bool check_tree_in_range(const struct node *root, int lo, int hi) < assert(lo value < lo || root->value > hi) return false; return check_tree_in_range(root->left, lo, root->value) && check_tree_in_range(root->right, root->value, hi); > if (check_tree_in_range(root, INT_MIN, INT_MAX)) /* Все в порядке */; else /* Дерево не упорядочено */; Источник
Alex tools
Иногда у нас уже есть двоичное дерево, и нам нужно определить, является ли оно BST (Binary Search Tree, двоичное дерево поиска). Эта проблема имеет простое рекурсивное решение.
Свойство BST — каждый узел в правом поддереве должен быть больше текущего узла, а каждый узел в левом поддереве должен быть меньше текущего узла — является ключом к выяснению, является ли дерево BST или нет. Жадный (greedy) алгоритм — просто обход дерева, на каждом узле проверка, содержит ли узел значение, большее, чем значение у левого дочернего элемента и меньше, чем значение у правого дочернего элемента, — не работает во всех случаях. Рассмотрим следующее дерево:
В приведенном выше дереве каждый узел удовлетворяет условию, что узел содержит значение, большее, чем его левый дочерний элемент, и меньше, чем его правый дочерний элемент, и все же это не 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
По сути, мы продолжаем создавать допустимый диапазон (начиная с [MIN_VALUE, MAX_VALUE]) и продолжаем уменьшать его для каждого узла, пока мы рекурсивно снижаемся.
Обход по порядку двоичного дерева поиска возвращает отсортированные узлы. Таким образом, нам нужно только сохранить последний посещенный узел при обходе дерева и проверить, меньше ли его ключ (или меньше/равен, если дубликаты должны быть разрешены в дереве) по сравнению с текущим ключом.
Источник
Определить, является ли данное бинарное дерево BST или нет
Учитывая бинарное дерево, определите, является ли оно BST.
Эта задача имеет простое рекурсивное решение. Свойство BST»каждый узел в правом поддереве должен быть больше текущего узла, а каждый узел в левом поддереве должен быть меньше текущего узла” является ключом к выяснению того, является ли дерево BST или нет.
The жадный алгоритм – пройтись по дереву, в каждом узле проверить, содержит ли узел значение больше, чем значение в левом дочернем элементе, и меньшее, чем значение в правом дочернем элементе – работает не во всех случаях. Рассмотрим следующее дерево:
В приведенном выше дереве каждый узел удовлетворяет условию, что узел содержит значение больше, чем его левый дочерний элемент, и меньше, чем его правое дочернее удержание, и все же это не BST: значение 5 находится в правом поддереве узла, содержащего 20, нарушение свойства BST.
Вместо того, чтобы принимать решения, основываясь исключительно на значениях узла и его дочерних элементов, нам также нужна информация, поступающая от родителя. В приведенном выше дереве, если бы мы могли вспомнить об узле, содержащем значение 20, мы увидели бы, что узел со значением 5 нарушает контракт свойства BST.
Итак, условие, которое нам нужно проверить в каждом узле:
- Если узел является левым дочерним элементом своего родителя, он должен быть меньше (или равен) родителю, и он должен передать значение от своего родителя в свое правое поддерево, чтобы убедиться, что ни один из узлов в этом поддереве не больше. чем родитель.
- Если узел является правым потомком своего родителя, он должен быть больше, чем родитель, и он должен передать значение от своего родителя в свое левое поддерево, чтобы убедиться, что ни один из узлов в этом поддереве не меньше родителя.
Ниже приведена реализация этой идеи на C++, Java и Python:
Источник
Проверка корректности двоичного дерева
Свойство двоичного дерева поиска можно сформулировать следующим образом: для каждой
вершины дерева V выполняется следующее условие:
• все ключи вершин из левого поддерева меньше ключа вершины V ;
• все ключи вершин из правого поддерева больше ключа вершины V .
Дано двоичное дерево. Проверьте, выполняется ли для него свойство двоичного дерева поиска.
Формат входного файла
Входной файл содержит описание двоичного дерева. В первой строке файла находится число
N (0 ≤ N ≤ 200000) — число вершин в дереве. В последующих N строках файла находятся описания
вершин дерева. В (i + 1)-ой строке файла (1 ≤ i ≤ N) находится описание i-ой вершины, состоящее
из трех чисел Ki, Li, Ri разделенных пробелами — ключа в i-ой вершине (|Ki| ≤ 10^9), номера левого
ребенка i-ой вершины (i < Li ≤ N или Li = 0, если левого ребенка нет) и номера правого ребенка
i-ой вершины (i < Ri ≤ N или Ri = 0, если правого ребенка нет).
Формат выходного файла
Выведите «YES», если данное на входе дерево является двоичным деревом поиска, и «NO», если
не является.
пример входного файла:
3
5 2 3
6 0 0
4 0 0
пример выходного файла:
NO
пример входного файла:
6
-2 0 2
8 4 3
9 0 0
3 5 6
0 0 0
6 0 0
пример выходного файла:
YES
Я считываю само дерево, далее вызываю функцию, которая начинает от корня дерева и в случае, если с корнем и его детьми все ок, запускается для каждого из детей. Считаю, что корень дерева — первый элемент массива (в условии не сказано, но вроде это так)
на всех моих тестах работало, но в проверяющей системе не проходит тест 8
вот мой код:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71
#include #include struct BinarySearchTree { int value; int left; int right; }; bool isBST(BinarySearchTree *, int const &); int main() { std::ifstream fin("input.txt"); std::ofstream fout("check.txt"); int n; fin >> n; if (n == 0) { fout "YES"; fout.close(); fin.close(); return 0; } BinarySearchTree *tree; tree = new BinarySearchTree[n + 1]; for (int i = 1; i n; i++) fin >> tree[i].value >> tree[i].left >> tree[i].right; if (isBST(tree, 1)) fout "YES"; else fout "NO"; fin.close(); fout.close(); return 0; } bool check(BinarySearchTree *tree, int const &j, int const &k, int const &c) { switch (k) { case 0: if (tree[j].value > c) return false; break; case 1: if (tree[j].value c) return false; break; } if (tree[j].left != 0 && !check(tree, tree[j].left, k, c)) return false; if (tree[j].right != 0 && !check(tree, tree[j].right, k, c)) return false; return true; } bool isBST(BinarySearchTree *tree, int const &j) { if (tree[j].left == 0 && tree[j].right == 0) return true; if (tree[j].left != 0 && tree[j].value tree[tree[j].left].value) return false; if (tree[j].right != 0 && tree[j].value > tree[tree[j].right].value) return false; if (tree[j].left != 0 && !check(tree, tree[j].left, 0, tree[j].value)) return false; if (tree[j].right != 0 && !check(tree, tree[j].right, 1, tree[j].value)) return false; if (tree[j].left != 0 && isBST(tree, tree[j].left) == false) return false; if (tree[j].right != 0 && isBST(tree, tree[j].right) == false) return false; return true; } Источник