二叉搜索树检查

Harshit Jindal 2023年10月12日

Data Structure Binary Tree Binary Search Tree

二叉树是否为二叉搜索树的检验算法
检查二叉树是否为二叉搜索树的算法实现方法
复杂度分析

二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多有两个子节点。这些子节点被称为左子和右子。一个二叉树要想成为 BST，必须满足以下属性。

左侧子树的所有节点都比根节点小。
右侧子树中的所有节点都比根节点大。
左子树和右子树也必须是二元搜索树。

二叉树是否为二叉搜索树的检验算法

算法 1

在这种方法中，我们通过将每个节点视为其子树的根，来检查左子树是否包含任何大于根值的元素，以及右子树是否包含小于根值的元素。为了找到最大和最小元素，我们必须使用两个独立的函数 getMin() 和 getMax()。

`getMin()`

初始化 temp 为 root。
当 temp 有一个 left 时，执行以下操作。
- 设置 temp 为 temp->left，即向左移动找到最小的元素。
返回 temp->val 作为该子树的最小值。

`getMax()`

初始化 temp 为 root。
当 temp 有一个 right 时，执行以下操作。
- 设置 temp 为 temp->right，即向右移动找到最大的元素。
返回 temp->val 作为该子树的最大值。

`isBST(root)`

如果 root 是 NULL，返回 true。
通过调用 getMax(root->left)在左边子树中找到最大元素 maxm。
通过调用 getMin(root->right)在右侧子树中查找最小元素 minm。
如果根元素小于 maxm 或大于 minm，返回 false。
通过调用 isBST(root->left) 和 isBST(root->right) 递归检查所有节点。如果两个递归调用都返回 true，那么这棵树就是 BST，返回 true，否则返回 false。

上面的算法告诉我们一棵树是否是 BST，但速度极慢。函数 getMin() 和 getMax() 在最坏情况下的时间复杂度为 O(n)，它们是为 n 节点调用的，使得总的时间复杂度为 O(n²)。

算法 2

该算法在前一种算法的基础上进行改进，不做重复计算。前一种方法对每个节点都调用 getMin() 和 getMax()。这个方法在上面的方法上做了改进，在我们遍历节点的时候，一直跟踪最小值和最大允许值。

`isBST(root)`

初始化两个变量 min 为 INT_MIN，max 为 INT_MAX。
调用 isBST(root,min,max)。

`isBST(root, min, max)`

如果 root 是 NULL，返回 true。
如果 min>root->data，则违反 BST 属性，返回 false。
如果 max<root->data，则违反 BST 属性，返回 false。
通过调用 isBST(root->left, min, root->data-1) 递归检查左子树（传递 min 和 root->data - 1 作为参数改变左子树中 BST 的有效范围），通过调用 isBST(root->right, root->data+1, max) 递归检查右子树（传递 root->data + 1 和 max 作为参数改变右子树中 BST 的有效范围）。
如果两个递归调用都返回 true，则树为 BST，返回 true。

此算法的时间复杂度为 O(n)，比前一种方法有很大的改进。

算法 3

这个算法避免了上面算法中使用 INT_MIN 和 INT_MAX，用两个指针 l 和 r 代替。

`isBST(root)`

初始化两个节点 l 和 r 为 NULL。
调用 isBST(root, l, r)。(重载函数调用)

`isBST(root, l, r)`

如果 root 是 NULL，返回 true。
如果 l 不是 NULL 并且 l->data>= root->data，则违反 BST 属性，返回 false。
如果 r 不是 NULL 并且 r->data<= root->data，那么 BST 属性被违反，返回 false。
通过调用 isBST(root->left, left, root)（将 root 作为第三个参数传递，改变子树的最小值限制）和调用 isBST(root->right, root, right)（将 root 作为第二个参数传递，改变子树的最大值限制）来递归检查左边的子树。
如果两个递归调用都返回 true，则该树为 BST，返回 true。

算法 4:

二叉搜索树的 inorder 遍历按排序顺序返回元素。我们可以利用这个特性来检查一棵二叉树是否为 BST。如果无序遍历中的所有元素都不是按升序排列，那么给定的树就不是二叉搜索树。

`isBST(root)`

将变量 prev 初始化为 INT_MIN。prev 用于检查当前节点是否大于 prev，从而按照排序顺序进行。
调用 isBST(root, prev)。(重载函数 Call)。

`isBST(root,prev)`

