ค้นหาว่ามีแฝดสามใน Balanced BST ที่เพิ่มเป็นศูนย์ใน C ++

สมมติว่าเรามีแผนผังการค้นหาไบนารีที่สมดุล เราต้องสร้างฟังก์ชันชื่อ is_valid_triplet() ที่คืนค่าเป็น true เมื่อมี triplet ใน BST ที่กำหนดซึ่งมีผลรวมเท่ากับ 0 มิฉะนั้นจะคืนค่าเท็จ . ออกแบบวิธีการโดยปฏิบัติตามข้อจำกัดเหล่านี้ -

• ความซับซ้อนของเวลาที่คาดหวังคือ O(n^2)

• O(logn) สามารถใช้พื้นที่เพิ่มเติมได้

ดังนั้น ถ้าอินพุตเป็นแบบนี้

จากนั้นผลลัพธ์จะเป็น True เนื่องจาก triplet คือ [-15,7,8]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดฟังก์ชัน bst_to_doubli_list() ซึ่งจะทำการรูท หัว หาง

• ถ้า root เหมือนกับ NULL แล้ว −

  • กลับ

• หากรูทที่เหลือไม่เป็นโมฆะ −

  • bst_to_doubli_list(ด้านซ้ายของ root, head, tail)

• ทางซ้ายของรูท :=หาง

• ถ้า tail ไม่ใช่ null แล้ว −

  • ทางขวาของหาง :=รูท

• มิฉะนั้น

  • หัว :=รูท

• หาง :=รูท

• หากสิทธิ์ของรูทไม่เป็นโมฆะ −

  • bst_to_doubli_list(ทางขวาของรูท หัว หาง)

• กำหนดฟังก์ชัน is_in_double_list() จะใช้ head, tail, sum

• ในขณะที่หัวไม่เท่ากับหางให้ทำ -

  • ปัจจุบัน :=กุญแจหัว + กุญแจหาง

  • ถ้ากระแสเท่ากับผลรวมแล้ว −

    • คืนความจริง

  • มิฉะนั้นเมื่อกระแส> ผลรวม แล้ว -

    • หาง :=ด้านซ้ายของหาง

  • มิฉะนั้น

    • head :=ด้านขวาของหัว

• คืนค่าเท็จ

• จากวิธีหลัก ให้ทำดังนี้ −

• ถ้ารูทเป็นโมฆะ −

  • คืนค่าเท็จ

• หัว =null

• หาง =null

• bst_to_doubli_list(ราก หัว หาง)

• ในขณะที่ (ด้านขวาของศีรษะไม่เท่ากับส่วนท้ายและกุญแจของศีรษะ <0) ทำ −

  • ถ้า is_in_double(ทางขวาของ head, tail, key of head * (-1) แล้ว

    • คืนความจริง

  • มิฉะนั้น

    • head :=ด้านขวาของหัว

• คืนค่าเท็จ

ตัวอย่าง (C++)

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

#include <bits/stdc++.h>
using namespace std;
class TreeNode {
   public:
   int key;
   TreeNode *left;
   TreeNode *right;
   TreeNode() : key(0), left(NULL), right(NULL) {}
   TreeNode(int x) : key(x), left(NULL), right(NULL) {}
};
void bst_to_doubli_list(TreeNode* root, TreeNode** head, TreeNode** tail) {
   if (root == NULL)
      return;
   if (root->left)
      bst_to_doubli_list(root->left, head, tail);
   root->left = *tail;
   if (*tail)
      (*tail)->right = root;
   else
      *head = root;
      *tail = root;
   if (root->right)
      bst_to_doubli_list(root->right, head, tail);
}
bool is_in_double_list(TreeNode* head, TreeNode* tail, int sum) {
   while (head != tail) {
      int current = head->key + tail->key;
      if (current == sum)
         return true;
      else if (current > sum)
         tail = tail->left;
      else
         head = head->right;
   }
   return false;
}
bool is_valid_triplet(TreeNode *root) {
   if (root == NULL)
      return false;
   TreeNode* head = NULL;
   TreeNode* tail = NULL;
   bst_to_doubli_list(root, &head, &tail);
   while ((head->right != tail) && (head->key < 0)){
      if (is_in_double_list(head->right, tail, -1*head->key))
         return true;
      else
         head = head->right;
   }
   return false;
}
TreeNode* insert(TreeNode* root, int key) {
   if (root == NULL)
      return new TreeNode(key);
   if (root->key > key)
      root->left = insert(root->left, key);
   else
      root->right = insert(root->right, key);
   return root;
}
int main(){
   TreeNode* root = NULL;
   root = insert(root, 7);
   root = insert(root, -15);
   root = insert(root, 15);
   root = insert(root, -7);
   root = insert(root, 14);
   root = insert(root, 16);
   root = insert(root, 8);
   cout << is_valid_triplet(root);
}

อินพุต

root = insert(root, 7);
root = insert(root, -15);
root = insert(root, 15);
root = insert(root, -7);
root = insert(root, 14);
root = insert(root, 16);
root = insert(root, 8);

ผลลัพธ์

1