二叉搜索树检查

Harshit Jindal 2023年1月30日 2021年2月28日
  1. 二叉树是否为二叉搜索树的检验算法
  2. 检查二叉树是否为二叉搜索树的算法实现方法
  3. 复杂度分析
二叉搜索树检查

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

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

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

算法 1

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

getMin()

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

getMax()

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

isBST(root)

  • 如果 rootNULL,返回 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)

  • 初始化两个变量 minINT_MINmaxINT_MAX
  • 调用 isBST(root,min,max)

isBST(root, min, max)

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

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

算法 3

这个算法避免了上面算法中使用 INT_MININT_MAX,用两个指针 lr 代替。

isBST(root)

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

isBST(root, l, r)

  • 如果 rootNULL,返回 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_MINprev 用于检查当前节点是否大于 prev,从而按照排序顺序进行。
  • 调用 isBST(root, prev)。(重载函数 Call)。

isBST(root,prev)

  • 如果 rootNULL,返回 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 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