如果 root 是 NULL，返回 true。
通过 isBST(root->left, prev) 递归检查左子树。如果返回 false，则返回 false。
如果 root->data<=prev，违反了升序，返回 false。
将 prev->data 更新为 root->data。
通过 isBST(root->right, prev) 递归检查右子树。如果返回 false，则返回 false。
否则，返回 true。

检查二叉树是否为二叉搜索树的算法实现方法

算法 1

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
int getMin(Node* root) {
  while (root->left) {
    root = root->left;
  }

  return root->data;
}
int getMax(Node* root) {
  while (root->right) {
    root = root->right;
  }

  return root->data;
}
bool isBST(Node* root) {
  if (root == NULL) return true;

  if (root->left != NULL && getMax(root->left) > root->data) return false;

  if (root->right != NULL && getMin(root->right) < root->data) return false;

  if (!isBST(root->left) || !isBST(root->right)) return false;

  return true;
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

算法 2

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int min, int max) {
  if (root == NULL) return 1;
  if (root->data < min || root->data > max) return 0;

  return isBST(root->left, min, root->data - 1) &&
         isBST(root->right, root->data + 1, max);
}

bool isBST(Node* root) { return isBST(root, INT_MIN, INT_MAX); }
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

算法 3

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, Node* l, Node* r) {
  if (root == NULL) return true;

  if (l != NULL and root->data <= l->data) return false;
  if (r != NULL and root->data >= r->data) return false;

  return isBST(root->left, l, root) && isBST(root->right, root, r);
}
bool isBST(Node* root) {
  Node* l = NULL;
  Node* r = NULL;
  return isBST(root, l, r);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

算法 4

#include <iostream>
using namespace std;

class Node {
 public:
  int data;
  Node *left, *right;
  Node(int x) {
    this->data = x;
    this->left = this->right = NULL;
  }
};
bool isBST(Node* root, int& prev) {
  if (!root) return true;

  if (!isBST(root->left, prev)) return false;

  if (root->data <= prev) return false;
  prev = root->data;

  return isBST(root->right, prev);
}

bool isBST(Node* root) {
  int prev = INT_MIN;
  return isBST(root, prev);
}
int main() {
  Node* root = new Node(6);
  root->left = new Node(3);
  root->right = new Node(9);
  root->left->left = new Node(1);
  root->left->right = new Node(5);
  root->right->left = new Node(7);
  root->right->right = new Node(11);
  if (isBST(root)) {
    cout << "This binary tree is a BST." << endl;
  } else {
    cout << "This binary tree is not a BST." << endl;
  }
  return 0;
}

复杂度分析

时间复杂度

平均情况

为了检查给定的二叉树是否是 BST，我们必须遍历所有 n 节点，因为一个不符合属性的节点将导致该树不是 BST。因此，时间复杂度是 [Big Theta]：O(n)。

最佳情况

最佳情况下的时间复杂度为 O(n)。它与平均情况下的时间复杂度相同。

最坏情况

最坏情况下的时间复杂度为 O(n)。它与最佳情况下的时间复杂度相同。

空间复杂度

由于递归调用所需的额外空间，该算法的空间复杂度为 O(n)。

作者： Harshit Jindal

Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.

二叉树是否为二叉搜索树的检验算法

算法 1

getMin()

初始化 temp 为 root。

当 temp 有一个 left 时，执行以下操作。

返回 temp->val 作为该子树的最小值。

getMax()

初始化 temp 为 root。

当 temp 有一个 right 时，执行以下操作。

返回 temp->val 作为该子树的最大值。

isBST(root)

如果 root 是 NULL，返回 true。

通过调用 getMax(root->left)在左边子树中找到最大元素 maxm。

通过调用 getMin(root->right)在右侧子树中查找最小元素 minm。

如果根元素小于 maxm 或大于 minm，返回 false。

通过调用 isBST(root->left) 和 isBST(root->right) 递归检查所有节点。如果两个递归调用都返回 true，那么这棵树就是 BST，返回 true，否则返回 false。

算法 2

isBST(root)

初始化两个变量 min 为 INT_MIN，max 为 INT_MAX。

调用 isBST(root,min,max)。

isBST(root, min, max)

如果 root 是 NULL，返回 true。

如果 min>root->data，则违反 BST 属性，返回 false。

如果 max<root->data，则违反 BST 属性，返回 false。

如果两个递归调用都返回 true，则树为 BST，返回 true。

算法 3

isBST(root)

初始化两个节点 l 和 r 为 NULL。

调用 isBST(root, l, r)。(重载函数调用)

isBST(root, l, r)

如果 root 是 NULL，返回 true。

如果 l 不是 NULL 并且 l->data>= root->data，则违反 BST 属性，返回 false。

如果 r 不是 NULL 并且 r->data<= root->data，那么 BST 属性被违反，返回 false。

通过调用 isBST(root->left, left, root)（将 root 作为第三个参数传递，改变子树的最小值限制）和调用 isBST(root->right, root, right)（将 root 作为第二个参数传递，改变子树的最大值限制）来递归检查左边的子树。

如果两个递归调用都返回 true，则该树为 BST，返回 true。

算法 4:

isBST(root)

将变量 prev 初始化为 INT_MIN。prev 用于检查当前节点是否大于 prev，从而按照排序顺序进行。

调用 isBST(root, prev)。(重载函数 Call)。

isBST(root,prev)

如果 root 是 NULL，返回 true。

通过 isBST(root->left, prev) 递归检查左子树。如果返回 false，则返回 false。

如果 root->data<=prev，违反了升序，返回 false。

将 prev->data 更新为 root->data。

通过 isBST(root->right, prev) 递归检查右子树。如果返回 false，则返回 false。

否则，返回 true。

检查二叉树是否为二叉搜索树的算法实现方法

算法 1

算法 2

算法 3

算法 4

复杂度分析

时间复杂度

空间复杂度

相关文章 - Data Structure

相关文章 - Binary Tree

相关文章 - Binary Search Tree

`getMin()`

初始化 `temp` 为 `root`。

当 `temp` 有一个 `left` 时，执行以下操作。

返回 `temp->val` 作为该子树的最小值。

`getMax()`

初始化 `temp` 为 `root`。

当 `temp` 有一个 `right` 时，执行以下操作。

返回 `temp->val` 作为该子树的最大值。

`isBST(root)`

如果 `root` 是 `NULL`，返回 `true`。

通过调用 getMax(root->left)在左边子树中找到最大元素 `maxm`。

通过调用 getMin(root->right)在右侧子树中查找最小元素 `minm`。

如果根元素小于 `maxm` 或大于 `minm`，返回 false。

通过调用 `isBST(root->left)` 和 `isBST(root->right)` 递归检查所有节点。如果两个递归调用都返回 true，那么这棵树就是 BST，返回 true，否则返回 false。

`isBST(root)`

初始化两个变量 `min` 为 `INT_MIN`，`max` 为 `INT_MAX`。

调用 `isBST(root,min,max)`。

`isBST(root, min, max)`

如果 `root` 是 `NULL`，返回 `true`。

如果 `min`>`root->data`，则违反 BST 属性，返回 false。

如果 `max`<`root->data`，则违反 BST 属性，返回 false。

如果两个递归调用都返回 `true`，则树为 BST，返回 `true`。

`isBST(root)`

初始化两个节点 `l` 和 `r` 为 `NULL`。

调用 `isBST(root, l, r)`。(重载函数调用)

`isBST(root, l, r)`

如果 `root` 是 `NULL`，返回 `true`。

如果 `l` 不是 `NULL` 并且 `l->data`>= `root->data`，则违反 BST 属性，返回 false。

如果 `r` 不是 `NULL` 并且 `r->data`<= `root->data`，那么 BST 属性被违反，返回 false。

通过调用 `isBST(root->left, left, root)`（将 root 作为第三个参数传递，改变子树的最小值限制）和调用 `isBST(root->right, root, right)`（将 root 作为第二个参数传递，改变子树的最大值限制）来递归检查左边的子树。

如果两个递归调用都返回 `true`，则该树为 BST，返回 `true`。

`isBST(root)`

将变量 `prev` 初始化为 `INT_MIN`。`prev` 用于检查当前节点是否大于 `prev`，从而按照排序顺序进行。

调用 `isBST(root, prev)`。(重载函数 Call)。

`isBST(root,prev)`

如果 `root` 是 `NULL`，返回 `true`。

通过 `isBST(root->left, prev)` 递归检查左子树。如果返回 `false`，则返回 false。

如果 `root->data`<=`prev`，违反了升序，返回 false。

将 `prev->data` 更新为 `root->data`。

通过 `isBST(root->right, prev)` 递归检查右子树。如果返回 `false`，则返回 false。