컨셉
주어진 균형 이진 탐색 트리 및 목표 합계와 관련하여 합계가 목표 합계와 같은 쌍이 있으면 true를 반환하고 그렇지 않으면 false를 반환하는 함수를 작성합니다. 이 경우 예상 시간 복잡도는 O(n)이고 O(Logn)의 추가 공간만 구현할 수 있습니다. 여기에서 Binary Search Tree에 대한 수정은 허용되지 않습니다. Balanced BST의 높이는 항상 O(Logn)입니다.
예
방법
Brute Force Solution에 따르면 BST의 각 쌍을 고려하고 합이 X인지 확인합니다. 이 솔루션의 시간 복잡도는 O(n^2)입니다.
이제 더 나은 솔루션은 보조 배열을 만들고 배열에 BST의 Inorder 순회를 저장하는 것입니다. 이 경우 배열은 BST의 inorder traversal이 항상 정렬된 데이터를 생성하므로 정렬됩니다. 따라서 inorder traversal을 사용할 수 있게 되면 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