二叉搜索树检查

  2. 教程
  3. 数据结构
  4. 二叉搜索树检查
Harshit Jindal 2023年1月30日 2021年2月28日
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)。

Author: 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