ធ្វើឱ្យមានសុពលភាពមែកធាងស្វែងរកគោលពីរ

សំណួរសំភាសន៍រចនាប្រព័ន្ធ អាចជាការបើកចំហរ ដូច្នេះវាពិបាកពេកក្នុងការដឹងពីវិធីត្រឹមត្រូវក្នុងការរៀបចំ។ ឥឡូវនេះខ្ញុំអាចបំបែកការរចនានៃ Amazon, Microsoft និង Adobe បន្ទាប់ពីទិញ សៀវភៅ​នេះ. ពិនិត្យឡើងវិញប្រចាំថ្ងៃ សំណួររចនា ហើយខ្ញុំសន្យាថាអ្នកអាចបំបែកការរចនាជុំ។

បញ្ហា

In ធ្វើឱ្យមានសុពលភាពមែកធាងស្វែងរកគោលពីរ បញ្ហាដែលយើងបានចាក់ឬសនៃក ដើមឈើយើងត្រូវពិនិត្យមើលថាតើវាជាមែកធាងស្វែងរកគោលពីររឺអត់។

ឧទាហរណ៍:

ពិន

លទ្ធផល:

ជាការពិត

ការពន្យល់: មែកធាងដែលបានផ្តល់ឱ្យគឺជាមែកធាងនៃការស្វែងរកគោលពីរពីព្រោះធាតុទាំងអស់ដែលនៅសល់ទៅអនុក្រឹត្យនីមួយៗតូចជាងឫសនៃអនុ។ ធាតុទាំងអស់ដែលត្រូវនឹងអនុក្រឹត្យនីមួយៗធំជាងឫសនៃអនុក្រឹត្យហើយអនុក្រឹត្យនីមួយៗគឺខ្លួនវាផ្ទាល់ជាមែកធាងស្វែងរកគោលពីរ។

វិធីសាស្រ្ត

• ដំបូងយើងធ្វើអន្តរកម្ម ឆ្លងកាត់ នៃមែកធាងដែលបានផ្តល់ឱ្យនិងទុកវានៅក្នុងមួយ អារេ។ បន្ទាប់មកយើងពិនិត្យមើលថាតើអារេត្រូវបានតម្រៀបតាមលំដាប់ដែលកើនឡើង។ បន្ទាប់មកយើងនិយាយថាវាជាមែកធាងស្វែងរកគោលពីរផ្សេងទៀតវាមិនមែនជាដើមឈើស្វែងរកគោលពីរទេ។
• ដើម្បីបង្រួមអប្បបរមានៃការប្រើប្រាស់ចន្លោះជំនួយយើងអាចតាមដានថ្នាំងដែលបានទស្សនាពីមុនហើយប្រសិនបើថ្នាំងបច្ចុប្បន្នតូចជាងថ្នាំងពីមុននោះវាមិនមែនជា មែកធាងស្វែងរកគោលពីរ ហើយប្រសិនបើថ្នាំងមុនទាំងអស់តូចជាងថ្នាំងបច្ចុប្បន្ននោះវាជាមែកធាងស្វែងរកគោលពីរ។
• យើងអាចជៀសវាងការប្រើប្រាស់ចន្លោះបន្ថែមដោយឆ្លងកាត់ថ្នាំងមុនជាប៉ារ៉ាម៉ែត្រ។

កូដ C ++ សម្រាប់មែកធាងស្វែងរកគោលពីរដែលមានសុពលភាព

// C++ program to check if a given tree is BST. 
#include <bits/stdc++.h> 
using namespace std; 

/* A binary tree node has data, pointer to 
left child and a pointer to right child */
struct Node 
{ 
  int data; 
  struct Node* left, *right; 
  
  Node(int data) 
  { 
    this->data = data; 
    left = right = NULL; 
  } 
}; 


bool isBSTUtil(struct Node* root, Node *&prev) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root) 
  { 
    if (!isBSTUtil(root->left, prev)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != NULL && root->data <= prev->data) 
    return false; 

    prev = root; 

    return isBSTUtil(root->right, prev); 
  } 

  return true; 
} 

bool isBST(Node *root) 
{ 
   Node *prev = NULL; 
   return isBSTUtil(root, prev); 
} 

/* Driver program to test above functions*/
int main() 
{ 
  struct Node *root = new Node(3); 
  root->left	 = new Node(2); 
  root->right	 = new Node(5); 
  root->left->left = new Node(1); 
  root->left->right = new Node(4); 

  if (isBST(root)) 
    cout << "Is BST"; 
  else
    cout << "Not a BST"; 

  return 0; 
} 

កូដចាវ៉ាសំរាប់មែកធាងស្វែងរកគោលពីរដែលមានសុពលភាព

// Java program to check if a given tree is BST. 
class Check
{ 
/* A binary tree node has data, pointer to 
left child and a pointer to right child */
static class Node 
{ 
  int data; 
  Node left, right; 
  
  Node(int data) 
  { 
    this.data = data; 
    left = right = null; 
  } 
}; 
static Node prev; 

static boolean isBSTUtil(Node root) 
{ 
  // traverse the tree in inorder fashion and 
  // keep track of prev node 
  if (root != null) 
  { 
    if (!isBSTUtil(root.left)) 
    return false; 

    // Allows only distinct valued nodes 
    if (prev != null && root.data <= prev.data) 
    return false; 

    prev = root; 

    return isBSTUtil(root.right); 
  } 
  return true; 
} 

static boolean isBST(Node root) 
{ 
  return isBSTUtil(root); 
} 

// Driver Code 
public static void main(String[] args) 
{ 
  Node root = new Node(3); 
  root.left	 = new Node(2); 
  root.right	 = new Node(5); 
  root.left.left = new Node(1); 
  root.left.right = new Node(4); 

  if (isBST(root)) 
    System.out.print("Is BST"); 
  else
    System.out.print("Not a BST"); 
} 
} 

Not a BST

ភាពស្មុគស្មាញពេលវេលា

អូរ (n) ដូចដែលយើងកំពុងឆ្លងកាត់ថ្នាំងនីមួយៗតែមួយដង។

ភាពស្មុគស្មាញនៃលំហ

អូរ (n) ពីព្រោះយើងកំពុងទុកថ្នាំងឆ្លងកាត់នីមួយៗហើយពិនិត្យមើលថាតើអារេត្រូវបានតម្រៀបតាមលំដាប់លំដោយដើម្បីពិនិត្យមើលថាតើដើមឈើនោះជាមែកធាងស្វែងរកគោលពីររឺអត់។

ឯកសារយោង