二叉搜尋樹檢查

  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