Chương 6: TREES - 7.Cây tìm kiếm nhị phân:Problems & Solutions(62-75)
Problem-62
Đưa ra một danh sách được liên kết đơn trong đó các phần tử được sắp xếp theo thứ tự tăng dần, hãy chuyển đổi nó thành height balanced BST(là cây nhị phân trong đó chiều cao của cây con bên trái và bên phải của bất kỳ node nào khác nhau không quá 1).
Solution: Một cách ngây thơ là áp dụng trực tiếp giải pháp Problem-60.(Chỗ này có lẽ tác giả nhầm lẫn, mình sẽ nói rõ ở Problem tiếp theo) Trong mỗi lần gọi đệ quy, chúng ta sẽ phải duyệt qua một nửa độ dài của danh sách để tìm phần tử ở giữa. Độ phức tạp của thời gian chạy rõ ràng là O(nlogn), trong đó n là tổng số phần tử trong danh sách. Điều này là do mỗi cấp độ của lời gọi đệ quy yêu cầu tổng số n/2 bước duyệt trong danh sách và có tổng số logn cấp độ (nghĩa là chiều cao của cây cân bằng).
Problem-63
Đối với Problem-62, chúng ta có thể cải thiện độ phức tạp không?
Solution: Hint: Suy nghĩ về việc làm thế nào về việc chèn các node theo thứ tự của list? Nếu chúng ta có thể đạt được điều này, chúng ta không cần phải tìm phần tử ở giữa nữa vì chúng ta có thể duyệt qua danh sách trong khi chèn các node vào cây.
Best Solution: Như thường lệ, giải pháp tốt nhất đòi hỏi chúng ta phải suy nghĩ từ một góc độ khác. Nói cách khác, chũng ta không còn tạo các node trong cây bằng cách sử dụng top-down approach(phương pháp từ trên xuống). Tạo các node từ dưới lên và gán chúng cho cha mẹ của chúng. The bottom-up approach(Cách tiếp cận từ dưới lên) cho phép chũng ta truy cập danh sách theo thứ tự của nó trong khi tạo các node.
Cách tiếp cận từ dưới lên có chính xác không? Bất cứ khi nào chúng ta gặp khó khăn với cách tiếp cận từ trên xuống, chúng ta có thể thử từ dưới lên. Mặc dù cách tiếp cận từ dưới lên không phải là cách tự nhiên nhất mà chũng ta nghĩ, nhưng nó vẫn hữu ích trong một số trường hợp. Tuy nhiên, chúng ta nên ưu tiên từ trên xuống thay vì từ dưới lên nói chung, vì từ dưới lên khó xác minh hơn.
Dưới đây là code để chuyển đổi singly linked list thành balanced BST. Xin lưu ý rằng thuật toán yêu cầu độ dài danh sách được chuyển vào dưới dạng tham số. Độ dài danh sách có thể được tìm thấy trong thời gian O(n) bằng cách duyệt qua toàn bộ danh sách một lần. Các cuộc gọi đệ quy duyệt qua list và tạo các node cây theo thứ tự của list, điều này cũng mất O(n) thời gian. Do đó, độ phức tạp của thời gian chạy tổng thể vẫn là O(n).
//First call is convertSortedList2BST(head, 0, lengthOfList - 1);
public BinarySearchTreeNode convertSortedList2BST(ListNode list, int start, int end){
if(start > end){
return null;
}
int mid = start + (end - start)/2;
BinarySearchTreeNode leftChild = convertSortedList2BST(list, start, mid - 1);
BinarySearchTreeNode parent = new BinarySearchTreeNode();
parent.setData(list.getData());
parent.setLeft(leftChild);
list = list.getNext();
parent.setRight(convertSortedList2BST(list, mid + 1, end));
return parent;
}
Lưu ý: Ở đây mình dịch đúng theo nguyên tác, nhưng mình thấy có vẻ tác giả có chút nhầm lẫn khi so sánh với Problem-60, ở bài toán đó tác giả đã áp dụng bottom-up approach chứ không phải top-down approach. Problem này mình cũng có viết ở bài trước, như thế có vẻ ở Problem-60 này Time Complexity cũng chỉ là O(n) chứ không phải O(nlogn).
Problem-64
Đưa ra thuật toán tìm phần tử nhỏ thứ k trong BST.
Solution: Ý tưởng đằng sau giải pháp này là duyệt inorder traversal của BST tạo ra các danh sách được sắp xếp. Trong khi duyệt qua BST theo thứ tự, hãy theo dõi số lượng phần tử đã truy cập.
public BinarySearchTreeNode kthSmallestInBST(BinarySearchTreeNode root, int k, int count){
if (root == null) {
return null;
}
BinarySearchTreeNode left = kthSmallestInBST(root.getLeft(), k, count);
if (left != null) {
return left;
}
if (++count == k) {
return root;
}
return kthSmallestInBST(root.getRight(), k, count);
}
Time Complexity: O(n). Space Complexity: O(1).
Problem-65
Floor(Sàn) và ceiling(trần): Nếu một data X đã cho nhỏ hơn data ở gốc BST thì floor của data (data lớn nhất trong BST nhỏ hơn hoặc bằng data X) phải nằm trong cây con bên trái. Nếu data X lớn hơn data ở gốc, thì floor của khóa có thể nằm trong cây con bên phải, nhưng chỉ khi có một data nhỏ hơn hoặc bằng data X trong cây con bên phải; nếu không (hoặc nếu data X bằng với data ở gốc) thì data ở gốc là floor của khóa. Tìm ceiling cũng tương tự, với việc hoán đổi bên phải và bên trái.
Lý thuyết thì hơi vòng vo, hãy xem ví dụ sau: Cho mảng đầu vào đã sắp xếp: {1, 2, 8, 10, 10, 12, 19} thì ta có:
- Với x = 0: floor không tồn tại trong mảng, ceiling = 1
- Với x = 1: floor = 1, ceiling = 1
- Với x = 5: floor =2, ceiling =8,
- Với x = 20: floor = 19, ceiling không tồn tại trong mảng
Solution: Ý tưởng đằng sau giải pháp này là, duyệt inorder traversal của BST tạo ra các danh sách được sắp xếp. Trong khi duyệt qua BST theo thứ tự, hãy theo dõi các giá trị được truy cập. Nếu dữ liệu gốc lớn hơn giá trị đã cho thì trả về giá trị trước đó mà chũng ta đã duy trì trong quá trình duyệt inorder traversal. Nếu dữ liệu gốc bằng với dữ liệu đã cho thì trả về dữ liệu gốc.
public BinarySearchTreeNode floorInBST(BinarySearchTreeNode root, int data){
BinarySearchTreeNode prev = null;
return floorInBSTUtil(root, prev, data);
}
public BinarySearchTreeNode floorInBSTUtil(BinarySearchTreeNode root, BinarySearchTreeNode prev, int data) {
if (root == null) {
return null;
}
BinarySearchTreeNode temp = floorInBSTUtil(root.getLeft(), prev, data);
if(temp != null) {
return temp;
}
if(root.getData() == data) {
return root;
}
if(root.getData() > data){
return prev;
}
prev = root;
return floorInBSTUtil(root.getRight(), prev, data);
}
Time Complexity: O(n). Space Complexity: O(n), cho cây xiên.
Đối với ceiling,, chúng ta chỉ cần gọi cây con bên phải trước, tiếp theo là cây con bên trái.
Problem-69
Cho một BST và hai số K1, K2, hãy viết thuật toán in ra tất cả các phần tử của BST trong dãy K1, K2.
Solution:
public void rangePrinter(BinarySearchTreeNode root, int K1, int K2){
if (root == null) {
return;
}
if(root.getData() >= K1){
rangePrinter(root.getLeft(), K1, K2);
}
if (root.getData() >= K1 && root.getData() <= K2) {
System.out.println(root.getData());
}
if(root.getData() <= K2){
rangePrinter(root.getRight(), K1, K2);
}
}
Time Complexity: O(n). Space Complexity: O(n), cho cây xiên.
Problem-70
Đối với Problem-69, có cách nào khác để giải quyết vấn đề không?
Solution: Chúng ta có thể sử dụng level order traversal: trong khi thêm các phần tử vào hàng đợi kiểm tra phạm vi.
public void rangeSearchLevelOrder(BinarySearchTreeNode root, int K1, int K2){
BinarySearchTreeNode temp;
Queue<BinarySearchTreeNode> Q = new ArrayDeque<>();
if (root == null) {
return;
}
Q.add(root);
while (!Q.isEmpty()) {
temp = Q.poll();
if (temp.getData() >= K1 && temp.getData() <= K2) {
System.out.println(temp.getData());
}
if (temp.getLeft() != null && temp.getData() >= K1) {
Q.add(temp.getLeft());
}
if (temp.getRight() != null && temp.getData() <= K2) {
Q.add(temp.getRight());
}
}
Q.clear();
}
Time Complexity: O(n). Space Complexity: O(n), cho việc sử dụng queue.
Problem-71
Đối với Problem-69, có cách nào khác để giải quyết vấn đề không?
Solution: Trong trường hợp đây là cây nhị phân theo luồng(threaded binary trees), Đầu tiên xác định vị trí K1 bằng tìm kiếm nhị phân thông thường và sau đó sử dụng InOrder successor cho đến khi chũng ta gặp K2.
Problem-72
Cho gốc của cây BST, cắt bớt cây sao cho tất cả các phần tử được trả về trong cây mới nằm giữa các đầu vào A và B.
Solution: Đây chỉ là một cách khác để hỏi Problem-69.
Problem-73
Cho hai BST, hãy kiểm tra xem các phần tử của chúng có giống nhau hay không. Ví dụ: hai BST có dữ liệu 10 5 20 15 30 và 10 20 15 30 5 sẽ trả về true và tập dữ liệu có 10 5 20 15 30 và 10 15 30 20 5 sẽ trả về false. Note: Dữ liệu BST có thể theo thứ tự bất kỳ.
Solution: Một cách đơn giản là thực hiện duyệt inorder traversal trên cây đầu tiên và lưu trữ dữ liệu của nó trong hash table. Bước thứ hai, thực hiện duyệt theo thứ tự trên cây thứ hai và kiểm tra xem dữ liệu đó đã có trong bảng băm hay chưa (nếu nó tồn tại trong bảng băm thì hãy đánh dấu nó bằng -1 hoặc một số giá trị duy nhất).
Trong quá trình duyệt cây thứ hai nếu chũng ta tìm thấy bất kỳ sự không phù hợp nào, hãy trả về giá trị sai. Sau khi duyệt qua cây thứ hai, hãy kiểm tra xem nó có tất cả trong bảng băm hay không (điều này đảm bảo có thêm dữ liệu trong cây thứ hai).
Time Complexity: O(max(m, n)), trong đó m và n là số phần tử trong BST thứ nhất và thứ hai. Space Complexity: O(max(m, n)). Điều này phụ thuộc vào kích thước của cây đầu tiên.
Problem-74
Đối với Problem-73, chúng ta có thể giảm độ phức tạp về thời gian không?
Solution: Thay vì thực hiện duyệt lần lượt từng cây, chúng ta có thể thực hiện duyệt inorder traversal của cả hai cây song song. Vì quá trình inorder traversal đưa ra danh sách được sắp xếp, chũng ta có thể kiểm tra xem cả hai cây có tạo ra cùng một trình tự hay không.
Time Complexity: O(max(m, n)). Space Complexity: O(1). Điều này phụ thuộc vào kích thước của cây đầu tiên.
Problem-75
Cho một BST có kích thước n, trong đó mỗi node r có một trường bổ sung r → size, số node trong cây con có gốc tại r (bao gồm cả node gốc r). Đưa ra thuật toán có O(h) GreaterthanConstant(r, k) để tìm số node có data lớn hơn k (h là chiều cao của cây tìm kiếm nhị phân).
Solution:
public int GreaterThanConstant(BinarySearchTreeNode r, int k){
int count = 0;
while (r != null) {
if (k < r.getData()) {
count = count + r.getRight().getSize() + 1;
r = r.getLeft();
} else if (k > r.getData()) {
r = r.getRight();
} else { // k = r.getData();
count = count + r.getRight().getSize();
break;
}
}
return count;
}
Thuật toán được đề xuất hoạt động tốt nếu data là một duy nhất cho mỗi node. Mặt khác, khi đến k=r.data, chúng ta nên bắt đầu quá trình di chuyển sang phải cho đến khi đến node y có data lớn hơn k, sau đó chúng ta nên trả về count + y.size.
Time Complexity: O(h) với h=O(n) trong trường hợp xấu nhất(cây xiên) và O(logn) trong trường hợp trung bình.
All rights reserved
