二叉搜尋樹檢查

  2. 教程
  3. 資料結構
  4. 二叉搜尋樹檢查
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)。

作者： 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