Проверить является ли дерево бинарным

Как определить, является ли бинарное дерево деревом поиска? [закрыт]

Закрыт. На этот вопрос невозможно дать объективный ответ. Ответы на него в данный момент не принимаются.

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

Предложите алгоритм, который определяет, является ли дерево бинарным деревом поиска? Оцените временную сложность.

@Котик_хочет_кушать, как считаете, ошибку (static struct node *prev = NULL;) в программе №4, которая делает ее «одноразовой» все заметили, но решили это не обсуждать ?

8 ответов 8

Немного псевдокода, который чудесным образом напоминает C++

struct node< node *l,*r; int key; >; bool isSearchTree(node *p, int minKey, int maxKey)< if (p == nullptr) return true; if (minKey < p->key && p->key < maxKey) return isSearchTree(p->l, minKey, p->key) && isSearchTree(p->r, p->key, maxKey); return false; > const int minInt = (1 <<30)*2; const int maxInt = minInt - 1; bool isSearchTree(node *root)< return isSearchTree(root, minInt, maxInt); //можно без бесконечностей, //но это захламляет идею >

Проэмулируйте руками код на том примере и поймите, что правильно, в отличие от кода @jonyrock выше. Заметьте, что функция точно эмулирует процедуру добавления элемента в бинарное дерево, передавая по рекурсии отрезок возможных значений ключа, которые попали в поддерево. При проверке элемента с ключом 11 будет вызов isSearchTree(. 5, 10) и ответ false. P.S. Сложность худшего случая, очевидно, O(число элементов в дереве), среднего — зависит от понимания среднего.

@cf_anonymous, согласен, хороший алгоритм, плюсую. «Без бесконечностей захламляет код» — это Вы имеете в виду передавать уровень и для уровня 0 — не проверять ?

У меня получился такой алгоритм:

bool isSearchTree(BinaryTree * tree) < if (tree == NULL) return false; if (tree->root == NULL) return true; return _isSearchTree(tree->root); > bool _isSearchTree(BinaryTreeNode * node) < BinaryTreeNode * pnode = node->parent; BinaryTreeNode * tnode = node; while(pnode != NULL) < if (pnode->leftChild == tnode)< if (pnode->value < node->value) return false; > else < if (pnode->value > node->value) return false; > tnode = pnode; pnode = pnode->parent; > bool isLeft, isRight; if (node->leftChild != NULL) isLeft = _isSearchTree(node->leftChild); else isLeft = true; if (node->rightChild != NULL) isRight = _isSearchTree(node->rightChild); else isRight = true; return isLeft && isRight; > 

@Ник, у Вас в node еще и указатель наверх (parent) появился ? Чем вам код из Geeks не понравился ? IMHO лучше не придумать.

 bool isSearchTree(Tree tree) < bool isLeftOk = true; bool isRightOk = true; if (tree.left != null) < isLeftOk = tree.left.root if (tree.right != null) < isRightOk = tree.right.root >tree.root); if(isRightOk) isRightOk = isSearchTree(tree.right); > return isLeftOk && isRightOk; > 

Осталось только определить класс Tree

Временная сложность: O(n) где n — кол-во вершин.

Док-во: в алгоритме просматривается каждая вершина не более 3-х раз.

Источник

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:

Источник

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]) и продолжаем уменьшать его для каждого узла, пока мы рекурсивно снижаемся.

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

Источник