Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> Java

ค้นหาคู่ที่มีผลรวมที่กำหนดใน Balanced BST ใน Java


แนวคิด

ในส่วนของ Balanced Binary Search Tree และผลรวมเป้าหมาย เราเขียนฟังก์ชันที่คืนค่า true หากมีคู่ที่มีผลรวมเท่ากับผลรวมเป้าหมาย มิฉะนั้นจะคืนค่าเท็จ ในกรณีนี้ ความซับซ้อนของเวลาที่คาดหวังคือ O(n) และสามารถใช้ช่องว่างพิเศษ O(Logn) ได้เท่านั้น ที่นี่ ไม่อนุญาตให้ทำการแก้ไขใด ๆ กับ Binary Search Tree เราต้องสังเกตว่าความสูงของ Balanced BST จะเป็น O (Logn) เสมอ

ตัวอย่าง

ค้นหาคู่ที่มีผลรวมที่กำหนดใน Balanced BST ใน Java

วิธีการ

จากข้อมูลของ Brute Force Solution เราพิจารณาแต่ละคู่ใน BST และตรวจสอบว่าผลรวมเท่ากับ X หรือไม่ ความซับซ้อนของเวลาของโซลูชันนี้จะเป็น O(n^2)

ทางออกที่ดีกว่าคือการสร้างอาร์เรย์เสริมและจัดเก็บการข้ามผ่าน Inorder ของ BST ในอาร์เรย์ ในกรณีนี้ อาร์เรย์จะถูกจัดเรียงตามการข้ามผ่านแบบไม่เรียงลำดับของ BST จะสร้างข้อมูลที่จัดเรียงเสมอ ดังนั้นหลังจากความพร้อมใช้งานของการข้ามผ่าน inorder เราสามารถจับคู่ในเวลา O(n) จำไว้ว่าโซลูชันนี้ใช้งานได้ในเวลา O(n) แต่ต้องใช้ช่องว่างเสริม O(n)

ตัวอย่าง

// Java code to find a pair with given sum
// in a Balanced BST
import java.util.ArrayList;
// A binary tree node
class Node1 {
   int data1;
   Node1 left1, right1;
   Node1(int d){
      data1 = d;
      left1 = right1 = null;
   }
}
public class BinarySearchTree {
   // Indicates root of BST
   Node1 root1;
   // Indicates constructor
   BinarySearchTree(){
      root1 = null;
   }
   // Indicates inorder traversal of the tree
   void inorder(){
      inorderUtil1(this.root1);
   }
   // Indicates utility function for inorder traversal of the tree
   void inorderUtil1(Node1 node1){
      if (node1 == null)
         return;
      inorderUtil1(node1.left1);
      System.out.print(node1.data1 + " ");
      inorderUtil1(node1.right1);
   }
   // Now this method mainly calls insertRec()
   void insert(int key1){
      root1 = insertRec1(root1, key1);
   }
   /* Indicates a recursive function to insert a new key in BST */
   Node1 insertRec1(Node1 root1, int data1){
   /* So if the tree is empty, return a new node */
   if (root1 == null) {
      root1 = new Node1(data1);
      return root1;
   }
   /* Otherwise, recur down the tree */
   if (data1 < root1.data1)
      root1.left1 = insertRec1(root1.left1, data1);
   else if (data1 > root1.data1)
      root1.right1 = insertRec1(root1.right1, data1);
   return root1;
}
// Indicates method that adds values of given BST into ArrayList
// and hence returns the ArrayList
ArrayList<Integer> treeToList(Node1 node1, ArrayList<Integer> list1){
   // Indicates Base Case
   if (node1 == null)
      return list1;
   treeToList(node1.left1, list1);
   list1.add(node1.data1);
   treeToList(node1.right1, list1);
   return list1;
}
// Indicates method that checks if there is a pair present
boolean isPairPresent(Node1 node1, int target1){
   // Now this list a1 is passed as an argument
   // in treeToList method
   // which is later on filled by the values of BST
   ArrayList<Integer> a1 = new ArrayList<>();
   // Now a2 list contains all the values of BST
   // returned by treeToList method
   ArrayList<Integer> a2 = treeToList(node1, a1);
   int start1 = 0; // Indicates starting index of a2
   int end1 = a2.size() - 1; // Indicates ending index of a2
   while (start1 < end1) {
      if (a2.get(start1) + a2.get(end1) == target1) // Target Found!{
         System.out.println("Pair Found: " + a2.get(start1) + " + " + a2.get(end1) + " " + "= " + target1);
         return true;
      }
      if (a2.get(start1) + a2.get(end1) > target1)
      // decrements end
      {
         end1--;
      }
      if (a2.get(start1) + a2.get(end1) < target1)
      // increments start
      {
         start1++;
      }
   }
   System.out.println("No such values are found!");
   return false;
}
// Driver function
public static void main(String[] args){
   BinarySearchTree tree1 = new BinarySearchTree();
/*
   16
   / \
  11 21
 / \ / \
9 13 17 26 */
      tree1.insert(16);
      tree1.insert(11);
      tree1.insert(21);
      tree1.insert(9);
      tree1.insert(13);
      tree1.insert(17);
      tree1.insert(26);
      tree1.isPairPresent(tree1.root1, 34);
   }
}

ผลลัพธ์

Pair Found: 13 + 21 = 34