Lưu ý: Đối với các vấn đề liên quan đến thứ tự với cây tìm kiếm nhị phân(binary search trees) và cây tìm kiếm nhị phân cân bằng (balanced binary search trees), Inorder traversal có lợi thế hơn các loại duyệt khác vì nó đưa ra thứ tự được sắp xếp.
Problem-52
Đưa ra thuật toán tìm đường đi ngắn nhất giữa hai node trong BST.
Solution: Không gì khác ngoài việc tìm LCA của hai node trong BST. [Problem 54]
Problem-53
Đưa ra thuật toán đếm số BST có thể có với n node.
Solution: Đây là một vấn đề của Dynamic Programming. Mình sẽ trình bày chi tiết khi viết tới chương này.
Problem-54
Đưa ra các con trỏ tới hai node trong cây tìm kiếm nhị phân, hãy tìm tổ tiên chung thấp nhất (LCA). Giả sử rằng cả hai giá trị đã tồn tại trong cây.
Solution: Ý tưởng chính của giải pháp là: trong khi duyệt BST từ gốc xuống dưới, node đầu tiên mà chúng ta gặp phải với giá trị nằm trong khoảng từ α đến β, tức là α < node → dữ liệu < β, là Tổ tiên chung nhỏ nhất (LCA) của α và β (trong đó α < β). Vì vậy, chỉ cần duyệt qua BST theo thứ tự trước và nếu chúng ta tìm thấy một node có giá trị nằm giữa α và β, thì node đó là LCA. Nếu giá trị của nó lớn hơn cả α và β thì LCA nằm ở phía bên trái của node và nếu giá trị của nó nhỏ hơn cả a và β thì LCA nằm ở phía bên phải.
public BinarySearchTreeNode LCA(BinarySearchTreeNode root, BinarySearchTreeNode a, BinarySearchTreeNode b){ if(root == null){ return root; } if(root == a || root == b){ return root; } if (Math.max(a.getData(), b.getData()) < root.getData()) { return LCA(root.getLeft(), a, b); } else if (Math.min(a.getData(), b.getData()) > root.getData()) { return LCA(root.getRight(), a, b); } else { return root; } }
Time Complexity: O(n). Space Complexity: O(n), đối với cây nghiêng.
Problem-55
Đưa ra thuật toán kiểm tra xem cây nhị phân đã cho có phải là BST hay không.
Solution: Hãy xem xét chương trình đơn giản dưới đây, đối với mỗi node, hãy kiểm tra xem node bên trái của nó có nhỏ hơn không và kiểm tra xem node bên phải có lớn hơn không.
public boolean isBST(BinaryTreeNode root){ if (root == null) { return false; } if(root.getLeft() != null && root.getLeft().getData() > root.getData()){ return false; } if(root.getRight() != null && root.getRight().getData() < root.getData()){ return false; } if(!isBST(root.getLeft()) || !isBST(root.getRight())){ return false; } return true; }
Cách tiếp cận này là sai vì điều này sẽ trả về true cho cây nhị phân bên dưới. Chỉ kiểm tra tại node hiện tại là không đủ.
Problem-56
Chúng ta có thể nghĩ đến việc có được thuật toán chính xác không?
Solution: Đối với mỗi node, hãy kiểm tra xem giá trị lớn nhất trong cây con bên trái có nhỏ hơn dữ liệu node hiện tại và giá trị nhỏ nhất trong cây con bên phải có lớn hơn dữ liệu node hay không.
public boolean isBST(BinaryTreeNode root){ if (root == null) { return false; } if(root.getLeft() != null && findMax(root.getLeft()) > root.getData()){ return false; } if(root.getRight() != null && findMin(root.getRight()) < root.getData()){ return false; } if(!isBST(root.getLeft()) || !isBST(root.getRight())){ return false; } return true; }
Giả sử rằng chúng ta có các hàm trợ giúp FindMin() và FindMax() trả về giá trị số nguyên tối thiểu hoặc tối đa từ một cây không trống. Time Complexity: O(n2). Space Complexity: O(n).
Problem-57
Chúng ta có thể cải thiện độ phức tạp của Problem-56 không?
Solution: Yes. Một giải pháp tốt hơn là chỉ xem xét từng node một lần. Mẹo nhỏ là viết một hàm IsBST(BinaryTreeNode root, int min, int max) đi qua cây để theo dõi các giá trị tối thiểu và tối đa được phép thu hẹp khi nó di chuyển, chỉ xem xét mỗi node một lần. Các giá trị ban đầu cho min và max phải là INT_MIN và INT_MAX — chúng thu hẹp từ đó.
Initial call: isBST(root, Integer.MIN_VALUE, Integer.MAX_VALUE);
public boolean isBST(BinaryTreeNode root, int min, int max){ if(root == null){ return true; } return (root.getData() > min && root.getData() < max && isBST(root.getLeft(), min, root.getData()) && isBST(root.getRight(), root.getData(), max));
}
Time Complexity: O(n). Space Complexity: O(n), cho cây nghiêng.
Problem-58
Chúng ta có thể cải thiện hơn nữa độ phức tạp của Problem-56 không?
Solution: Có, bằng cách sử dụng inorder traversal. Ý tưởng đằng sau giải pháp này là việc duyệt inorder traversal của BST tạo ra các danh sách được sắp xếp. Trong khi duyệt BST theo thứ tự, tại mỗi node, hãy kiểm tra điều kiện rằng giá trị khóa của nó phải lớn hơn giá trị khóa của node đã truy cập trước đó. Ngoài ra, chúng ta cần khởi tạo prev với giá trị số nguyên nhỏ nhất có thể (giả sử Integer.MIN_VALUE).
private int prev = Integer.MIN_VALUE; public boolean isBST(BinarySearchTreeNode root){ if(root == null){ return true; } if(!isBST(root.getLeft())){ return true; } if(root.getData() < prev){ return false; } prev = root.getData(); return isBST(root.getRight()); }
Time Complexity: O(n). Space Complexity: O(n), cho cây nghiêng.
Problem-59
Đưa ra thuật toán chuyển BST sang circular DLL(Circular Doubly Link List) hình tròn với độ phức tạp không gian O(1).
Solution:
- Con trỏ trái và phải trong các node sẽ được sử dụng làm con trỏ trước và sau tương ứng trong Danh sách liên kết vòng được chuyển đổi.
- Thứ tự của các node trong Danh sách phải giống như trong Inorder cho Cây nhị phân đã cho.
- node đầu tiên của Inorder traversal phải là node đầu của Circular List.
// Java Program to convert a Binary Tree to a
// Circular Doubly Linked List // Node class represents a Node of a Tree
class Node { int val; Node left, right; public Node(int val) { this.val = val; left = right = null; }
} // A class to represent a tree
class Tree { Node root; public Tree() { root = null; } // concatenate both the lists and returns the head // of the List public Node concatenate(Node leftList, Node rightList) { // If either of the list is empty, then // return the other list if (leftList == null) return rightList; if (rightList == null) return leftList; // Store the last Node of left List Node leftLast = leftList.left; // Store the last Node of right List Node rightLast = rightList.left; // Connect the last node of Left List // with the first Node of the right List leftLast.right = rightList; rightList.left = leftLast; // left of first node refers to // the last node in the list leftList.left = rightLast; // Right of last node refers to the first // node of the List rightLast.right = leftList; // Return the Head of the List return leftList; } // Method converts a tree to a circular // Link List and then returns the head // of the Link List public Node bTreeToCList(Node root) { if (root == null) return null; // Recursively convert left and right subtrees Node left = bTreeToCList(root.left); Node right = bTreeToCList(root.right); // Make a circular linked list of single node // (or root). To do so, make the right and // left pointers of this node point to itself root.left = root.right = root; // Step 1 (concatenate the left list with the list // with single node, i.e., current node) // Step 2 (concatenate the returned list with the // right List) return concatenate(concatenate(left, root), right); } // Display Circular Link List public void display(Node head) { System.out.println("Circular Linked List is :"); Node itr = head; do { System.out.print(itr.val + " "); itr = itr.right; } while (itr != head); System.out.println(); }
} // Driver Code
class Main { public static void main(String args[]) { // Build the tree Tree tree = new Tree(); tree.root = new Node(10); tree.root.left = new Node(12); tree.root.right = new Node(15); tree.root.left.left = new Node(25); tree.root.left.right = new Node(30); tree.root.right.left = new Node(36); // head refers to the head of the Link List Node head = tree.bTreeToCList(tree.root); // Display the Circular LinkedList tree.display(head); }
}
Bài này trong sách tác giả viết hơi ngắn gọn nên mình có tham khảo code và thuật toán ở đây
Problem-60
Cho một danh sách liên kết kép(doubly linked list) đã được sắp xếp, hãy viết thuật toán chuyển đổi nó thành cây tìm kiếm nhị phân cân bằng.
Solution: Tìm độ dài danh sách và xây dựng cây từ dưới lên.
public BinarySearchTreeNode sortedList2BST(ListNode head){ int len = 0; ListNode currentNode = head; while(currentNode != null){ len++; currentNode = currentNode.getNext(); } return construct(head, 0, len - 1); } public BinarySearchTreeNode construct(ListNode head, int start, int end){ if(start > end){ return null; } int mid = start + (end - start)/2; BinarySearchTreeNode left = construct(head, start, mid - 1); BinarySearchTreeNode root = new BinarySearchTreeNode(head.getData()); root.setLeft(left); if(head.getNext() != null){ head.setData(head.getNext().getData()); head.setNext(head.getNext().getNext()); } root.setRight(construct(head, mid + 1, end)); return root; }
Time Complexity: 2T(n/2) + O(n) [Cho việc tìm node giữa] = O(nlogn).
Problem-61
Cho một mảng đã được sắp xếp, hãy đưa ra thuật toán để chuyển đổi mảng thành BST.
Solution: Nếu chúng ta phải chọn một phần tử mảng làm gốc của một BST cân bằng, chúng ta nên chọn phần tử nào? Gốc của BST cân bằng phải là phần tử ở giữa từ mảng đã sắp xếp. chúng ta sẽ chọn phần tử ở giữa từ mảng đã sắp xếp trong mỗi lần lặp. Sau đó, chúng ta tạo một node trong cây được khởi tạo với phần tử này. Sau khi phần tử được chọn, phần tử còn lại là gì? Bạn có thể xác định các vấn đề phụ trong vấn đề không? Có hai mảng còn lại — mảng bên trái và mảng bên phải.
Hai mảng này là các vấn đề con của vấn đề ban đầu, vì cả hai đều được sắp xếp. Hơn nữa, chúng là các cây con của node con trái và phải của node hiện tại.
Mã bên dưới tạo BST cân bằng từ mảng đã sắp xếp trong thời gian O(n) (n là số phần tử trong mảng). So sánh mức độ tương tự của mã với thuật toán tìm kiếm nhị phân. Cả hai đều đang sử dụng phương pháp chia để trị.
public BinaryTreeNode buildBST(int A[], int left, int right){ BinaryTreeNode newNode; if(left > right){ return null; } newNode = new BinaryTreeNode(); if(left == right){ newNode.setData(A[left]); newNode.setLeft(null); newNode.setRight(null); } else { int mid = left + (right - left)/2; newNode.setData(A[mid]); newNode.setLeft(buildBST(A, left, mid - 1)); newNode.setRight(buildBST(A, mid + 1, right)); } return newNode; }