二叉搜索树检查

Harshit Jindal 2023年10月12日 Data Structure Binary Tree Binary Search Tree
  1. 二叉树是否为二叉搜索树的检验算法
  2. 检查二叉树是否为二叉搜索树的算法实现方法
  3. 复杂度分析
二叉搜索树检查

二叉树是一种非线性数据结构。它被称为二叉树，因为每个节点最多有两个子节点。这些子节点被称为左子和右子。一个二叉树要想成为 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(n2)。

算法 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)。

Enjoying our tutorials? Subscribe to DelftStack on YouTube to support us in creating more high-quality video guides. Subscribe
作者： Harshit Jindal
Harshit Jindal avatar Harshit Jindal avatar

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.

LinkedIn

相关文章 - Data Structure

相关文章 - Binary Tree

相关文章 - Binary Search Tree