Tìm cặp có tổng cho trước trong BST cân bằng (Balanced BST) bằng Java

Khái niệm

Với một Cây tìm kiếm nhị phân cân bằng (Balanced Binary Search Tree) và tổng mục tiêu cho trước, chúng ta viết hàm trả về true nếu tồn tại cặp có tổng bằng mục tiêu, ngược lại trả về false. Trong trường hợp này, độ phức tạp thời gian kỳ vọng là O(n) và chỉ O(log n) không gian phụ có thể được triển khai. Ở đây, bất kỳ sửa đổi nào đối với BST không được phép. Chúng ta lưu ý rằng chiều cao của BST cân bằng luôn là O(log n).

Ví dụ

Phương pháp

Theo giải pháp Brute Force, chúng ta xem xét mỗi cặp trong BST và kiểm tra xem tổng có bằng X hay không. Độ phức tạp thời gian của giải pháp này sẽ là O(n^2).

Giải pháp tốt hơn là xây dựng mảng phụ và lưu trữ duyệt Inorder của BST trong mảng. Trong trường hợp này, mảng sẽ được sắp xếp vì duyệt inorder của BST luôn tạo ra dữ liệu đã sắp xếp. Vì vậy sau khi có duyệt inorder, chúng ta có thể tìm cặp trong O(n) thời gian. Nhớ rằng, giải pháp này hoạt động trong O(n) thời gian, nhưng yêu cầu O(n) không gian phụ.

Ví dụ

// 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 { 
    // Chỉ ra root của BST 
    Node1 root1; 
    // Constructor 
    BinarySearchTree() { 
        root1 = null; 
    } 
    // Duyệt inorder của cây 
    void inorder() { 
        inorderUtil1(this.root1); 
    } 
    // Hàm tiện ích duyệt inorder 
    void inorderUtil1(Node1 node1) { 
        if (node1 == null) 
            return; 
        inorderUtil1(node1.left1); 
        System.out.print(node1.data1 + " "); 
        inorderUtil1(node1.right1); 
    } 
    // Gọi insertRec() 
    void insert(int key1) { 
        root1 = insertRec1(root1, key1); 
    } 
    /* Hàm đệ quy chèn khóa mới vào BST */ 
    Node1 insertRec1(Node1 root1, int data1) { 
        if (root1 == null) { 
            root1 = new Node1(data1); 
            return root1; 
        } 
        if (data1 < root1.data1) 
            root1.left1 = insertRec1(root1.left1, data1); 
        else if (data1 > root1.data1) 
            root1.right1 = insertRec1(root1.right1, data1); 
        return root1; 
    } 
    // Phương thức thêm giá trị BST vào ArrayList 
    ArrayList<Integer> treeToList(Node1 node1, ArrayList<Integer> list1) { 
        if (node1 == null) 
            return list1; 
        treeToList(node1.left1, list1); 
        list1.add(node1.data1); 
        treeToList(node1.right1, list1); 
        return list1; 
    } 
    // Kiểm tra cặp có tổng bằng target 
    boolean isPairPresent(Node1 node1, int target1) { 
        ArrayList<Integer> a1 = new ArrayList<>(); 
        ArrayList<Integer> a2 = treeToList(node1, a1); 
        int start1 = 0; 
        int end1 = a2.size() - 1; 
        while (start1 < end1) { 
            if (a2.get(start1) + a2.get(end1) == target1) { 
                System.out.println("Pair Found: " + a2.get(start1) + " + " + a2.get(end1) + " = " + target1); 
                return true; 
            } 
            if (a2.get(start1) + a2.get(end1) > target1) 
                end1--; 
            if (a2.get(start1) + a2.get(end1) < target1) 
                start1++; 
        } 
        System.out.println("No such values are found!"); 
        return false; 
    } 
    // Driver function 
    public static void main(String[] args) { 
        BinarySearchTree tree1 = new BinarySearchTree(); 
        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); 
    } 
}

Kết quả

Pair Found: 13 + 21 = 34